November 2019

[SmartMersenne]

Originally Posted by SmartMersenne

Do you mean this is the highest you found?

You never replied to this one. If this is good, it may be the highest determinant ever found.

[uau]

Originally Posted by SmartMersenne

You never replied to this one. If this is good, it may be the highest determinant ever found.

There was a comment from the puzzle author that it was not enough to get the award for best solution found.

[yae9911]

To support the end stage of the challenge a bit, it certainly does not hurt to provide some more information. None of this is directly suited to solving the problem, but you can then classify how good your own results are.

Some time ago the question was discussed, which determinant values can be reached with Latin squares, which would not be permissible if the puzzle definition is interpreted restrictively. The few determinant values greater than 920000000 are the following ones: 920271375, 920606715, 921397680, 923005125, 923209245, 924220125, 926679285, 929587995. All were found by stupidly performing all possible 9! symbol permutations in the list of the 2393407 9x9 Latin squares listed with title "Isotopy classes with nontrivial groups" on Brendan Mc Kay's Latin Squares web page. This gives 1747706 distinct absolute determinant values, which is still not the full list. If you are patient and have fast web access, then you can download and view a 36 MB pdf file Occurrence Counts that gives you an idea of the distribution of determinants. Determinants > 900000000 are extremely rare.

The best determinant < 929587995 of a non-Latin square known to me is 927006660, found by Hermann Jurksch outside of the challenge. The record setting determinant value found in the challenge is > 933000000.

[LaurV]

Very nice info, thank you for sharing it.

So, I am hopeless this time...

[ I have to add this puzzle to the list of the "unsolved puzzles from 'ponder this' which I would like to solve in the future, if I have time and got a better idea", probably when I will retire, if any. By unsolved I mean "by myself". Up to now, this list has three items, included the current one. It doesn't mean that I solved all the others, the most of them were too simple or too uninteresting, and few were out of my league... But this seems to be the first and only item in this list which is not definitively solved (i.e. a better solution may exist, which is not known yet), the others had an exhaustive search and a final answer by their solvers or by the puzzle promoter. ]


Edit: I edited your post to add spoiler to the score, that astronomic number may discourage some guys here

[bsquared]

Originally Posted by yae9911

The best determinant < 929587995 of a non-Latin square known to me is 927006660, found by Hermann Jurksch outside of the challenge.

The best I found was 926612865. It feels like it would eventually find 927M+ if I let it run longer, but given the other results it doesn't seem of interest to do so.

On another computer running sequence A085000(7) I've now found 25+ examples of determinant 762150368499, nothing larger. After finding the improved lower bound to A085000(8) I have stopped running it. Would it be of interest to keep looking for larger determinants there?

[a1call]

The names are up.
Someone surpassed the open question in less than 2 days.
No one designated with a single asterisk which might indicate that all who surpassed got the same result which is unlikely.
Congratulations to all who got the answer.

[bsquared]

Originally Posted by a1call

The names are up.
Someone surpassed the open question in less than 2 days.
No one designated with a single asterisk which might indicate that all who surpassed got the same result which is unlikely.
Congratulations to all who got the answer.

Oleg was kind enough to post his solution and code, which still seem like magic to me.

Of no use whatsoever now, but just before I killed my search programs I found a matrix with determinant 927380637. Still satisfying and a nice ending point.

The search method I used was random hill climbing. Rough pseudocode:

nov2019():
    while (1)
        m = create_random_matrix()

        d1 = determinant(m)
        d2 = d1
        do
            d1 = d2
            m = find_best_swap(m)
            d2 = determinant(m)
        while (d2 > d1) 

find_best_swap(m):
    best = determinant(m)
    best_m = m
    for i=1:81
        for j=i+1:81
            swap(m[i],m[j])
            d = determinant(m)
            if (d > best)
                best_m = m
            swap(m[i],m[j])

    return best_m

find_best_swap() benefited greatly from uau's hint because it nearly eliminates the innermost determinant at the cost of a single inverse at the beginning; probably he was doing something similar to the above.

Cheers to all!

[edit]
I found that for the other matrix type (https://oeis.org/A085000) the search benefits a lot from annealing, where find_best_swap can accept matrices worse than the input with probability decreasing with distance from the input. The challenge matrices did not benefit from this.

[uau]

Originally Posted by a1call

The names are up.
Someone surpassed the open question in less than 2 days.

The results don't tell that. Stars can be added to names later, and the timestamp is not changed. So if you submit the worst possible passable solution at the start of the challenge, and improve it at the last second of the challenge, you'll have your name on the list with an early timestamp and a star.

[yae9911]

@uau: With the suggestion that Oleg's first solution was not yet optimal, you are probably right, because I received an E-mail from IBM's puzzlemaster Oded dated Nov 12, 2019, 10:22 AM, in which he reported that now the problem was solved. I guess I will not reveal any secrets or anything private now if I quote this:

...
I'm happy to tell you that I just got, from Oleg, a solution to the open problem:
941568327
594632187
859214736
437981526
368197254
175829634
682473951
716746491
223355889

Note that it has some nice properties.

[EdH]

The best I found were several above 921e6 (a couple 922e6), but still below 923e6, but I was partly infatuated with the 929e6 latin square and started using it for a starting matrix. I also tried using the 921/922e6 squares, too. At one point I had over 175 cores running. Better programming skills were definitely a necessity - something I hopefully did advance a little. . .


Congrats to all!

[yae9911]

Originally Posted by a1call

No one designated with a single asterisk which might indicate that all who surpassed got the same result which is unlikely.

Once it was clear that the "**" problem had been solved, it was planned to give the submitters of record setting solutions an additional "*". Apparently, however, all submitted "**" solutions reached the same target value.
A proof that this solution is really optimal now is out of reach, but I will risk taking this value as the next entry A301371(9), similar to the inclusion of A085000(7) that has received multiple confirmations, including those from b².