I fiddled with Sudoku's using SAT solvers a few years ago. What surprised me, was how many (including some "fiendish" ones) were solved in the preprocessor. This involved iterating over all the boolean variables, trying true or false (no branching involved) and seeing this gave a logical contradiction. If it did, you could safely set it to the opposite value. There are 729 boolean variables. However, this, and things like dancing links are not very good measures of how hard it is for humans. What I think is that human algorithms have a very limited amount of memory allowed (say 10 bits). I'm not aware of anything done on evaluating difficulty with limited memory. Victor Miller On Sat, Mar 14, 2020 at 1:23 PM Mike Stay <metaweta@gmail.com> wrote:
On Sat, Mar 14, 2020 at 8:01 AM Bernie Cosell <bernie@fantasyfarm.com> wrote:
I'm wondering about such things like: after you generate a grid, how do you figure out which cells to give as clues, recalling that the clues should be optimal for that grid [that is, yield a unique solution and have the solution not be unique if any clue is removed]? How do they determine the "difficulty" of a puzzle?
One way is to remove numbers and then solve the puzzle using dancing links to find all solutions. Backtrack if there's more than one solution. The difficulty is the runtime. http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun