Sudoku puzzle generation
-
Just out of lack of anything better to do while learning Python I started to implement a few bits and pieces for the game of Sudoku. The game is played on a 9 by 9 board and according to www.sudoku.com/rule.htm: There is really only one rule: Fill in the grid so that every row, every column, and every 3 x 3 box contains the digits 1 through 9. The "every 3 x 3 box" part is not quite true, but have a look at the site and you'll see what it means. And there is an extra rule, that each puzzle has an unique solution (I can't really see the reason for this one from the solver's point of view, apart for using it in competitions. But it's a nice challenge to implement). So far I've finished a set of tools to generate new boards, display, play, save and restore games and a game-solver is on the way (console mode only, no GUI yet). Everything is pretty rough, the goal was to learn Python, not to get a finished product :-O Where I'm completely stuck is: 1. how to generate a starting position. How many grid cell are initially visible? Are there any other rules except that the starting position has to be symmetrical? 2. how to control the level of difficulty, or at least determine it after the board has been generated? The count of visible cells at the start is not it. 3. how to check if the extra rule, uniqueness of solution, is satisfied (except for the obvious "use back tracking to generate all solutions from a given starting point, then check count == 1") Is anyone aware of any documentation on the subject (my google skills failed me badly on this one), or just interested in the challenge? OGR
-
Just out of lack of anything better to do while learning Python I started to implement a few bits and pieces for the game of Sudoku. The game is played on a 9 by 9 board and according to www.sudoku.com/rule.htm: There is really only one rule: Fill in the grid so that every row, every column, and every 3 x 3 box contains the digits 1 through 9. The "every 3 x 3 box" part is not quite true, but have a look at the site and you'll see what it means. And there is an extra rule, that each puzzle has an unique solution (I can't really see the reason for this one from the solver's point of view, apart for using it in competitions. But it's a nice challenge to implement). So far I've finished a set of tools to generate new boards, display, play, save and restore games and a game-solver is on the way (console mode only, no GUI yet). Everything is pretty rough, the goal was to learn Python, not to get a finished product :-O Where I'm completely stuck is: 1. how to generate a starting position. How many grid cell are initially visible? Are there any other rules except that the starting position has to be symmetrical? 2. how to control the level of difficulty, or at least determine it after the board has been generated? The count of visible cells at the start is not it. 3. how to check if the extra rule, uniqueness of solution, is satisfied (except for the obvious "use back tracking to generate all solutions from a given starting point, then check count == 1") Is anyone aware of any documentation on the subject (my google skills failed me badly on this one), or just interested in the challenge? OGR
One other rule which I have seen stated somewhere is that at every move at least one more cell number can be deduced with certainty from the current configuration. In other words there is never any need to use guesswork, or trial and error. (When implemented I guess this would guarantee that the solution for any start grid is unique) Steve T
-
Just out of lack of anything better to do while learning Python I started to implement a few bits and pieces for the game of Sudoku. The game is played on a 9 by 9 board and according to www.sudoku.com/rule.htm: There is really only one rule: Fill in the grid so that every row, every column, and every 3 x 3 box contains the digits 1 through 9. The "every 3 x 3 box" part is not quite true, but have a look at the site and you'll see what it means. And there is an extra rule, that each puzzle has an unique solution (I can't really see the reason for this one from the solver's point of view, apart for using it in competitions. But it's a nice challenge to implement). So far I've finished a set of tools to generate new boards, display, play, save and restore games and a game-solver is on the way (console mode only, no GUI yet). Everything is pretty rough, the goal was to learn Python, not to get a finished product :-O Where I'm completely stuck is: 1. how to generate a starting position. How many grid cell are initially visible? Are there any other rules except that the starting position has to be symmetrical? 2. how to control the level of difficulty, or at least determine it after the board has been generated? The count of visible cells at the start is not it. 3. how to check if the extra rule, uniqueness of solution, is satisfied (except for the obvious "use back tracking to generate all solutions from a given starting point, then check count == 1") Is anyone aware of any documentation on the subject (my google skills failed me badly on this one), or just interested in the challenge? OGR
A feature that would be nice on a Sudoku-playing app would be a way to mark two or more cells as candidates (or non-candidates) for a particular number with, say, greyed-out numbers (or different background color), to help with further elimination/deduction. I do that on paper and it really helps me but none of the Sudoku-playing apps I've found allow that. Steve T
-
A feature that would be nice on a Sudoku-playing app would be a way to mark two or more cells as candidates (or non-candidates) for a particular number with, say, greyed-out numbers (or different background color), to help with further elimination/deduction. I do that on paper and it really helps me but none of the Sudoku-playing apps I've found allow that. Steve T
thanks for your help I'll certainly try to do something like 'lock cell' later, then you could just lock the cells you're confident with. I would have to figure out some sort of GUI feedback for it as well But doesn't this request contradict your previous reply, when you suggested that at least one more position can be determined at each point? Anyway, this doesn't really help me much, so far I was trying to apply a 'visibility template' to a previously determined full board. It is also possible to have started completely wrong. Maybe instead of randomly generating a full board using a back tracking algorithm I should do something like: 1. pick a 'visibility template' (can anyone suggest a better name?) 2. generate a partial random solution for it 3. try to solve the game in a deterministic fashion 4. re-start from point 1. if no solution can be found That would still leave the difficulty level question open though OGR
-
thanks for your help I'll certainly try to do something like 'lock cell' later, then you could just lock the cells you're confident with. I would have to figure out some sort of GUI feedback for it as well But doesn't this request contradict your previous reply, when you suggested that at least one more position can be determined at each point? Anyway, this doesn't really help me much, so far I was trying to apply a 'visibility template' to a previously determined full board. It is also possible to have started completely wrong. Maybe instead of randomly generating a full board using a back tracking algorithm I should do something like: 1. pick a 'visibility template' (can anyone suggest a better name?) 2. generate a partial random solution for it 3. try to solve the game in a deterministic fashion 4. re-start from point 1. if no solution can be found That would still leave the difficulty level question open though OGR
I must admit the remaining problem you have--deciding which visible cells to use in the start grid--is the one thing that has had me stumped in Sudoku puzzle generation. As for : ogrig wrote: But doesn't this request contradict your previous reply, when you suggested that at least one more position can be determined at each point? No. You can often determine that a particular number (x) must appear in either of two adjacent--or aligned--candidate cells and thereby iliminate that number from the remainder of a row or column. Then using that information you can sometimes determine another number's position in that row or column. It may be a few moves later before you can determine which of the two candidate cells in that row gets number 'x'. There is no guesswork involved. In this solving technique you must know for sure that x appears in one of the two aligned candidate cells (and hence in that row or column) and you do not need to guess which one. Steve T
-
Just out of lack of anything better to do while learning Python I started to implement a few bits and pieces for the game of Sudoku. The game is played on a 9 by 9 board and according to www.sudoku.com/rule.htm: There is really only one rule: Fill in the grid so that every row, every column, and every 3 x 3 box contains the digits 1 through 9. The "every 3 x 3 box" part is not quite true, but have a look at the site and you'll see what it means. And there is an extra rule, that each puzzle has an unique solution (I can't really see the reason for this one from the solver's point of view, apart for using it in competitions. But it's a nice challenge to implement). So far I've finished a set of tools to generate new boards, display, play, save and restore games and a game-solver is on the way (console mode only, no GUI yet). Everything is pretty rough, the goal was to learn Python, not to get a finished product :-O Where I'm completely stuck is: 1. how to generate a starting position. How many grid cell are initially visible? Are there any other rules except that the starting position has to be symmetrical? 2. how to control the level of difficulty, or at least determine it after the board has been generated? The count of visible cells at the start is not it. 3. how to check if the extra rule, uniqueness of solution, is satisfied (except for the obvious "use back tracking to generate all solutions from a given starting point, then check count == 1") Is anyone aware of any documentation on the subject (my google skills failed me badly on this one), or just interested in the challenge? OGR
I found some posts on a VB forum about puzzle generation. One post seemed to have what you need ... ...Now you have your legal grid, you have to decide how difficult to make the puzzle. First of all, to make the solution unique, you HAVE to reveal at least one number in each of 8 rows and 8 columns (in theory you could get away with fewer, depending on the construction of the miniblocks) That, however, would probably be a very difficult puzzle to solve. If you want to make it easier, make sure that the number of possible selections for at least one of the blank slots is limited to two numbers... Thread here[^] Steve T
-
I must admit the remaining problem you have--deciding which visible cells to use in the start grid--is the one thing that has had me stumped in Sudoku puzzle generation. As for : ogrig wrote: But doesn't this request contradict your previous reply, when you suggested that at least one more position can be determined at each point? No. You can often determine that a particular number (x) must appear in either of two adjacent--or aligned--candidate cells and thereby iliminate that number from the remainder of a row or column. Then using that information you can sometimes determine another number's position in that row or column. It may be a few moves later before you can determine which of the two candidate cells in that row gets number 'x'. There is no guesswork involved. In this solving technique you must know for sure that x appears in one of the two aligned candidate cells (and hence in that row or column) and you do not need to guess which one. Steve T
looks like it's just a scribble so you don't have to remember a partial result. if I ever get to write a full version I'll certainly put in various hints and cheats. no problem with that, my initial Excel spreadsheet helper had much worse things, like lists of values valid on rows and columns :-) Since yesterday I had a few more ideas about how to generate a starting position. My problem was that I started the thing as a learning exercise (read: zero analysis and planning :-) ) so it was easy to underestimate the problem. In fact I'm generating a random new solution anyway, I only have to find a suitable starting position for it. This is just a similar problem on a smaller scale: generate a random symmetrical pattern on a square board. Add in a few constraints, like the minimum and maximum number of visible cells and maximum number of visible cells of the same value, and then verify it's solvable. I think that if you keep the board deterministic the solution is automatically unique (this should be easy to prove). Which means the problem of finding a starting position is solved by implementing the solver, that was planned anyway. OGR
-
I found some posts on a VB forum about puzzle generation. One post seemed to have what you need ... ...Now you have your legal grid, you have to decide how difficult to make the puzzle. First of all, to make the solution unique, you HAVE to reveal at least one number in each of 8 rows and 8 columns (in theory you could get away with fewer, depending on the construction of the miniblocks) That, however, would probably be a very difficult puzzle to solve. If you want to make it easier, make sure that the number of possible selections for at least one of the blank slots is limited to two numbers... Thread here[^] Steve T