The New Sudoku Players' Forum

Website · by **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 ?

by **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:

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

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.

by **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:

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.

Website · by **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.

by **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.

by **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.

by **Mathimagics** » Fri Jun 19, 2015 5:48 am

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

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.

Website · by **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.

by **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).

by **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:

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!

by **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.

Website · by **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.

by **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:

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.

by **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).

3

2

5

3

2

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.

by **Mathimagics** » Sun Jun 21, 2015 12:05 am

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

8

7

8

7

8

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%

The New Sudoku Players' Forum

Futoshiki Generation, properties

Re: DFS vs Symbol reflection

pU for Sudoshiki

Re: DFS vs Symbol reflection

Re: DFS vs Symbol reflection

DFS behaviour

Futoshiki properties - DFS issues

2A reflected

Re: DFS behaviour

DFS behaviour

DFS senitivity

DFS sensitivity

Re: Futoshiki Generation, properties

DFS stability achieved?

Improper LS's in Futoshiki

Order-preserving cycles