The New Sudoku Players' Forum

[codelieb]

I have devised a method for solving sudoku puzzles which is very unlike others I have seen or heard of. My sudoku-solving algorithm, PSS, does not use any form of logical deduction or trial and error. A puzzle is represented as a point somewhere inside the unit hypercube of 729 dimensions - each dimension corresponding to the probability of a digit in some cell. The probabilities are initialized according to the clues of a given puzzle, then a simple iterative calculation is made that incrementally modifies the probabilities, gently displacing the point in the hypercube, until each probability becomes either 1 or 0, at which point it is locked. When all the probabilities have been locked, a solution has been found. Thus the puzzle state is moved along a stepwise continuous path from its initial state inside the hypercube to its final state in one of the corners. However, this is a "greedy" algorithm, not guaranteed to succeed in all cases. I have implemented PSS in Mathematica and 'C' and tested it on over 1200 puzzles. It succeeds in solving all but ~2.5% of randomly generated single-solution puzzles. So far I have not found any puzzle intended for human recreation that the algorithm fails to solve, even those considered "expert." Of 1106 so-called "unsolvable" puzzles I tested (generously donated by sudoku.ork.uk), PSS solves 573 - about 52%. A more detailed description of the algorithm, plus complete source code and executables, can be found at http://www.feynmanlectures.info/sudoku/pss.html.