Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Checker and the Minimum Number of Clues Problem

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Fri Mar 27, 2009 5:47 pm    Post subject: Checker and the Minimum Number of Clues Problem Reply with quote

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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Tue Mar 31, 2009 6:39 am    Post subject: Reply with quote

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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Tue Mar 31, 2009 7:13 pm    Post subject: Reply with quote

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 17-puzzles, all sharing a 14-clue 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 17-puzzle and the 14 disjoint unavoidable sets
Code:
+---+---+---+
|...|..6|.5.|
|.7.|...|2..|
|..8|1..|...|
+---+---+---+
|3..|.54|...|
|...|...|8.1|
|...|...|7..|
+---+---+---+
|54.|...|.6.|
|...|.2.|...|
|...|8..|...|
+---+---+---+

Code:

+---+---+---+
|439|286|157|
|176|593|284|
|258|147|396|
+---+---+---+
|381|754|629|
|795|632|841|
|624|918|735|
+---+---+---+
|542|371|968|
|867|429|513|
|913|865|472|
+---+---+---+

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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Apr 01, 2009 4:49 am    Post subject: Reply with quote

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. Wink


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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Wed Apr 01, 2009 11:00 am    Post subject: Reply with quote

Using checker to check all grids - the moot point is that it would take too long.

Regarding the possible 16-clue 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 16-puzzle 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 Idea Question

Red Ed on the players forum is attacking the problem directly with a co-operative venture.

http://www.sudoku.com/boards/viewtopic.php?t=6636&sid=6a6f50f35ed08135b23e6e84b0bd9a5c

C
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Apr 01, 2009 12:03 pm    Post subject: Reply with quote

Thanks, it's about time! Smile

I'm in like a porch climber.
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Wed Apr 01, 2009 1:14 pm    Post subject: Reply with quote

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. Laughing

C
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Apr 01, 2009 11:55 pm    Post subject: Reply with quote

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

Clever, but evil!
Back to top
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Mon May 18, 2009 8:51 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Tue May 19, 2009 1:05 pm    Post subject: Reply with quote

Yes, checker only does what you say !

I should add that its fairly difficult to get even an 19 or an 18-puzzle 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 Exclamation 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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron