constrained puzzles

gsf · Posted: Mon Sep 19, 2005 7:11 am Post subject: constrained puzzles

Details and examples posted at http://www.research.att.com/~gsf/sudoku/

Consider the basic constraint set:

and define constraint propagation to be the repeated application of the
constraint set until no cell values change.

A constrained puzzle is solvable by constraint propagation (no trial
and error.)

A magic cell set is the smallest set of solution cells with the
smallest number of candidate values that produces a constrained puzzle.
("magic cell" was coined by Vegard Hanssen in a private communication.)

A puzzle with 0 magic cells is constrained.

A puzzle with M magic cells is M-constrained.

A survey of ~225M puzzles produced the following counts:

Adding box claims, naked and hidden tuples, weak cycles (generic
xwing/swordfish) and strong cycles (fishy?) to the constraint set
produced:

No 3-constrained or greater puzzle was found for either constraint set.

It was a surprise that the 2-constrained puzzles were so rare and that
no 3-constrained puzzles were found.

Magic cells might form the basis for a new solver constraint. The
empirical data that most unconstrained puzzles are just one cell away
from being constrained is compelling.

dukuso · Posted: Mon Sep 19, 2005 11:51 am Post subject:

thanks. 2e8 sudokus !
hmm, the table suggests that there could be
6e21/2e8*0.1 - 6e21/2e8*0.01 = 3e12 - 3e11
17s, and Gordon already has 2e4*3e6=6e10.
Where are the 60000 17s from ? Gordon has only about 25000

what's the average number
of clues in a random minimal sudoku
generated by your method ?

I get 24.3 when starting from a full random grid and
23.9 when starting from an empty grid.

I don't understand, what a "magic cell" is.

What's a "solution cell" ?
Is the (C-) constrained-puzzle produced by the candidate values or by
the solution cells and how ?

-Guenter

gsf · Posted: Mon Sep 19, 2005 1:59 pm Post subject:

Lummox JR · Posted: Mon Sep 19, 2005 3:39 pm Post subject:

This is quite a fascinating idea. Of course it's easy to notice that one guess or guess-like choice does not necessarily lead to a fully logical solution, and several tries may be needed. What's interesting is to discover that only two such guess-like choices are needed in any puzzle found so far.

I suppose the questions from here out would be along the lines of:

- Which cells are in the best position to provide the most information about the grid? Is it possible to determine this without knowing the solution value for the cell? (A possible corollary question: Which cells are lousing up attempts to use fishy cycles, X-wing/swordfish, subsets?)

- Where are "stopping points" (where standard logical methods fail) likely to occur if cell XY is chosen?

- Is there a particular digit for which choosing the correct cell could break open the remaining clues to the puzzle? If so, what are the characteristics of this digit in the puzzle (i.e., number already placed, candidates locked in pairs/tuples, )?

dukuso · Posted: Mon Sep 19, 2005 3:42 pm Post subject:

gsf wrote:
>dukosu wrote:
>
>>what's the average number
>>of clues in a random minimal sudoku
>>generated by your method ?
>
>
>25.3 starting with 30 randomly placed givens

when I start without givens, I get 23.9
That method is slower (5 times or such ?), but produces about
20 times more 19s . I don't really know, why.

>dukosu wrote:
>
>>I don't understand, what a "magic cell" is.
>>
>>What's a "solution cell" ?
>>Is the (C-) constrained-puzzle produced by the candidate values or by
>>the solution cells and how ?
>
>
>Sorry, I get too close to the bits and become terminology challenged.
>A solution cell is not a given. A puzzle is solved by assigning values
>to all solution cells.

so the 81 cells are partitioned into givens (=clues) and solution cells

>Of the puzzles surveyed, only 0, 1 and 2-constrained puzzles
>were found. "M magic cells" and "M-constrained" are equivalent.
>If you gave me a 1-constrained puzzle I could give you 1 solution
>cell (1 magic cell), and a value to place in that cell, that would
>produce a constrained puzzle (a puzzle solved by logic alone,
>no trial and error.)

I see. But the puzzle would be no longer minimal.
So, when you remove one given from a M-constrained valid puzzle
you get either an invalid puzzle or a M-constrained puzzle
again or a (M-1) constrained puzzle.
You conjecture that there is no 3-constrained 9*9 (number-place-)puzzle.
What's the maximum for 16*16 ?

You can also try this constraint (level 2 FN) : at each step in the
constraint propagation eliminate all candidates whose placement leads
to a 0-FN-puzzle.

Also level 3 FN etc.

Please check the puzzles at
http://magictour.free.fr/subig20
I had 2 or 3 which require level 3. Unlikely though,
since we examined much fewer than 2e8.

