I've been pondering Sudoku recently. It is easy [I think] to generate a sudoku grid. But beyond that there are a bunch of questions about turning it into a puzzle that I haven't seen much talked about. Most of the articles I've found fret about numbers, rather than algorithms [minimum number of clues necessary, how many grids are there with the, the maximum number of clues and still have an ambiguous grid, etc] 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? /Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
One of Knuth's YouTube lectures deals with these issues a little. At 07:00 AM 3/14/2020, Bernie Cosell wrote:
I've been pondering Sudoku recently. It is easy [I think] to generate a sudoku grid. But beyond that there are a bunch of questions about turning it into a puzzle that I haven't seen much talked about. Most of the articles I've found fret about numbers, rather than algorithms [minimum number of clues necessary, how many grids are there with the, the maximum number of clues and still have an ambiguous grid, etc]
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?
/Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep
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
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
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 --
Don's code is all on his web site and they compile and run without any problem, and include detailed descriptions of the algorithms. Well worth playing with if you're interested. -tom On Sat, Mar 14, 2020 at 11:51 AM 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 -- 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 --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
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
https://puzzling.stackexchange.com/questions/29/what-are-the-criteria-for-de... On Sat, Mar 14, 2020 at 2:07 PM Mike Stay <metaweta@gmail.com> wrote:
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
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
participants (5)
-
Bernie Cosell -
Henry Baker -
Mike Stay -
Tomas Rokicki -
Victor Miller