Checker and the Minimum Number of Clues Problem

ChPicard

Hi everybody

At:

http://math.ie/checker.html

we can read:

Adak · 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.

coloin · 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 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

Adak · 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. 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.

coloin · 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 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

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

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

Thanks, it's about time! Smile

I'm in like a porch climber.

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

Adak · 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!

lkSudoku · 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

coloin · 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 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