Sudoku solver
Dave Angel
davea at davea.name
Thu Mar 26 11:03:16 EDT 2015
On 03/26/2015 10:41 AM, Chris Angelico wrote:
that's already been proven. So, that's why I would avoid guessing.
>
> I've written a lot of solvers for various puzzles. Minesweeper,
> Sudoku, a binary Sudoku-like puzzle that I don't really have a good
> name for, several others. Every time, I've tried to prove the puzzles
> solvable by humans, and sometimes that means rejecting ones that could
> technically be solved by brute force.
OK, we're on the same page. I would use different terminology for some
of it, but that's okay.
The purist in me would like to write a solver which (within a few
seconds) could solve any unique puzzle, and identify puzzles which don't
have a unique solution. One reason I never got back to writing one was
I also wanted a difficulty-ranker, which would identify how hard a human
was likely to consider the puzzle.
Had I been writing it in Python, I'd probably have pursued adding brute
force, and then used some of the code to write a puzzle-generator. But
even then, the problem of ranking was one that had me buffaloed. It's
clearly not enough to count the starting clues
(eg. easyness = (clues - 17) * pi )
And writing an efficient program that generates a non-trivial puzzle
would seem to be quite hard. I've heard it said that Sudoku puzzles
generated by machines are much less satisfying than those generated by a
human.
When in a playful mood, I wonder if all the Sudoku puzzles out there are
just permutations of a few hundred written by Will Shortz. Swap around
rows, columns, boxes, and cryptogram the digit mapping. Voila, a new
puzzle. <g> i read a short story about the purpose of jokes, in which
it said there were only a few hundred of them, the rest were just minor
variants, and that they were an experiment being run on human beings.
And once we realized it, they'd shut off our sense of humor.
--
DaveA
More information about the Python-list
mailing list