On 14 Mar 2020 at 11:18, Mike Stay 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
I think I understand what you're saying -- I have Knuth's Dancing Links lectures but haven't had a chance to view them [they're an hour each]. But: you start with generating a sudoku grid. and then start removing numbers as long as the dancing-links machinery says that the puzzle is still unique, then when it finds multiple solutions you back out. I guess you can stop when you want. You could let it run until it finds the minimal clue-set. Dunno about how that maps into difficulty. I guess you're saying that the runtime to figure out that the clues you've got give a unique solution gives you a metric on how hard it'd be to *find* that solution. I'll play with that. thanks! /Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --