
View previous topic :: View next topic 
Author 
Message 
 gsf
 Joined: 18 Aug 2005  Posts: 411  :  Location: NJ USA  Items 

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:
F (forced cell) only one value possible.
N (only cell) only one value in row/col/box.
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 Mconstrained.
A survey of ~225M puzzles produced the following counts:
153476504 constrained
071536584 1constrained
000066500 2constrained
Adding box claims, naked and hidden tuples, weak cycles (generic
xwing/swordfish) and strong cycles (fishy?) to the constraint set
produced:
187757998 constrained
037317899 1constrained
000003692 2constrained
No 3constrained or greater puzzle was found for either constraint set.
It was a surprise that the 2constrained puzzles were so rare and that
no 3constrained 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. 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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) constrainedpuzzle produced by the candidate values or by
the solution cells and how ?
Guenter 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 411  :  Location: NJ USA  Items 

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


dukuso wrote:  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 
Rats, I eliminated equivalence class dups from the generated data but not from the puzzles scraped from the forum. There were a bunch of cross refs to the 17 givens puzzles. Correct data reposted.
thanks
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
dukosu wrote: 
I don't understand, what a "magic cell" is.
What's a "solution cell" ?
Is the (C) constrainedpuzzle 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.
Of the puzzles surveyed, only 0, 1 and 2constrained puzzles were found. "M magic cells" and "Mconstrained" are equivalent. If you gave me a 1constrained 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.)
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, [19] for the givens, [AI] for the solution cells (A=1, B=2, ...) and [JR] 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 1constrained puzzles and 2 levels deep for 2constrained puzzles.
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. 

Back to top 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

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 guesslike 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 guesslike 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, Xwing/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, )? 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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) constrainedpuzzle 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 2constrained puzzles
>were found. "M magic cells" and "Mconstrained" are equivalent.
>If you gave me a 1constrained 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 Mconstrained valid puzzle
you get either an invalid puzzle or a Mconstrained puzzle
again or a (M1) constrained puzzle.
You conjecture that there is no 3constrained 9*9 (numberplace)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 0FNpuzzle.
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, [19] for the givens, [AI] for
>the solution cells (A=1, B=2, ...) and [JR] 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
>1constrained puzzles and 2 levels deep for 2constrained 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 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 411  :  Location: NJ USA  Items 

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


>>Of the puzzles surveyed, only 0, 1 and 2constrained puzzles
>>were found. "M magic cells" and "Mconstrained" are equivalent.
>>If you gave me a 1constrained 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.)
dukosu wrote: 
I see. But the puzzle would be no longer minimal.
So, when you remove one given from a Mconstrained valid puzzle
you get either an invalid puzzle or a Mconstrained puzzle
again or a (M1) constrained puzzle.
You conjecture that there is no 3constrained 9*9 (numberplace)puzzle.
What's the maximum for 16*16 ?

Removing a given from an Mconstrained puzzle might produce an (M+1)constrained puzzle, but not an (M1)constrained puzzle.
Adding a magic cell to a minimal Mconstrained puzzle might make it an (M1)constrained puzzle. (Its possible that some magic cells only work in groups rather than alone  I haven't checked for that situation.) If removing one did produce an (M1)constrained puzzle then it might be possible to remove givens from the (M1)constrained puzzle to produce a minimal (M1)constrained puzzle.
Vegard Hanssen checked higher order sudoku and the conjecture held, but it was a much smaller survey.
These were included in the scraped puzzles.
>If a solver made the right (luckiest) choice of solution cells
>to backtrack on, it would never go more than 1 level deep for
>1constrained puzzles and 2 levels deep for 2constrained puzzles.
Quote:  if a solver always makes the luckiest choice, it would never
backtrack

right, "magic cells" gives a name to those lucky choices
Quote:  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. 
The longest to solve from the 225M survey (not already posted on the forum) would be in the minimal FNBTXZ2constrained puzzles in http://www.research.att.com/~gsf/sudoku/FNBTXZ2constrained.dat.gz
Can you do the timing on those? 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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


>Removing a given from an Mconstrained puzzle might produce
>an (M+1)constrained puzzle, but not an (M1)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 FNBTXZ2constrained puzzles in
>http://www.research.att.com/~gsf/sudoku/FNBTXZ2constrained.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. 

Back to top 


 rallveird
 Joined: 13 Jun 2005  Posts: 31  :   Items 

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. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 411  :  Location: NJ USA  Items 


Back to top 


 Moschopulus
 Joined: 12 Aug 2005  Posts: 39  :   Items 

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 1constrained?
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! 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

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 3FNconstraint.
I found no 4FNconstraint 16*16sudoku so far.
edit: I found one now :
Code: 
...........9.F..
.A..2..7.....C.6
.C.B.F9.6..2D8..
.52D3.4.E...9..7
....47......1.6.
F9..B.A5.6.G....
GE53...2A.9.B...
...2.G.......3..
....1B.DC.25....
E..G.....48A....
...7G.2.F......8
.......CD..1..3E
.B.8......F....C
.....CE.8...46.B
1.C...F..9...G82
..GF7....D...5A.



Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 411  :  Location: NJ USA  Items 

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


Moschopulus wrote:  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

thanks for the pointer
Moschopulus wrote: 
The author identifies a magic cell in R9C7.
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 1constrained?
Could you explain the output 8/23/04/0062/1 please?
And why is there an N at the end?

correct about M==4 for the magic cell position and value
FN is a typo but not a syntax error
you meant to type qFN to limit the constraints to F (forced cell) and N (only cell in row/col/box)
the man option prints the man page on stderr, including a description of the default output (%S%,%s) under the f perpuzzle format option  there's also a link to the man page on the web site
(this is in the man page) 8/23/04/0062/1 means rating 8 (1: easy to 7: hard, 8: 1 magic cell, 9: 2 magic cells), 23 givens (clues), 4 guesses, 62 constraint iterations, 1 magic cell
F is a final format before program exit, in your case "N"
so the default constraints were in effect and only one magic cell was found
you can print the magic cell [r,c] with the %m format; try
Code:  sudoku d qFN f%m ... 
and it should print the 2 magic cells [9,1][4,6]
if you drop qFN then all constraints will be enabled and in that case there is only 1 magic cell [9,7] 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