>A puzzle generator could use magic cells to produce only
>constrained puzzles. The %s output from my solver produces
>an inline grid of 81 chars, [1-9] for the givens, [A-I] for
>the solution cells (A=1, B=2, ...) and [J-R] for the magic
>cells (J=1, K=2, ...) Changing the 1 or 2 magic cells for
>any unconstrained puzzle to givens produces a constrained puzzle.
>
>If a solver made the right (luckiest) choice of solution cells
>to backtrack on, it would never go more than 1 level deep for
>1-constrained puzzles and 2 levels deep for 2-constrained puzzles.

if a solver always makes the luckiest choice, it would never
backtrack :-)

>Determining the magic cell set for a given puzzle is currently
>done by brute force: solve the puzzle; then assign the solution
>value to each solution cell separately (i.e., try making each
>solution cell a given), and check if the resulting puzzle is
>constrained. My interest lies in doing it with a lighter touch.

can you filter the puzzles by solving time to improve my
top95 list ? I do 100 random permutations of the 324 constraints
and 729 placements and measure the average solving time
with "DLX" using FN only.

-Guenter

gsf · Posted: Mon Sep 19, 2005 4:28 pm Post subject:

>>Of the puzzles surveyed, only 0, 1 and 2-constrained puzzles
>>were found. "M magic cells" and "M-constrained" are equivalent.
>>If you gave me a 1-constrained puzzle I could give you 1 solution
>>cell (1 magic cell), and a value to place in that cell, that would
>>produce a constrained puzzle (a puzzle solved by logic alone,
>>no trial and error.)

dukuso · Posted: Tue Sep 20, 2005 8:06 am Post subject:

>Removing a given from an M-constrained puzzle might produce
>an (M+1)-constrained puzzle, but not an (M-1)-constrained puzzle.

ahh, yes. Sorry.

>Vegard Hanssen checked higher order sudoku and the conjecture held,
>but it was a much smaller survey.

he doesn't create minimal puzzles, AFAIK

>The longest to solve from the 225M survey (not already posted
>on the forum) would be in the minimal FNBTXZ-2-constrained puzzles in
>http://www.research.att.com/~gsf/sudoku/FNBTXZ-2-constrained.dat.gz
>Can you do the timing on those?

I made a new list with all puzzles known to me and uploaded to
http://magictour.free.fr/top94
(sorted by average solution time over 100 randomized initialisations,
hardest first)

top94 takes me 3%-5% longer than top95 with randomized initialization.
Not necessarily those puzzles which require more advanced
techniques also take the most time here. Any puzzle which
can't be solved by FN could be a candidate.

rallveird · Posted: Tue Sep 20, 2005 10:03 pm Post subject:

>>Vegard Hanssen checked higher order sudoku and the conjecture held,
>>but it was a much smaller survey.

>he doesn't create minimal puzzles, AFAIK

Yes, I do. All my optimal sudokus are minimal, and used in this experiment.

gsf · Posted: Wed Sep 21, 2005 3:43 pm Post subject:

I said:

> Its possible that some magic cells only work in groups rather than alone.
> I haven't checked for that situation.

which is wrong -- by definition magic cells work alone.

I also claimed that these 2-constrained puzzles were minimal http://www.research.att.com/~gsf/sudoku/FNBTXZ-2-constrained.dat.gz
but they were not due to a bug that allowed some non-minimal puzzles to slip by.

I reposted minimal mutually non-isomorphic 2-constrained puzzle files at http://www.research.att.com/~gsf/sudoku/FN-2-constrained.dat.gz and http://www.research.att.com/~gsf/sudoku/FNBTXZ-2-constrained.dat.gz

Moschopulus · Posted: Thu Sep 22, 2005 12:49 am Post subject:

So a magic cell is a cell where, if we guess the right digit, the rest of the puzzle follows easily. (If there's only one magic cell) These have been discussed - for example in this post in another thread on another forum:

http://www.sudoku.com/forums/viewtopic.php?t=972&start=36

The author identifies a magic cell in R9C7.

BTW the puzzle in question is a candidate for the "toughest".

I ran your program on this puzzle, typing "sudoku -d -FN filename" and I got

8/23/04/0062/1 BAEH7F94CFGHC9DBA53DIAB5H7FEH74CB1FI463IHAGEBAIBFE7C8D8BFGDCEIA7CDEAIF28I5A26HMCG
N

for output. Am I right in thinking that the M 3rd from last signifies that R9C7 is a magic cell, and that guessing 4 here makes it all work?

Since there is no other letter beyond I, this puzzle is 1-constrained?

Could you explain the output 8/23/04/0062/1 please?
And why is there an N at the end?

Thanks for the program, and web page!

dukuso · Posted: Thu Sep 22, 2005 5:44 am Post subject:

sudokus 1,4,5,7,9,10,11,13,14,15 from
http://magictour.free.fr/su16
are 3-FN-constraint.
I found no 4-FN-constraint 16*16-sudoku so far.

edit: I found one now :

gsf · Posted: Thu Sep 22, 2005 7:03 am Post subject: