Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Futoshiki Uniqueness Testing

Postby Mathimagics » Mon Jul 06, 2015 8:46 pm

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

Futoshiki Uniqueness Testing

Postby Mathimagics » Mon Jul 06, 2015 8:47 pm

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


... allegedly! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Maximum number of Solutions

Postby Mathimagics » Wed Jul 08, 2015 3:37 am

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

Maximum number of Solutions

Postby Mathimagics » Wed Jul 08, 2015 12:25 pm

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

Unique Solutions - Size 6

Postby Mathimagics » Mon Jul 13, 2015 4:08 am

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

Unique Solutions - Size 6

Postby Mathimagics » Tue Jul 14, 2015 6:28 am

After isotopy elimination, we are left with 27,209,266 genuinely distinct, unique-solution, 6x6 Latin squares
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Futoshiki Uniqueness Testing

Postby Mathimagics » Wed Jul 15, 2015 8:44 am

mathimagics wrote: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).
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki Uniqueness Testing

Postby denis_berthier » Fri Jul 17, 2015 3:55 am

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

Futoshiki - Irreducible forms

Postby Mathimagics » Fri Jul 17, 2015 6:35 pm

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

Re: Futoshiki - Irreducible forms

Postby denis_berthier » Sat Jul 18, 2015 3:29 am

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

Previous

Return to Sudoku variants