The New Sudoku Players' Forum

[Mathimagics]

It took my DFS solver 275,416 visits to find the first solution (which took 5m 30s). To enumerate all solutions (of which there are 2,748,444) took 12 million visits and nearly 2 hours.

I'm an idiot (v3, or is that v4?)!

For weakly-specified puzzles, the order of DFS move selection certainly does matter. If I adopt the simple expediency of testing the available moves from the middle one first, then mid +/- 1, 2 etc then I will find the first solution, and the second, far more quickly.

For the allegedly pathological case in question, DFS = 15 (!) was sufficient to determine non-U'ness, and .01s the time!

For complete enumeration both DFS visit count and time are, of course, unaltered.

Urrgh! I really could kick myself ...

[Mathimagics]

But that's ok, public humiliation is character-building ...


... allegedly!

[Mathimagics]

I'm also running N=8, which is also still running, and has just ticked over 140,000,000 solutions

Well I've just killed that job, since I believe the number of solutions for N = 8 will exceed 6,879,707,136 . Not only will that take forever, it would blow my 32-bit counters anyway.

The logic is as follows - any LS with symbol sets {1,2,3,4} and {5,6,7,8} in a checkerboard pattern will have the same ordering.

For each set, there are (4!)(3!)(2!) = 288 ways to fix the values in half of the rows, so there are 288^2 ways to fix each set, and thus 288^4 ways to set the entire square.

This gives us a lower-bound on the maximum number of solutions, MS, for even N.

For N=4, MS = 2^4 = 16, and we actually have 17 solutions.

For N=6, MS = 24^4 = 20,736, and we actually have 25,498.

The additional solutions comes from additional OPC opportunities at the "crossover" values {N/2, N/2+1}. For example, the additional solution for N=4 arises from this case:

3 1 4 2
1 3 2 4
4 2 3 1
2 4 1 3

Swapping the values indicated gives an equivalent LS, but one that doesn't match the original {1,2} x {3,4} checkerboard pattern.

[Mathimagics]

This has 22 chains of length 3 (can this be reduced? I think not) and produces 93,527 solutions

Wrong again!

For N=7, the following LS has 45 sinks/sources, only 12 chains of length 3, and produces 156,252 solutions:

6 1 5 3 4 2 7
1 6 2 7 3 5 4
3 2 6 1 7 4 5
2 5 4 6 1 7 3
7 4 1 2 5 3 6
4 7 3 5 2 6 1
5 3 7 4 6 1 2

The highlighted entries are the only ones which aren't sources or sinks.

There is evidence to suggest that this is in fact the maximal solution count for N = 7.

[Mathimagics]

I can now advise that the exact number of 6x6 Latin squares which correspond to unique Futoshiki solutions is 217,548,736, which is 26.76366% of the total Latin squares, LS6 = 812,851,200.

blue will be pleased to see how close this figure is to his observed figure (hats off to the Pittenger random LS generator).

The number of distinct DAG's (ie. complete hint specifications) for N = 6 is 385,204,902.

Thus the 595,302,464 non-unique LS's correspond to (385204902 - 217548736) = 167,656,166 DAG's.

[Mathimagics]

After isotopy elimination, we are left with 27,209,266 genuinely distinct, unique-solution, 6x6 Latin squares

[Mathimagics]

I've yet to establish whether a unique solution is possible with a maximum chain length of 4, but they definitely exist with MCL = 5

Well, now we know, a 9x9 LS can be a unique solution with MCL = 4:

7 5 6 3 8 4 1 2 9
6 2 7 4 3 1 5 9 8
8 9 1 6 2 7 3 5 4
1 7 9 2 6 5 8 4 3
3 8 4 5 7 2 9 1 6
2 4 5 9 1 3 6 8 7
4 3 8 7 5 9 2 6 1
5 6 3 1 9 8 4 7 2
9 1 2 8 4 6 7 3 5

Code: Select all

9
><><>><<><>>><<><><><><><<><><>><><<><><<<<><<<>><>><><><>><>><>><<><<><
><><><<<><><>><><><><<>><<><<>><>><<><<>><>><<>><><<>><<<>>><><>>>><<><<


This is quite rare, it happens only once in a million U's (literally, in this case).

[denis_berthier]

a 9x9 LS can be a unique solution with MCL = 4:

7 5 6 3 8 4 1 2 9
6 2 7 4 3 1 5 9 8
8 9 1 6 2 7 3 5 4
1 7 9 2 6 5 8 4 3
3 8 4 5 7 2 9 1 6
2 4 5 9 1 3 6 8 7
4 3 8 7 5 9 2 6 1
5 6 3 1 9 8 4 7 2
9 1 2 8 4 6 7 3 5

Code: Select all

9
><><>><<><>>><<><><><><><<><><>><><<><><<<<><<<>><>><><><>><>><>><<><<><
><><><<<><><>><><><><<>><<><<>><>><<><<>><>><<>><><<>><<<>>><><>>>><<><<

This is quite rare, it happens only once in a million U's (literally, in this case).

Rare but easy: it requires only Pairs and Naked-Triplets.

[Mathimagics]

Yes, I was surprised at that (DFS = 11 in my case).

It's interesting, however, to see what happens when we reduce it:

Code: Select all

9
><-->-<---->>--><------>---->-->--<------<---<->-->>--->---->-<>-<<>-<--
-<>---<<>-><-><-<----<->-<--<>--->-<--<-----<-->---<>-<-->--->---->-<-<-


Recall my earlier reduced-form 9x9 example "1B", with DFS = 3400, and 44 hints (and MCL = 6).

This one has 53 hints, but DFS = 2,815,865, which makes it one really tough puzzle.

I've just written a new version of my solver (same DFS method, but much more efficient, 3 times faster), and it still takes 13 minutes to resolve this (ie. verify uniqueness of solution).

[denis_berthier]

Code: Select all

9
><-->-<---->>--><------>---->-->--<------<---<->-->>--->---->-<>-<<>-<--
-<>---<<>-><-><-<----<->-<--<>--->-<--<-----<-->---<>-<-->--->---->-<-<-


This one has 53 hints, but DFS = 2,815,865, which makes it one really tough puzzle.

Yep. Apart from the usual ascending chains, hills and valleys at the start, it has no elimination by subsets, whips or g-whips.

[denis_berthier]

Reviving this old thread.

I thought I remembered you had given a 6x6 example where all the inequality constraints between cells were given but that had several solutions. I'm unable to find it.

[Edit]: while I'm at it:
- do you have an example with still smaller size?
- what are your final results about the probability that a kxk Futoshiki puzzle with all the inequality constraints between cells given (and no cell value given) have a unique solution?

[Mathimagics]

Hi Denis,

All this was so long ago!

Alas, all my Futoshiki stuff is on my old PC, which is now gathering dust.