hard Sudoku's

Hi!
I am the author of the other Sudoku class in phpClasses.org :-)
I found that your program has a nice addition to mine, because it can generate Sudoku's, while mine cannot. Mine has a real user interface though, where you can easily enter Sudoku's you found in a newspaper etc. and have them solved.

Although your solver looks as if it is much better written, mine can solve more Sudoku's. I think your assumption that you can solve all sudoku's with either a positive or a negative uniqueness rule is not true. I will paste an example below. For example, if there are two possibilities in a column for a certain number (whithin the same square), you can make the negative assumption that this number cannot appear elsewhere in that square.
I found Sudoku's on the web that have a unique solution, but where the only way to solve them is by trial and error.

I made a link with your generator, probably I will post it sometime later.

1 7 7
1 9 9
2 1 3
2 6 9
2 8 4
3 6 7
3 7 3
3 8 8
4 4 9
4 6 3
4 7 6
4 8 5
5 2 6
5 3 3
5 4 7
5 6 1
5 7 2
5 8 9
6 2 7
6 3 5
6 4 4
6 6 2
7 2 3
7 3 9
7 4 1
8 2 1
8 4 2
8 9 5
9 1 5
9 3 6

Cheers!

Well it's my understanding that Sudoku's are required to have single solutions and that you "never guess" during the solution process. On the surface of it, any set of clues that lead you to a position in which you can't infer the proper value for the next step is a violation of the "rules". Now clearly I haven't seen bunches of Sudoku, but from what I've read the "never guess" rule appears to be generally accept. Trial and error is just a fancy name for guessing so any set of clues that requires you to guess the solution certainly looses my interest. Clearly [I think] you can continue to make progress mechanically in this situation by stuffing values into the most constrained portions of the solution available at the time you have to "guess" and keep going until you get to "the" solution and, if necessary, I'll write code to do that, but it strikes me as pretty unfair of the author.

Which, I guess, is me whining about something that I wouldn't want to run into myself. BTW, every Sudoku I've seen published has been solvable using these techniques, even the most difficult "black belt" ones. I'll definately take a look at the one you posted and see what happens.

Thanks for the pointer. I've put up a "Daily Sudoku" website using the class just for fun. A few visitors thus far. Maybe if I can get a handle on generation of really difficult Sudoku (that don't require guessing) I'll pull more visitors.

As an observation, the number of clues necessary to solve a Sudoku appears to be on the order of 27 give or take a few. Is there any mathematics on the minimum number required to solve a Sudoku? I haven't seen much on the net.

I agree with you about the guessing part. But maybe there are rules for some of them that I could not figure out yet.
Try this one:

1 1 8
1 3 1
1 7 5
2 1 2
2 6 9
2 8 4
3 1 5
3 2 3
4 4 2
4 5 9
5 3 4
5 7 1
6 5 4
6 6 1
7 8 9
7 9 2
8 2 5
8 4 7
8 9 8
9 3 8
9 7 4
9 9 3

(I have it from an Italian Sudoku book)

If you solve it with:

$p = new Sudoku() ;
$p->initializePuzzleFromFile("diavolo1.txt") ;
$p->solve() ;
$p->printSolution() ;

You will see in row 2, cols 2 and 3, twice the pairs 6,7. This means that 6 and 7 cannot occur elsewhere in row 2, and you can take out the 6 and 7 in col 9, which leaves a unique 1. With this given you can now solve the puzzle using the old rules.

So, this is an example that can be solved without guessing, but which requires more complicated rules than the ones you implemented. (I implemented this pair rule, and therefore my solver can solve this one. Maybe there is a rule for the other one I sent you, but I could not find it).

Here is a pointer to a free Sudoku generator:
opensky.ca/~jdhildeb/software/sudok ...
This site leads you to another site,
sourceforge.net/projects/gnome-sudo ...
which has a Sudoku generator in Python, for which I unfortunately have no facilities to run it.

Cheers!

Interesting about the pairs rule. I use that all the time in solving
Sudoku but every time I've ever seen the situation arise in practice, it
serves to get me to a simplification of the "unique" rule I use. Thus I
(apparently incorrectly) assumed that the pairs rule was a special case of
the unique rule that was easier for me to use in my own head.

I just implemented a brute force guesser that solves the Sudoku in your
first message in this thread. There's your data and and example of use in
the new source on phpclasses.org. Of course the problem with brute force
is that you have no guarantee that there IS a solution once the deduction
fails and finding out that there isn't a solution can potentially take a
while. Getting to the solution to your first problem required about 6 or
so guesses at only a pair of cells in order to generate the solution. I
suspect that this will generally be the case for clue sets that are
"close".

FWIW, I think that the pair rule also generalizes to a triple (at least
within a row or column embedded within a square) which I've seen from time
to time working things out. Again, in practice I've only seen the triples
rule as shortcut to the unique rule.

Tomorrow for your next problem. I've got to get some work done.

Dick

I think your pairs rule is a special case of a more general "n-tuple"
rule, i.e., given n cells constrained to n values and m open cells, then
the values possible in the disjoint set of n and m cells cannot contain
the values possible within the n cells. Which is what I've implemented.
It solves the Sudoku from your last post and continues to generate Sudoku
(although it's a little hard to tell when it's making a "pair" inference,
I'll have to work on that).

I suspect that the trick to generating "hard" Sudoku is seeding the
solution space with "pair" inferences. I haven't had any thoughts on how
to actually DO that, so any suggestions would be appreciated.

Thanks again for your contributions.

Dick Munroe

I checked out http://www.opensky.ca/~jdhildeb/software/sudokugen/ to get
a few Sudoku from another generator. Out of the 4 " very hard" none had
a solution given the clues provided. They could only be solved using
brute force. Which means that either I don't understand the deep
structure of Sudoku (easily true) or that I'm missing something in the
inference engine I'm using.

Now if I could only figure out what...

Dick

While solving a few Sudoku, I spotted another inference that can be taken. Here's an example:

Given that the following tuples could appear in cells within a row/column/square:

(2, 5)
(5, 8)
(2, 5, 8)

then no other cell in that row/column/square may contain those values.

The proof is straightforward.

1. Assume that any value (2, 5, 8) could appear elsewhere in the row/square/colum, e.g., 2.

2. After substitutition, you find that two cells must take on the value 5, a violation of the rules.

3. Repeat for all other values and you find that you always have a violation of the rules.

4. Therefore this pattern excludes these values from the other cells.

Now, implementing this may be tricky, but it will certainly add additional "muscle" to solving algorithms.

As with the straightfoward tuple rule, I think that this generalizes to any collection of cells of size n and n-1.

Dick Munroe

Were are other classes for generation sudoku on PHP?
Who knows?
Sorry of my english.