FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Need help with my first Sudoku generator Goto page Previous  1, 2, 3  Next          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Sat Aug 30, 2008 5:34 pm    Post subject: m_b_metcalf wrote: The easist way is to write a backtracking solver. It doesn't necessarily have to be DLX. Since you claim to have a backtacking generator, you would seem to have the basics already in place. You can worry about efficiency later. I know of no way to prove, without counting, that a candidate puzzle has multiple solutions, other than by finding one solution, determining all the unavoidable sets that it contains, and showing that at least one is not covered. You may not want to get into that. Regards, Mike Metcalf Hi Mike, Thanks for replying! I do can program a brute-force backtrack solver, but i do not undersand how it is going to count solutions, since it stop backtracking when it find the first solution. Otherwise, this algorithm would try EVERY SINGLE possibility of filling a board (in the worst case, where the board really has only one solution): 1- Board Generated 2- Brute-force backtracking solver runs until it can get to R9C9. So, it found one solution. Now, imagine that's the ONLY solution possible. 3- Somehow, this Brute-force backtracking solver, backtracks again to the begginning of the board, trying to find a new solutin, but since there's no other, it will try ALL possibilities in vain. I'm i right, or i didn't get your point at all? I'm beggining to think that i'm too dumb for this task... Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Sat Aug 30, 2008 8:17 pm    Post subject: pedrohp wrote: Thanks for replying! I do can program a brute-force backtrack solver, but i do not undersand how it is going to count solutions, since it stop backtracking when it find the first solution. Otherwise, this algorithm would try EVERY SINGLE possibility of filling a board (in the worst case, where the board really has only one solution): 1- Board Generated 2- Brute-force backtracking solver runs until it can get to R9C9. So, it found one solution. Now, imagine that's the ONLY solution possible. 3- Somehow, this Brute-force backtracking solver, backtracks again to the begginning of the board, trying to find a new solutin, but since there's no other, it will try ALL possibilities in vain. An important point to bear in mind is that there being only one solution is a special case. Usually there are many, so finding just the first two is not so onerous. And, of course, you limit the search space to only those combinations that anyway fulfil the sudoku row/column/box constraints. There are further optimizations, but that should get you started. HTH Mike Metcalf Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Sat Aug 30, 2008 8:30 pm    Post subject: Hi mike, I realize that a unique solution is a rare case, but it's a case that i HAVE TO find! Here's what my professor assigned to me: Quote: Develop a Sudoku generator able to solve the generated game. In every turn, a new board must be presented to be filled out by the player and there must be an option to solve it automatically. The generated problem must only admit ONE SOLUTION. I'm becoming to desperate in here! Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Sat Aug 30, 2008 8:52 pm    Post subject: pedrohp wrote: Hi mike, I realize that a unique solution is a rare case, but it's a case that i HAVE TO find! Here's what my professor assigned to me: Quote: Develop a Sudoku generator able to solve the generated game. In every turn, a new board must be presented to be filled out by the player and there must be an option to solve it automatically. The generated problem must only admit ONE SOLUTION. I'm becoming to desperate in here! But I don't quite see what your difficulty is. For a given candidate puzzle, selected from a full solution, there are only two possibilities: either there is one solution or there are many. For each empty cell in the candidate puzzle, there are not nine possible values, but a smaller number imposed by the sudoku constraints. A solver has to slog through these combinations until it finds two solutions. Rarely, it will go through all of the combinations finding that there is only one solution. Bingo! Problem solved. Stll hoping that helps, Mike Metcalf Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Sat Aug 30, 2008 11:19 pm    Post subject: Sudoku Facts of Life When Starting With a Filled Grid: 1) Starting with a filled grid guarantees that there is a unique solution initially. 2) As you conceal cell values, you introduce the possibility that mutiple solutions may result. 3) After you conceal a single/pair of cell values, you must solve the puzzle to see if a unique solution still exists. 4) A number of approaches exist to accomplish (3). All approaches rely on searching for multiple solutions. When a unique solution exists, then a lot of effort will be wasted searching for multiple solutions When multiple solutions exist, then finding two solutions is sufficient to end the search. 5) Just because concealing one single/pair of cell values results in the puzzle going from a unique solution to multiple solutions, it does not mean that concealing a different single/pair of cell values will result in multiple solutions. You will need to keep trying to conceal cell values after you've backtracked from an instance where multiple solutions are found. You will need to keep track of which cells caused backtracking so you know when to stop trying to conceal cells. Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Sun Aug 31, 2008 5:46 am    Post subject: Ok guys, Thanks so much for spending your time with me. I'll try to code this backtrack solver that stops when finds 2 solutions or fail to find more the one solution as soon as i can. I'll post back with my results Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Sun Aug 31, 2008 3:28 pm    Post subject: Step 1: Generate a (randomly) filled grid Step 2: Conceal a (randomly) single/pair of cell values Step 3: Check for restrictions (no more than 4 empty boxes, no more than 1 empty line in the same band/stack, at least 8 of the 9 values are among the givens) => passed or failed Step 4: If step 3 failed then restore the last concealed single/pair of cell values and continue with step 2 Step 5: Solve the puzzle to see if a unique solution still exists => one solution=passed, more then one solution=failed Step 6: If step 5 failed then restore the last concealed single/pair of cell values and continue with step 2 Step 7: Count the givens and continue with step 2 if you want to conceal more cell values Step 8: Done Now for the solver from step 5... It's obvious that the solver has to try out all possible values for each blank (concealed) cell, and this in same order (most likely ascending from 1 to 9). Based on the givens left, you can eliminate candidates in the blank cells first, this will shorten the brute force solving time. In my solver (See topic: Dancing Links and Visual Basic) the blank cells their possible candidates are continiously updated each time the next value is tried for a cell. And it allways takes the blank cell with the least possible candidates to continue solving. That same principle is handled by real DLX-solvers. If a blank cell has 0 candidates than the previous filled in blank cell(s) caused it and must be reset by backtracking those cell(s) and applying the next possible candidate. Marc. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Mon Sep 01, 2008 10:52 pm    Post subject: Ok, guys I think i have created a program to generate one SudokuBoard with one single solution. THANKS SO MUCH for your patience!! I find that my algorithm is VERY FAR AWAY from efficient, and would very much like to improove it. I'd really like to post my source code here, but the forum does not allow me to post hyperlinks. Here's what i'm doing: For the Generator: 1- Start with a valid solved grid 2- Randomly concel 40 cells 3- Solve the board. If one solution, go to step 4, if more than one, go to step 5. 4- Print both solved and unsolved board on the screen and smile. The End 5- Conceal two more cells and solve again. If one solution, go to step 4, if more then one, repeat step 5 until i have concealed 61 cells (20 clues in the game). If so, start from Step One (from scratch); This is giving me a slow generation time... For the Solver: 1- Starting from Cell 0. If this cell's value is grater then 0 (it's a clue), check the next cell (recursion), else, Step 2; 2- Find all candidates for the current cell from the original unsolved board; 3- Start a loop to check all candidates: 3.1- Insert first candidate; 3.2- Check row, column and box constrains, if success, go to step check the next cell (recursion), if fails check the next Candidate (backtrack). 4- When the recursion reaches cell 81, compare the found solution with the first generated, if true, increment the solution counter and backtrack, if false, return as failure for another concealing. Lunatic wrote: Step 1: Generate a (randomly) filled grid Step 2: Conceal a (randomly) single/pair of cell values Step 3: Check for restrictions (no more than 4 empty boxes, no more than 1 empty line in the same band/stack, at least 8 of the 9 values are among the givens) => passed or failed Step 4: If step 3 failed then restore the last concealed single/pair of cell values and continue with step 2 Step 5: Solve the puzzle to see if a unique solution still exists => one solution=passed, more then one solution=failed Step 6: If step 5 failed then restore the last concealed single/pair of cell values and continue with step 2 Step 7: Count the givens and continue with step 2 if you want to conceal more cell values Step 8: Done Now for the solver from step 5... It's obvious that the solver has to try out all possible values for each blank (concealed) cell, and this in same order (most likely ascending from 1 to 9). Based on the givens left, you can eliminate candidates in the blank cells first, this will shorten the brute force solving time. In my solver (See topic: Dancing Links and Visual Basic) the blank cells their possible candidates are continiously updated each time the next value is tried for a cell. And it allways takes the blank cell with the least possible candidates to continue solving. That same principle is handled by real DLX-solvers. If a blank cell has 0 candidates than the previous filled in blank cell(s) caused it and must be reset by backtracking those cell(s) and applying the next possible candidate. Marc. Lunatic, Thanks so much for replying! i'll try to modify my algorithm to do some of theese implementations... here's what i have in mind: 1- If i'm cheking a cell with only one candidate (a Naked Single), i treat that cell as a clue, and don't reset it to blank when backtracking. 2- Use the recommended roll-back when concealing a pair that ruined everything instead of starting from scratch Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Tue Sep 02, 2008 12:28 am    Post subject: Also, how can i hide cells simmetricaly, if theese values are ramdomly generated? Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Tue Sep 02, 2008 6:15 am    Post subject: pedrohp wrote: For the Generator: 1- Start with a valid solved grid 2- Randomly concel 40 cells 3- Solve the board. If one solution, go to step 4, if more than one, go to step 5. 4- Print both solved and unsolved board on the screen and smile. The End 5- Conceal two more cells and solve again. If one solution, go to step 4, if more then one, repeat step 5 until i have concealed 61 cells (20 clues in the game). If so, start from Step One (from scratch); This is giving me a slow generation time... In step 5 you need to restore any cells that led to a multiple solution, before you remove still more clues. The method is to start off with many clues and one solution and move towards fewer clues and still one solution. If, at any point, there are multiple solutions, you need to replace the clues that led to that (see Lunatic's post). In general, solvers can be made more efficient by: a) solving for singles before even starting (thereby reducing the search space, or pruning the search tree, however you wish to express it); b) by varying fastest the cells with the most candidates and slowest those with the fewest. To remove clues while maintaining symmetry, you simply need to generate one random deletion and then delete also its symmetry partners. HTH Mike Metcalf Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Tue Sep 02, 2008 5:14 pm    Post subject: I'm already working on those fixes... About the symmetric puzzles: 00 01 02 || 03 04 05 || 06 07 08 09 10 11 || 12 13 14 || 15 16 17 18 19 20 || 21 22 23 || 24 25 26 ----------------------------------------- 27 28 29 || 30 31 32 || 33 34 35 36 37 38 || 39 40 41 || 42 43 44 45 46 47 || 48 49 50 || 51 52 53 ----------------------------------------- 54 55 56 || 57 58 59 || 60 61 62 63 63 65 || 66 67 68 || 69 70 71 72 73 74 || 75 76 77 || 78 79 80 Like this? (where symetric clues are in same color) If yes, what about the central column? Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Tue Sep 02, 2008 6:18 pm    Post subject: pedrohp wrote: Like this? (where symetric clues are in same color) If yes, what about the central column? Yes, like that. There are many types of symmetry, this one is left/right. Others are rotational by 90 or 180 degrees, or about the diagonal or anti-diagonal. There are no rules, but a very common one is that used by crossword puzzles, 180 rotational. In your case, the central column is its own reflection, so you can do with it what you want. Regards, mike metcalf Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Tue Sep 02, 2008 7:27 pm    Post subject: pedrohp wrote: I'm already working on those fixes... About the symmetric puzzles: 00 01 02 || 03 04 05 || 06 07 08 09 10 11 || 12 13 14 || 15 16 17 18 19 20 || 21 22 23 || 24 25 26 ----------------------------------------- 27 28 29 || 30 31 32 || 33 34 35 36 37 38 || 39 40 41 || 42 43 44 45 46 47 || 48 49 50 || 51 52 53 ----------------------------------------- 54 55 56 || 57 58 59 || 60 61 62 63 63 65 || 66 67 68 || 69 70 71 72 73 74 || 75 76 77 || 78 79 80 Like this? (where symetric clues are in same color) If yes, what about the central column? To gain 180 rotational, randomly pick a cell out of the 81 cells (number between 0 and 80) and substract that cell number from 80 to calculate the other "180 rotational" cell. For example: if your program randomly picks cell number 52, then the other cell must be 80-52=28 In fact, each type of symmetry has it's own way on calculating the reflective cell. Have fun... Marc. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Wed Sep 03, 2008 10:28 am    Post subject: pedrohp wrote: I'd really like to post my source code here, but the forum does not allow me to post hyperlinks. Since you have more than 5 posts, you should be able to use one of those two possibilities... Code: [url]http://url[/url] or [url=http://url]URL text[/url] Marc. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Thu Oct 16, 2008 11:10 pm    Post subject: HI there Guys! I'm back here just to say a huge THANKS to all of you who provided help and guidance to me in this algorithm. I managed to fill the task before the deadline and got an A+ (9.9 out of 10.0)! once again, THANKS SO MUCH! Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Goto page Previous  1, 2, 3  Next Page 2 of 3   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron