Thread: 25x25 sudoku

Originally Posted by iMalc

I don't know why you're saying that. I'll define "branching factor" to mean how many numbers have not yet been eliminated for the cell with the lowest number of non-eliminated values.

consider

Code:

|  |  |  ||  |  |  ||* |* |  |
|* |  |  ||* |  |  ||  |  |  |
|  |* |  ||  |* |  ||  |  |  |
==============================
|* |  |  ||* |  |  ||  |  |  |
|  |* |  ||  |* |  ||  |  |  |
|  |  |  ||  |  |  ||* |* |  |
==============================
|  |  |* ||  |  |* ||  |  |  | 
|  |  |* ||  |  |  ||  |  |* | 
|  |  |  ||  |  |* ||  |  |* |

where an * represents a box with exactly 2 possibilities, this puzzle would have two solutions (I think that's kinda what he meant by branching)

Guess that won't hold for harder puzzles (and I don't know what XY-wing is, I think I should look into it).

Here's an example of XY-wing in practice. Two must be in either tip of the "wings", as otherwise nothing could go in the square with 5 and 7. Therefore, at the intersection of these squares there cannot be a 2 and we know it is a six. From there on it is quite straightforward. (I find it impossible, though, to discover XY-wing without marking the candidates.)

(The bonus factor here is how the eliminations of 4's in the middle right block has revealed the pattern. )

Unfortunately, at this point the puzzle could be simply solved by guessing. Pick some of the two-candidate squares, make a choice and see whether it leads to a solution. If not, undo the moves and try the other.

I don't think brute-force solvers are interested in such techniques, and I'm afraid 9 * 9 is too deeply hard-coded in the logical solver of this program to see how well it would do with larger puzzles.

I should revive my Haskell sudoku solver as well one of these days. It was pretty smart, being able to apply the "4 elimination" technique anon aluded to (but not the XY-wing technique, first time I hear of this), but was otherwise too complex and slow.

I'm curious how your brute force approach eliminates numbers. Does it plug a value in, then run through all the possible numbers for the other cells, checking each time?

The code for my 9 by 9 solver is on my website under Useful Classes.

Basically it checks for an invalid board, if not invalid then it copies the board, plugs in a number from one of the remaining possibilities in the cell with the least remaining probabilities, eliminates any now impossible values from any row, col or square and recurses, iirc.

Heh. Well, my implementation so far can only solve simple 9x9 fields. I need to implement more solution strategies.

Originally Posted by cyberfish

Code:

Node count: 668

real	0m0.022s
user	0m0.012s
sys	0m0.004s

(for the "difficult" 16x16 puzzle).

That's pretty good!
Mine solved the 16x16 one in 123 milliseconds on my ageing PC. Clearly still room for more optimisation.