The New Sudoku Players' Forum

[Mathimagics]

Just an update to the above post. I actually checked the DFS rating for each of these, and (again to my surprise), the case of the least number of hints was not the "hardest", in fact quite the opposite. It only required 8 (or 12, I'm not sure as there were two cases with nHints = 20), while for the batch the average was DFS = 36, with a maximum of DFS = 1457.

That max is pretty high for a 7x7 puzzle, here's the spec:

Code: Select all

 7
---><>-><---->-><--->-->-<<>-<><---><--<--
>>-<----<----<---------<>---->---->>>-----


[denis_berthier]

Just an update to the above post. I actually checked the DFS rating for each of these, and (again to my surprise), the case of the least number of hints was not the "hardest", in fact quite the opposite.

No surprise here for me. In Sudoku, for minimal puzzles:
- there is no correlation between the number of clues and the rating
- even when the puzzles have the same solution

The way I understand it is, all the clues do not have the same impact on resolution. Some useless clues have no impact at all; e.g. starting from a minimal P and adding clues clues obtained from Singles doesn't change the rating.
In Futoshiki, it might be interesting to see if the impact of deleted clues is related to properties of the < graph.

For the above 4 puzzles:
7 ">><><>>><><><>>><<<>><<>><<>><><><>><<><><" ">>><<><<<><><<>><<>>><><>><<<><><>>>><><><" ==> W = 0
7 "------>>----->-------<---<-->------><--<--" "----<---<--><->>--------->---><-->---->---" ==> W = 2
7 "----->>-->---->-----><---<->>->--->-<-><--" ">-><<------><<>-<<>----->>-<--<---->-->-><" ==> W = infinity
7 "---><>-><---->-><--->-->-<<>-<><---><--<--" ">>-<----<----<---------<>---->---->>>-----" ==> W = infinity


One more thing that is not a surprise: having (apparently many) small puzzles not in T&E(1). Once more, it shows that < constraints are weak ones.

[Mathimagics]

Some useless clues have no impact at all

I analysed the log from that run (which now includes over 10,000 reduced forms) and checked to see if any hints were absent in all cases or present in all cases, neither of which occurred.

In Futoshiki, it might be interesting to see if the impact of deleted clues is related to properties of the < graph.

I've asked a question on StackExchange (CS) about this. I might try and contact Brendan McKay (ANU, he's just down the road from me) who provided the LS data for my 6x6 enumeration, and who is author of a graph processing library ("nauty"). He might have some insights.

[denis_berthier]

Some useless clues have no impact at all

I analysed the log from that run (which now includes over 10,000 reduced forms) and checked to see if any hints were absent in all cases or present in all cases, neither of which occurred.

That was to be expected. The useless clues I mentioned are useless only in the context of other clues.

[Mathimagics]

Just heard back from Brendan McKay - he says the problem (what's special about the LS / DAG relationships) is both interesting and challenging, and wished me luck ...

He has, however, identified a couple of things I might look into ...

[Mathimagics]

I think that the DAG idea is not going to be useful. It's essentially a reformulation of the same problem.

I realised that, in trying to make my digraph traversal smarter in terms of recognising LS cases, the closer it was becoming to look like a DFS solver.

DFS itself, of course, is essentially a digraph traversal algorithm.

My conclusion at this stage, is that the only distinguishing feature of latin squares with unique solutions, other than digraph uniqueness, is the absence of OPC's. However this too can be viewed as simply a reformulation of the problem.

Moreover, since OPC's can be of varying lengths/number of symbols, detecting them is a complicated process, and one that is perhaps also best handled by the DFS solver.

[Mathimagics]

Moreover, since OPC's can be of varying lengths/number of symbols, detecting them is a complicated process, and one that is perhaps also best handled by the DFS solver.

That depends on the circumstances, it seems.

I have redesigned my OPC tester, and it is now more efficient. It concentrates on cases that are relatively easy to detect, and are the most common. This involves symbol-cycles of 2 to 4, with a maximum span of 4 rows, 4 columns. These are now picked up by a simpler submatrix-pattern search.

For larger grid sizes (N >= 7), this is most effective, when applied to the specific problem of determining whether or not a random Latin square, of uncertain provenance, corresponds to a unique solution.

This also assumes we want a thorough investigation. In other words we do not wish to simply bailout if DFS reaches a certain value, we want to be mathematically certain of the result. (More on bailout conditions later).

You may recall the example I quoted whose LS was just one of 372,377 LS's which had the same DAG. Apply any one of these to a (thorough) uniqueness test and they will require 23,616 DFS visits to demonstrate that they are not unique.

Testing any of these cases with the OPC detector will correctly identify all except a handful as non-unique, so no DFS is required.

This makes a big difference when generating random LS's in order to find unique solution cases. For N=9 grids this runs 4 times faster with OPC checking (and on average it found OPC's in half of the non-unique cases).

On my system, for 1000 unique solutions, it takes about 150 minutes without OPC check, 35 minutes with OPC check.

[Mathimagics]

The Markov unique-solution generator seems to be quite good. Connectivity issues aside, it is much faster, generating at the rate of 1000 U's in 45-90 seconds.

As far as connectivity is concerned, I think the fact that unique solutions correspond to 1% of 9x9 LS cases is significant. There are, I think, far more Pittenger perturbations available at each step, so the chances are relatively good that a U will be found.

Is there an N for which this no longer holds true? That's hard to predict, because of the weird behaviour of growth rates for LS's.

Brendan McKay told me that the number of DAG's (2 ^ (2N x (N-1)) was generally less than the number of LS's, which I found staggering since it didn't seem to match with reality. But he was right, apparently somewhere around N = 20 the growth rate of LS's becomes quite extreme, and overtakes the DAG count around N = 23.

[Mathimagics]

This could well be a candidate! This has the highest DFS rating I have yet encountered for a 9x9 LS.

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

The specification:

Code: Select all

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


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.

Now we can see on closer inspection that the LS contains an OPC, highlighted below:

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

That's a pretty good demonstration of the usefulness of the cycle detector!

There are other clues which, while indicative of ambiguity, are sadly not (yet) definitive:

• the maximum chain length is only 4
• the number of reversals (direction changes) in the spec is also quite high (95)

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.

Reversals (swaps) in the spec are also a potential indicator, yet to be explored in any detail. There is a suggestion that a high reversal count, particularly in combination with low average chain length (ACL), might be a strong indicator of ambiguity.

[denis_berthier]

The specification:

Code: Select all

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

Now we can see on closer inspection that the LS contains an OPC, highlighted below:

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

Apart from the obvious initial ones due to ascending-chains, hills and valleys, the puzzle with no digit data doesn't allow many eliminations:
(solve 9
"................................................................................."
"><<><><>>><<<>><<<>><><><>><><>><<>><>><<><>><>><<><><>>><<><><><><<><><"
">><><><<<<<><>><><><><>>><><<><><><><<><<>><>><><><><<><><>><<<><>><><<<")

Hidden Text: Show

Code: Select all

whip[2]: r2n2{c4 c8} - r2n1{c8 .} ==> r2c3 ≠ 4, r2c3 ≠ 3
whip[2]: r9c3{n6 n1} - r2c3{n1 .} ==> r8c3 ≠ 2
whip[4]: r5c8{n4 n1} - r2n1{c8 c3} - r6n1{c3 c9} - r4c9{n1 .} ==> r4c8 ≠ 2
whip[5]: r9c9{n7 n9} - r2n9{c9 c6} - r5n9{c6 c3} - r3n9{c3 c8} - r8c8{n9 .} ==> r8c9 ≠ 8
str-asc[2]: r6c9<r7c9<r8c9 ==> r7c9 ≠ 7
whip[5]: r6n1{c9 c3} - r6n2{c3 c6} - r7c6{n5 n1} - r9n1{c6 c8} - r2n1{c8 .} ==> r6c9 ≠ 5
whip[4]: r6c5{n8 n3} - r6c6{n6 n2} - r6c3{n2 n1} - r6c9{n1 .} ==> r6c4 ≠ 4
whip[5]: r6n1{c9 c3} - r6n2{c3 c6} - r7c6{n5 n1} - r9n1{c6 c8} - r2n1{c8 .} ==> r6c9 ≠ 4, r6c9 ≠ 3
whip[2]: r4c9{n6 n1} - r6c9{n1 .} ==> r3c9 ≠ 2


However, if we fix all the values corresponding to the above cycle,
(solve 9
".....6.5.....6.5.......5..6....5..6..................................6.5........."
"><<><><>>><<<>><<<>><><><>><><>><<>><>><<><>><>><<><><>>><<><><><><<><><"
">><><><<<<<><>><><><><>>><><<><><><><<><<>><>><><><><<><><>><<<><>><><<<")

we get many more eliminations. Again, I skip the obvious initial ones due to ascending-chains, hills and valleys (there are more than before, because of more Singles).

Hidden Text: Show

Code: Select all

whip[1]: r7n6{c4 .} ==> r7c3 ≠ 5, r7c3 ≠ 4
whip[2]: r9n6{c3 c4} - r9n5{c4 .} ==> r9c2 ≠ 4
whip[2]: c8n9{r8 r3} - c8n8{r3 .} ==> r8c8 ≠ 7
whip[2]: r8c8{n8 n9} - r8c4{n9 .} ==> r8c3 ≠ 8
str-asc[1]: r8c2<r8c3 ==> r8c2 ≠ 4
str-asc[1]: r9c3<r8c3 ==> r9c3 ≠ 6, r9c3 ≠ 5, r9c3 ≠ 4
whip[1]: c3n5{r6 .} ==> r6c3 ≠ 6
whip[2]: r6n6{c2 c4} - r6n5{c4 .} ==> r6c2 ≠ 4
whip[2]: r6n6{c2 c4} - r6n9{c4 .} ==> r6c2 ≠ 5
whip[2]: r9n5{c2 c4} - r9n6{c4 .} ==> r9c1 ≠ 7, r9c1 ≠ 8
str-asc[2]: r7c1<r8c1<r9c1 ==> r8c1 ≠ 7, r7c1 ≠ 5
str-asc[1]: r7c1<r8c1 ==> r7c1 ≠ 4
whip[2]: c1n5{r6 r9} - c1n6{r9 .} ==> r6c1 ≠ 3, r6c1 ≠ 4
whip[2]: r7n5{c4 c2} - r7n6{c2 .} ==> r7c4 ≠ 7
whip[2]: r7n5{c2 c4} - r7n6{c4 .} ==> r7c2 ≠ 7, r7c2 ≠ 8
whip[2]: r8c1{n3 n4} - r8c3{n4 .} ==> r8c2 ≠ 3
whip[2]: r8c2{n2 n1} - r1c2{n1 .} ==> r2c2 ≠ 2
str-asc[1]: r2c2<r2c1 ==> r2c1 ≠ 3
str-asc[1]: r2c2<r3c2 ==> r3c2 ≠ 3
whip[2]: r2n2{c4 c8} - r2n1{c8 .} ==> r2c3 ≠ 3
whip[2]: r9c3{n3 n1} - r2c3{n1 .} ==> r8c3 ≠ 2
whip[2]: c3n5{r6 r5} - r5n6{c2 .} ==> r6c1 ≠ 5
str-asc[1]: r6c1<r6c2 ==> r6c2 ≠ 6
whip[1]: r6n5{c4 .} ==> r6c4 ≠ 4
whip[2]: c5n9{r7 r9} - c5n8{r9 .} ==> r7c5 ≠ 7
whip[1]: r7n7{c8 .} ==> r7c8 ≠ 8
str-asc[2]: r6c9<r6c8<r7c8 ==> r6c8 ≠ 7
hidden-pairs-in-a-column: c8{n8 n9}{r3 r8} ==> r3c8 ≠ 7
naked-pairs-in-a-row: r3{c3 c8}{n8 n9} ==> r3c2 ≠ 8
str-asc[2]: r2c3<r2c2<r3c2 ==> r2c2 ≠ 7
str-asc[1]: r1c2<r2c2 ==> r1c2 ≠ 4
whip[2]: r3c2{n4 n7} - r3c4{n7 .} ==> r3c5 ≠ 4
whip[2]: c5n7{r6 r9} - c5n8{r9 .} ==> r7c5 ≠ 4
whip[2]: r5n6{c4 c1} - r5c2{n6 .} ==> r5c3 ≠ 5
hidden-singles ==> r6c3 = 5, r6c9 = 1
whip[2]: r6n2{c6 c8} - r6n3{c8 .} ==> r6c6 ≠ 4
str-asc[1]: r7c6<r6c6 ==> r7c6 ≠ 3
whip[2]: r7c1{n3 n1} - r7c6{n1 .} ==> r7c2 ≠ 2
whip[2]: r4n9{c2 c7} - r4n8{c7 .} ==> r4c2 ≠ 7
naked-triplets-in-a-column: c7{r4 r7 r9}{n9 n8 n7} ==> r6c7 ≠ 8, r6c7 ≠ 7
naked-single ==> r6c7 = 4
str-asc[1]: r5c8<r5c7 ==> r5c8 ≠ 3
naked-pairs-in-a-row: r6{c6 c8}{n2 n3} ==> r6c5 ≠ 3
str-asc[1]: r6c5<r6c4 ==> r6c4 ≠ 7, r6c4 ≠ 6
naked-single ==> r6c4 = 9
hidden-single-in-a-row ==> r6c1 = 6
str-asc[1]: r8c5<r8c4 ==> r8c5 ≠ 7
str-asc[2]: r9c3<r9c4<r8c4 ==> r9c4 ≠ 7
hidden-pairs-in-a-column: c1{n7 n8}{r2 r4} ==> r4c1 ≠ 4, r4c1 ≠ 3, r2c1 ≠ 4
hidden-pairs-in-a-row: r8{n8 n9}{c6 c8} ==> r8c6 ≠ 7
hidden-singles ==> r8c4 = 7, r3c2 = 7
naked-singles ==> r6c2 = 8, r4c2 = 9, r6c5 = 7
str-asc[2]: r2c3<r2c4<r3c4 ==> r2c4 ≠ 4
hidden-pairs-in-a-column: c5{n8 n9}{r7 r9} ==> r9c5 ≠ 4
x-wing-in-columns: n9{c5 c7}{r7 r9} ==> r9c9 ≠ 9, r7c3 ≠ 9
whip[2]: r5c5{n4 n1} - r5c8{n1 .} ==> r5c4 ≠ 2
whip[2]: r5c1{n5 n1} - r5c8{n1 .} ==> r5c2 ≠ 2
hidden-pairs-in-a-column: c2{n1 n2}{r1 r8} ==> r1c2 ≠ 3
naked-triplets-in-a-row: r9{c5 c7 c9}{n8 n9 n7} ==> r9c8 ≠ 7
hidden-single-in-a-column ==> r7c8 = 7
naked-pairs-in-a-row: r7{c5 c7}{n8 n9} ==> r7c3 ≠ 8
naked-single ==> r7c3 = 6
whip[2]: r5n5{c2 c4} - r5n6{c4 .} ==> r5c2 ≠ 3, r5c2 ≠ 4
naked-pairs-in-a-column: c2{r5 r9}{n5 n6} ==> r7c2 ≠ 5
hidden-singles ==> r7c4 = 5, r4c4 = 1
naked-triplets-in-a-row: r9{c5 c7 c9}{n8 n9 n7} ==> r9c6 ≠ 7
naked-triplets-in-a-column: c9{r1 r4 r7}{n4 n3 n2} ==> r5c9 ≠ 4, r5c9 ≠ 3
hidden-triplets-in-a-row: r5{n7 n8 n9}{c9 c6 c3} ==> r5c6 ≠ 4
whip[3]: r5c7{n3 n2} - r5c8{n2 n1} - r5c5{n1 .} ==> r5c4 ≠ 3
whip[3]: c4n2{r2 r9} - r9c3{n3 n1} - r2n1{c3 .} ==> r2c8 ≠ 2
biv-chain[4]: r3n4{c1 c4} - r5c4{n4 n6} - r5c2{n6 n5} - c1n5{r5 r9} ==> r9c1 ≠ 4
whip[4]: r6n2{c6 c8} - r5c8{n2 n1} - r9n1{c8 c3} - r2n1{c3 .} ==> r9c6 ≠ 2
whip[4]: r9n2{c4 c8} - r9n1{c8 c6} - r7c6{n1 n2} - r6n2{c6 .} ==> r9c3 ≠ 3
naked-pairs-in-a-column: c3{r2 r9}{n1 n2} ==> r4c3 ≠ 2
x-wing-in-columns: n2{c3 c4}{r2 r9} ==> r9c8 ≠ 2
whip[5]: r6n2{c6 c8} - r5c8{n2 n1} - r2n1{c8 c3} - r9n1{c3 c6} - r7c6{n1 .} ==> r4c6 ≠ 2
hidden-single-in-a-row ==> r4c9 = 2
naked-pairs-in-a-row: r7{c2 c9}{n3 n4} ==> r7c1 ≠ 3
whip[5]: r8c3{n4 n3} - r8c1{n3 n2} - r7n2{c1 c6} - r6c6{n2 n3} - r4n3{c6 .} ==> r8c5 ≠ 4
whip[9]: r1c2{n2 n1} - c7n1{r1 r3} - r3n2{c7 c1} - r7c1{n2 n1} - c6n1{r7 r9} - c6n4{r9 r4} - c3n4{r4 r8} - c1n4{r8 r5} - c5n4{r5 .} ==> r1c5 ≠ 2


I wonder how many solutions the "impure" Futoshiki puzzle (with the ".....6.5.....6.5.......5..6....5..6..................................6.5........." digit sequence) has.
I also wonder if this could still be reduced by other permutation chains.

[Mathimagics]

I will investigate the effect of presetting the permutation cycle. I know from inspecting the first few solutions we'd need to preset many more to fix a solution.

Meanwhile that example is just a baby when it comes to number of siblings (solutions with same ordering). See my next post.

[Mathimagics]

Now we understand a bit more about order vs disorder, it seems obvious that the example above is not going to be a record at all!

We can directly construct an example with maximal disorder, and use that to place an (expected) upper bound on the number of solutions (ie. the maximum number of LS's that can correspnd to a DAG).

For N = 6, and indeed any even N, this is particularly easy:

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

This LS has the maximum degree of disorder, and the minimum possible MCL and ACL. Every cell is a sink or a source, so every chain is minimal, length 2. This gives rise to 25,498 solutions.

For odd N, we can't achieve this perfect state of disorder, but can go very close, having every cell except the main diagonal being a sink or source. For example, N=7:

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

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

As to our N=9 example, it looks like this:

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

This has 72 source/sinks, and 30 chains of length 3. The number of solutions (or LS's with same degree of disorder) is 45,000,000+ (and it's still running!).

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

[Mathimagics]

I wonder how many solutions the "impure" Futoshiki puzzle (with the ".....6.5.....6.5.......5..6....5..6..................................6.5........." digit sequence) has.

84

I also wonder if this could still be reduced by other permutation chains.

Well this is always true. For example, fixing the values for the simple OPC at {r7,c5} x {r9,c7} = {8,9} reduces the solution count to 24.

To make it unique, we need to fix the values for

• the {8,9} cycle in r={2,3,6,8}, c={3,6,7,9}
• the {1,2,3} cycle in r={5,6,7,9}, c={1,6,8}

The resulting spec would be:

".....6.5.....685.9..8..5.96....5..6.3.9....18.....3.2.1...829.......9685....9183."

The number of presets required to fix uniqueness will (I think, it remains to be seen) vary according to which of the 2,748,444 original solutions we started with.

[denis_berthier]

To make it unique, we need to fix the values for

• the {8,9} cycle in r={2,3,6,8}, c={3,6,7,9}
• the {1,2,3} cycle in r={5,6,7,9}, c={1,6,8}

The resulting spec would be:
".....6.5.....685.9..8..5.96....5..6.3.9....18.....3.2.1...829.......9685....9183."

which makes it trivial : it can be solved using only ascending chains and singles.

[Mathimagics]

which makes it trivial : it can be solved using only ascending chains and singles.

Well that's hardly surprising, since we have filled in 37% of the grid!