## Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: DFS vs Symbol reflection

Mathimagics wrote:I ran the DFS on Reduction_1B, with all the hints reversed. It produced the expected solution (a reflection of the grid values) and with the same DFS visit count and time.
That suggests iso-stability, I think?

Indeed, it really puzzles me.
DFS, which normally accepts "guesses", is not invariant under isos when you look for a solution of a 1-sol puzzle (and you stop as soon as you've found it).
There must be more than DFS (and asc-chains) in your solver.

Could you make the test on a real puzzle, e.g. 2A ?
And also try the other symmetries ?
denis_berthier
2010 Supporter

Posts: 1620
Joined: 19 June 2007
Location: Paris

### pU for Sudoshiki

I've just adapted my solver to work with the extra constraints imposed by region membership, so I can now estimate the likelihood p(u) of uniqueness (maximal hints + no restrictions on chains) for Sudoshiki as:

11:25:03 Start generator
11:38:32 Sudoku mode
11:38:32 Generated = 12133, nU = 3890, pU = 32.061%

Then I ran it with the restriction that the Sudoku grid had at least one 9-chain and got the expected boost:

14:04:03 Start generator
14:04:03 Sudoku mode
14:04:03 Hints = 144, max chain len = 9
14:06:27 Generated = 13812, nU = 6483, pU = 46.937%

How random my Sudoku grids are is hard to estimate. I found that filling in the top 3 regions one by one, randomly selecting from the available values at each step minimised the amount of backtracking and the generation process was quite fast. I'm not sure anybody has come up with a mathematically rigorous random Sudoku generator, based on a quick trawl of the web.

To get a Sudoku grid with a 9-chain I simply performed random walks on each grid generated until I found a walk with 9 different values (insisting on crossing a region boundary once or twice), then permuted the symbols to achieve the desired effect.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: DFS vs Symbol reflection

denis_berthier wrote:Indeed, it really puzzles me. DFS, which normally accepts "guesses", is not invariant under isos when you look for a solution of a 1-sol puzzle (and you stop as soon as you've found it).

I'm an idiot!

I never implemented a "stop at 1 soln" option, since I assumed I'd always want to know whether the solution is unique.

When I run it with a "stop at 1" option, I get this:

14:44:08 Puzzle id = Reduction_1B
14:44:08 Hints = 44, max chain len = 6
14:44:08 NS = 1, DFS = 16, et = 0.042214

Whoa!

denis_berthier wrote:Could you make the test on a real puzzle, e.g. 2A ?
And also try the other symmetries ?

What's a real puzzle?

I take it you mean from an acknowledged source, like H4062.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: DFS vs Symbol reflection

Mathimagics wrote:
denis_berthier wrote:Could you make the test on a real puzzle, e.g. 2A ?
And also try the other symmetries ?

What's a real puzzle?
I take it you mean from an acknowledged source, like H4062.

More generally: valid (even if not minimal), i.e. with only one solution.
I suggested 2A because it is not too easy.
denis_berthier
2010 Supporter

Posts: 1620
Joined: 19 June 2007
Location: Paris

### DFS behaviour

denis_berthier wrote:More generally: valid (even if not minimal), i.e. with only one solution

Ah, now, we have a little nomenclature problem. Where I come from a valid puzzle is simply one whose parameters are consistent, ie. have one or more solutions.

A well-formed puzzle is one that allows only one solution.

Before I proceed, a news report just come to hand ...

It has been independently confirmed - yes, it seems that I really an am idiot!

I spent so much time working on the domain shaving routines that I forgot all about those few lines buried in amongst the DFS solver:

Code: Select all
` for each V in the list of possible moves   { Set cell(r, c) = V;    call DFS}`

Knd of explains a lot, doesn't it? 1B yields just 2 measly inferences at the first level, neither of which is in a chain. If the first value I pick is 1, and that's right, it will fly. If it's 9 then I'll die waiting, wishing I'd solved the reflected version.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Futoshiki properties - DFS issues

I suppose I could work from the centre, picking the median V and doing it first, then V+, V- etc..

Of course that only makes sense if you know the puzzle is well-formed. If you're testing uniqueness I don't see any easy way out.

With cell selection, I give preference to cells that are in chains, and are near to cells whose values I have.

None of which helps me at the very top level of a stinker like 1B.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### 2A reflected

2A is quite stable, either way takes about the same:

15:42:09 Puzzle id = Reduction_2A
15:42:09 Hints = 46, max chain len = 9
15:42:30 NS = 1, DFS = 7, et = 0.009243
15:42:30
15:42:40 Puzzle id = Reduction_2A
15:42:40 Hints = 46, max chain len = 9
15:42:47 Reversed all hints
15:42:48 NS = 1, DFS = 16, et = 0.024592

But that's to be expected, most cells are filled in the pre-shave process, so order of V selection for the search phase has less effect. The sensitivity to value selection is still evident, however.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: DFS behaviour

Mathimagics wrote:
denis_berthier wrote:More generally: valid (even if not minimal), i.e. with only one solution

Ah, now, we have a little nomenclature problem. Where I come from a valid puzzle is simply one whose parameters are consistent, ie. have one or more solutions.
A well-formed puzzle is one that allows only one solution.

OK, I'ven't been very careful in my wording.
denis_berthier
2010 Supporter

Posts: 1620
Joined: 19 June 2007
Location: Paris

### DFS behaviour

As I see it, there will be no sensitivity to isomorphisms per se. At the top level all domain shaving is the same, and the selection of which cell to try is also the same, leaving value order as the the only factor of sensitivity.

The difference between a good and a bad guess in reduced forms, when one is not seeking to test uniqueness, or enumerating all solutions, has the potential to wildly vary the outcome.

To get the fastest route to the first solution, it might be better to evaluate all V to 1 or two moves ahead, picking the one that showed the most improvement (ie. led to the greatest amount of domain reduction).

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### DFS senitivity

You can see what I mean here. The normal 1B actually starts closer to the initial target value, but things quickly deteriorate after that:

16:23:52 Puzzle id = Reduction_1B
16:23:52 Hints = 44, max chain len = 6
16:23:56 (L1) cell selected = (4,7) V = { 1 2 3 4} target is 2
16:23:56 (L2) cell selected = (4,8) V = { 2 3 4 5} target is 5
16:23:56 (L3) cell selected = (4,9) V = { 3 4 5 6} target is 6
16:24:38 NS = 1, DFS = 23595, et = 42.565899

16:25:52 Puzzle id = Reduction_1B
16:25:53 Reversing all hints
16:26:12 Hints = 44, max chain len = 6
16:26:13 (L1) cell selected = (4,7) V = { 6 7 8 9} target is 8
16:26:13 (L2) cell selected = (4,8) V = { 5 6} target is 5
16:26:13 (L3) cell selected = (4,9) V = { 4 5} target is 4
16:26:13 NS = 1, DFS = 16, et = 0.049200

When the reflected version chooses 6 at L1, the effect on the following cells is a series of "must-be" conditions 6 => 5 => 4. Even though 6 itself is wrong, the sub-tree is more quickly eliminated. The normal version is faced with far more choices.

When the normal version gets to choice 4 at the top level, he would have the same advantages, but the soln target is 2!

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### DFS sensitivity

So a stratagem that evaluated each choice for its potential domain reduction could work.

Always assuming that we know the puzzle is well-formed.

And how do we know when generating a puzzle, or reducing an existing one, when it's well-formed or not. We have no choice but to look for a second solution.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Re: Futoshiki Generation, properties

I meant the 1st-sol-only case as a test case for sensitivity to isos. It seems that your smart choice of cells reduces this sensitivity, without cancelling it.
I agree that in the normal workings of a generator, you'll need 1 of 3 possible answers: 0, 1 or more solutions.And you'll need it as fast as possible because you'll have to call it many times.
denis_berthier
2010 Supporter

Posts: 1620
Joined: 19 June 2007
Location: Paris

### DFS stability achieved?

denis_berthier wrote:It seems that your smart choice of cells reduces this sensitivity, without cancelling it.

Actually, it seems my cell choice was not as smart as it could have been. Here's my bete noir, 1B, tamed at last:
18:45:36 Puzzle id = Reduction_1B
18:45:36 Hints = 44, max chain len = 6
18:45:39 NS = 1, DFS = 3399, et = 2.837261

18:45:41 Puzzle id = Reduction_1B
18:45:41 Hints = 44, max chain len = 6
18:45:41 Reversed all hints
18:45:44 NS = 1, DFS = 3131, et = 2.656407

So that's about 10 times faster than the previous best effort, and what I'd call an acceptable time (for generation purposes).

And it is now stable under iso's!

I rewrote the cell selection logic - now I ignore chains, and simply concentrate on pairs, ie (a < b). I pick the pair with the least number of available settings. This virtually guarantees it will follow chains in any case.

I realised (finally!) that no matter how reduced it is, a well-formed puzzle will still have the property that satisfying all pairs will be sufficient to solve it.

It follows that a uniqeness test needs only to consider the grid state once all pairs have been satisifed. If there are still free cells following domain shaving (with implied moves applied) then it's not U, there are multiple solutions.

Similarly, if more than 1 "all pairs satisfied" states are detected, it's not U.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Improper LS's in Futoshiki

I've just discovered something interesting. Most of the grids generated by a random LS generator can be eliminated without troubling the Futoshiki solver.

The reason is simple - they have order-preserving cycles (OPC's).

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

You can swap the values shown without disturbing the order relationships. This LS cannot possibly have property U.

To my surprise, of 10,000 random LS generations, 60% had cycles like these, and my checker only detects 2-symbol and 3-symbol cycles. I will try to increase this capability.

This will change our calculations of p(U) considerably, I would imagine. We really only want to consider proper grids,ie grids with no OPC's.

A test run seems to confirm that p(U) for 9x9 grids increases from 1% to 2.5% with only proper grids being tested.

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

### Order-preserving cycles

I've improved the OPC detector. It now picks up cases like this:

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

It can detect a 2-symbol-cycle that spans multiple rows/cols (Jacobson & Matthews use cycles like this in their random LS method).

Now, as expected, the number of proper Latin squares decreases sharply, and the number of proper LS's that lead to unique solutions rises accordingly:

Code: Select all
`Gen = 20697, Proper = 486, p(P) = 2.348%, n(V=>U) = 195, p(V=>U) = 40.123%`

Mathimagics
2017 Supporter

Posts: 1581
Joined: 27 May 2015
Location: Canberra

PreviousNext