Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Futoshiki - Irreducible forms

Postby Mathimagics » Sun Jun 28, 2015 10:15 pm

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
---><>-><---->-><--->-->-<<>-<><---><--<--
>>-<----<----<---------<>---->---->>>-----
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Futoshiki - Irreducible forms

Postby denis_berthier » Mon Jun 29, 2015 4:06 am

Mathimagics wrote: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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Futoshiki - Irreducible forms

Postby Mathimagics » Mon Jun 29, 2015 5:49 am

denis_berthier wrote: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.

denis_berthier wrote: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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Futoshiki - Irreducible forms

Postby denis_berthier » Mon Jun 29, 2015 6:30 am

Mathimagics wrote:
denis_berthier wrote: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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Futoshiki Uniquness, Graph Theory

Postby Mathimagics » Mon Jun 29, 2015 8:52 am

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 ... 8-)

He has, however, identified a couple of things I might look into ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Futoshiki and Dag Properties

Postby Mathimagics » Thu Jul 02, 2015 8:11 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Futoshiki and Uniqueness testingg

Postby Mathimagics » Fri Jul 03, 2015 5:17 pm

Mathimagics wrote: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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Futoshiki Generation with Markov chain

Postby Mathimagics » Fri Jul 03, 2015 5:29 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Futoshiki - Non-unique World Record?

Postby Mathimagics » Sun Jul 05, 2015 3:31 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Futoshiki - Non-unique World Record?

Postby denis_berthier » Mon Jul 06, 2015 6:33 am

Mathimagics wrote: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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Not a World Record

Postby Mathimagics » Mon Jul 06, 2015 9:15 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Futoshiki - Non-unique World Record?

Postby Mathimagics » Mon Jul 06, 2015 9:19 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Futoshiki Uniqueness Testing

Postby Mathimagics » Mon Jul 06, 2015 1:37 pm

denis_berthier wrote: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

denis_berthier wrote: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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Futoshiki Uniqueness Testing

Postby denis_berthier » Mon Jul 06, 2015 2:09 pm

Mathimagics wrote: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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Futoshiki Uniqueness Testing

Postby Mathimagics » Mon Jul 06, 2015 4:17 pm

denis_berthier wrote: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! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to Sudoku variants