
View previous topic :: View next topic 
Author 
Message 
 ChPicard
 Joined: 12 Mar 2008  Posts: 82  :  Location: Montreal, Canada  Items 

Posted: Fri Mar 27, 2009 5:47 pm Post subject: Checker and the Minimum Number of Clues Problem 


Hi everybody
At:
http://math.ie/checker.html
we can read:
Quote:  Thus one may consider checker as answering the question "does this grid have a puzzle with n clues?" In a sense, checker answers yes or no. 
Can checker answer this question?
Does a grid have a puzzle with 16 clues?
What is the strategy to find the good grid among the 5472730538 essentially different grids?
What is the chance to find a solution?
ChPicard 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Tue Mar 31, 2009 6:39 am Post subject: 


Unfortunately, I don't believe checker is able to authoritatively answer your question.
The man who's writing up about checker there, is not the author of checker, and shows no tests of checker, that it is 100% accurate.
The best way to test it, in my opinion, is to generate all the isomorphically unique grids, and then run them through one or two fast solvers that have tested accurate.
We have the fast solvers, and we have at least two programmers that can generate all the unique grids for say, 16 givens. Problem is, they're focused on the 17's, and what they're working on for the 16's is unclear to me.
From what I've read, it's rather hit or miss as far as a systematic search of the 16's search space, is concerned. 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Tue Mar 31, 2009 7:13 pm Post subject: 


Greetings.
I believe checker is 100 % accurate.
If you understand the pretext on which it works, it can completly check a grid for ,16,17,18........
However depending on the "structure of the solution grid" the length of time that this takes is variable.
Certain characteristicts of the unavoidable sets in a specific solution grid dictate whether its fast or not.
To exclude a 17 in some grids takes a few days, and is some grids takes a few hours.
Ths SF grid has been checked  there were 29 17puzzles, all sharing a 14clue base.
http://www.sudoku.com/boards/viewtopic.php?t=4754&highlight=
No other 17 has been found subsequently in another "region" in this grid  with wildly different clues has been found  nor will be found.
the characteristics of the grid are defined by the mcn.
this is the largest group of unavoidable sets [all disjoint  ie no similar clues] this means that at least one clue from each of these sets has to be in any minimal puzzle from this grid [period].
The easiest grid to study is this one  with an MCN of 14. Which i did some time ago.
Such a large MCN should tend to preclude a 17...but by quirk it doesnt.
Heres the 17puzzle and the 14 disjoint unavoidable sets
Code:  ++++
.....6.5.
.7....2..
..81.....
++++
3...54...
......8.1
......7..
++++
54.....6.
....2....
...8.....
++++ 
Code: 
++++
439286157
176593284
258147396
++++
381754629
795632841
624918735
++++
542371968
867429513
913865472
++++
439286157176593284258147396381754629795632841624918735542371968867429513913865472 
with clues {16,18,22,27,33,34,41,45,46,57,59,67,71,72,78,85,94} [The numbers 16=r1c6]
from unavoid
Code: 
Found 239 unavoidable sets (24 of size 4 or 6).
The maximum # of disjoint unavoidable sets (max clique number  MCN) is 14.
One such maximal collection is:
{16,19,36,39} 1.......16
{17,18,87,88} 1.......18
{22,23,82,83} 1.......22
{27,29,97,99} 1.......27
{46,48,56,58} 1.......46
{62,63,72,73} 1.......72
{75,78,95,98} 1.......78
{11,14,31,35,84,85} 1.......85
{13,15,25,28,33,38} 1.......33
{42,49,52,57,77,79} 1.......57
{43,45,53,59,65,69} 2.......45&59
{44,47,51,54,61,67} 1.......67
{64,66,81,86,91,94} 1.......94
{21,24,32,34,71,76,92,96} 2.......34&71
41 not used in this disjoint collection 
Here is U4 {16,19,36,39}
Code:  ++++
.....6..7
.........
.....7..6
++++
.........
.........
.........
++++
.........
.........
.........
++++ 
All these unavoidable sets are there...please confirm this for yourself !
that at least one clue from each of these sets has to be in any valid minimal puzzle from this grid is an absolute necessity.
Checking for a 16 is quicker...but we couldnt check them all in our lifetime.
Comments welcome.
C 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Wed Apr 01, 2009 4:49 am Post subject: 


So using checker is a moot point in this context.
Your unavoidable sets are quite interesting. Perhaps they could be used to help filter out pseudo grids with 16 givens, before a final test for a unique solution, is made.
BT's solver is very fast though, so I'm not sure of that.
I believe the fact remains that to get enough computer power to test the 16 given grids comprehensively, for a valid Sudoku puzzle, it will require a distributed computing project. 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Wed Apr 01, 2009 11:00 am Post subject: 


Using checker to check all grids  the moot point is that it would take too long.
Regarding the possible 16clue possibilities
Even for one single grid its a big ask. 81! / [65! * 16!] ~ 3* 10^16
Althought this can be reduced by 9! * 6^8 * 2 = 27558
which is a managable number
except there will be 5*10^9 grids
although if the average 16puzzle has maybe 4 million solutions
double counting will, be a prominent feature
Having said that all combinations of 16 clues from a subgrid with > 1 solution will not yield a single valid puzzle [ with n clues  no valid puzzle]
And all combinations of clues from an invalid template with not yield a single valid puzzle.
And all combinations of clues that doesnt have 8 clue values will not yield a single valid puzzle.
Even with these reductions there are still many many combinations to check.....
or is there
Red Ed on the players forum is attacking the problem directly with a cooperative venture.
http://www.sudoku.com/boards/viewtopic.php?t=6636&sid=6a6f50f35ed08135b23e6e84b0bd9a5c
C 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Wed Apr 01, 2009 12:03 pm Post subject: 


Thanks, it's about time!
I'm in like a porch climber. 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Wed Apr 01, 2009 1:14 pm Post subject: 


myself wrote:  Even for one single grid its a big ask. 81! / [65! * 16!] ~ 3* 10^16
Althought this can be reduced by 9! * 6^8 * 2 = 27558
which is a managable number 
this is of course wrong
i dont know the extent of the isomorphic reduction...but it cant be as huge as I suggested. I doubt if its 1%.
We await Red Ed's method !
Edit......1st Aprill 2009......which rather amusingly is a send up.
C 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Wed Apr 01, 2009 11:55 pm Post subject: 


Posting an April Fool's Joke on the last day of March = Evil!
Clever, but evil! 

Back to top 


 lkSudoku
 Joined: 16 May 2009  Posts: 60  :   Items 

Posted: Mon May 18, 2009 8:51 pm Post subject: 


The checker, as least as seems, only answer whether a given board can have some number of exposed cells and a single solution
The question if there can be some board of 16 givens cannot be answered by the checker, unless you happen to give it a complete board that has 16 givens solution. It can only tell the answer for one given board
I think the best way to answer if there is a board with 16 given numbers is using some mathematical reasoning. If there is no such board, then the number of puzzles to test until exhausting all boards is so large that it probably cannot be computed no matter how strong your computing power is in current terms 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Tue May 19, 2009 1:05 pm Post subject: 


Yes, checker only does what you say !
I should add that its fairly difficult to get even an 19 or an 18puzzle from a random grid. At least it is very unlikely by random means. However to come up with a puzzle / and to prove catagorically that there isnt a puzzle with x clues in any one grid is no mean feat. It also proves in some ways that these puzzles are indeed no more than an exercise in set cover theory.
But you may not have seen this Proof of Minimum Clue >= 17
There is no reason why it should be 16, but as yet there is no reason why it cant be 16  although almost certainly wont be 16.
Too many unavoidable sets might be one reason though.
C 

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
