On Sat, Mar 14, 2020 at 12:51 PM Bernie Cosell <bernie@fantasyfarm.com> wrote:
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
Sorry, I wasn't very clear.
-- 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.
Yes, that was the idea.
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.
No, I meant the runtime for dancing links to find the unique configuration given the clues. But it seems I was misremembering: this site says that dancing links gets faster on problems humans rate more difficult: https://rafal.io/posts/solving-sudoku-with-dancing-links.html
I'll play with that. thanks! /Bernie\
Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com