Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: DFS vs Symbol reflection

Postby denis_berthier » Fri Jun 19, 2015 3:27 am

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: 1253
Joined: 19 June 2007
Location: Paris

pU for Sudoshiki

Postby Mathimagics » Fri Jun 19, 2015 4:25 am

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

Re: DFS vs Symbol reflection

Postby Mathimagics » Fri Jun 19, 2015 4:47 am

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! :shock:

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

Re: DFS vs Symbol reflection

Postby denis_berthier » Fri Jun 19, 2015 5:06 am

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: 1253
Joined: 19 June 2007
Location: Paris

DFS behaviour

Postby Mathimagics » Fri Jun 19, 2015 5:35 am

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! :roll:

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

Futoshiki properties - DFS issues

Postby Mathimagics » Fri Jun 19, 2015 5:40 am

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

2A reflected

Postby Mathimagics » Fri Jun 19, 2015 5:48 am

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

Re: DFS behaviour

Postby denis_berthier » Fri Jun 19, 2015 5:50 am

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: 1253
Joined: 19 June 2007
Location: Paris

DFS behaviour

Postby Mathimagics » Fri Jun 19, 2015 6:02 am

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

DFS senitivity

Postby Mathimagics » Fri Jun 19, 2015 6:42 am

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

DFS sensitivity

Postby Mathimagics » Fri Jun 19, 2015 6:50 am

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

Re: Futoshiki Generation, properties

Postby denis_berthier » Fri Jun 19, 2015 3:22 pm

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: 1253
Joined: 19 June 2007
Location: Paris

DFS stability achieved?

Postby Mathimagics » Sat Jun 20, 2015 12:15 pm

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

Improper LS's in Futoshiki

Postby Mathimagics » Sat Jun 20, 2015 3:58 pm

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

Order-preserving cycles

Postby Mathimagics » Sun Jun 21, 2015 12:05 am

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%

User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

PreviousNext

Return to Sudoku variants