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 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: Tue Aug 26, 2008 11:57 pm    Post subject: Need help with my first Sudoku generator Hi there! I'm totaly new to Sudoku and Sudoku programming. I need to program an algorithm to generate valid Sudoku boards with only one solution. I managed to program a backtracking algorithm that generates a random solved board. I wonder now how to determine witch Cells now i should show to the player as Givens and witch ones i should hide to keep the board with only one solution. Can anybody help-me with this? I've uploaded my code to rapidshare, but can't post it here... Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Wed Aug 27, 2008 10:29 am    Post subject: Hi pedrohp, welcome... You will have to randomly take away givens, step by step, and check after each step if the sudoku is still valid (one unique solution). If the sudoku became unvalid (more than one solution), you must replace the last removed given(s) and try removing another given. To keep the symetry, you better remove the givens by pairs. Keep in mind that: - you cannot have two empty rows in the same band or stack - more than 4 empty boxes are not allowed - at least 8 of the 9 numbers must be among the givens You can insert a routine to check these restrictions before running the routine for checking the uniqueness. Marc. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Wed Aug 27, 2008 11:01 am    Post subject: Marc is, of course, assuming that you already have a solver. Since you have a backtracking generator, you must have something pretty close. The solver has to be able to count the number of solutions that a candidate puzzle has. You can test it on the following pseudo-puzzle: Code:  . . 1 . . 2 . . .  . 4 . . . . . 5 .  6 . . . 7 . 1 . .  . . . 6 . 3 . . 8  . . 9 . . . 2 . .  8 . . 2 . 1 . . .  . . 6 . 3 . . . 9  . 5 . . . . . 4 .  9 . . 7 . . 8 . .  309 solutions Once it works, you can stop the count when it reaches 2, as you need to know only whether the number of solutions is 1 or more than 1. Hope that helps, Mike Metcalf Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Wed Aug 27, 2008 3:08 pm    Post subject: Re: Need help with my first Sudoku generator pedrohp wrote: I need to program an algorithm to generate valid Sudoku boards with only one solution. I managed to program a backtracking algorithm that generates a random solved board. I wonder now how to determine witch Cells now i should show to the player as Givens and witch ones i should hide to keep the board with only one solution. Can anybody help-me with this? The second hardest part when creating a puzzle is guaranteeing a unique solution. Starting with a filled grid, as in your case, requires you to conceal cell values. Unfortunately, there isn't any rule/algorithm for this process. It's very much like the backtracking approach you used to fill the grid. There are many references to DLX solvers in this forum. If you embed this type of solver in your puzzle generator, then you can use it to check your grid as you conceal cell values and try to turn it into a puzzle. DLX has the ability to determine exactly how many solutions remain. As Metcalf mentioned, you can stop the DLX logic after it finds two solutions. No need wasting time continuing to check when there may be thousands of solutions. Also, in my mind, it's possible to get to a position where you go straight from multiple solutions to zero solutions. DLX will tell you this as well. Most people are accustomed to newspaper Sudoku puzzles where the clues are presented in a symmetric pattern. You may want to consider concealing clues in pairs to generate puzzles of this nature. There are several symmetric patterns, so there are different ways to select concealed pairs. Finally, none of the above addresses the difficulty level of the resulting puzzle. Be aware that over 95% of all Sudoku puzzles can be solved easily. If you plan to generate puzzles of varying difficulty, then you have a much bigger headache ahead!!! Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Wed Aug 27, 2008 4:40 pm    Post subject: Re: Need help with my first Sudoku generator daj95376 wrote: Also, in my mind, it's possible to get to a position where you go straight from multiple solutions to zero solutions. Surely, if you're generating from a solution grid, there must always be at least one solution? Quote: Finally, none of the above addresses the difficulty level of the resulting puzzle. Be aware that over 95% of all Sudoku puzzles can be solved easily. If you plan to generate puzzles of varying difficulty, then you have a much bigger headache ahead!!! Yes, it's called the Patterns Game! Regards, Mike Metcalf Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Wed Aug 27, 2008 7:00 pm    Post subject: Hi there, Thank you all who replied! i really appreciate! I could guess that i'm gonna need a solver, but i really don't have one already, and in fact, i don't get the slightest idea on how to code a solver... Specially because the solver for this task has to determine how many possible solutions there are. In fact, i was trying to avoid programming a solver, because if i have a solve, i could simply try to generate a new valid board from the solver approach... so i wasted my time coding this solved board generator... : ( Also, i had a talk to my professor who gave-me this task and he told me that i should build a Graph from the board and the use my generated grid to color the Graph. After colored, i should search inside this graph for the smallest connected structure. This should get me to the (theoricaly) hardest possible board. I managed to create the Graph matrix, but i think that searching this structure shall be very hard to code, so i'll try what you guys proposed here first... Sorry for my bad english, i'm not a native english speaker... Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Thu Aug 28, 2008 6:50 pm    Post subject: I hesitate to offer an alternate approach because I consider it a terrible option. That said ... You can write a backtracking -- i.e., brute force -- routine that takes the puzzle and starts from cell [r1c1] and systematically assigns a candidate as it moves from cell-to-cell until it finally reaches cell [r9c9]. Now, use the same routine but have it backtrack from cell [r9c9] to [r1c1]. If the solution is the same as the first, then the puzzle has one solution (In my opinion). Important: the routine must assign candidate values in the same order -- no matter which direction it is traveling Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Thu Aug 28, 2008 11:38 pm    Post subject: daj95376 wrote: You can write a backtracking -- i.e., brute force -- routine that takes the puzzle and starts from cell [r1c1] and systematically assigns a candidate as it moves from cell-to-cell until it finally reaches cell [r9c9]. Now, use the same routine but have it backtrack from cell [r9c9] to [r1c1]. If the solution is the same as the first, then the puzzle has one solution (In my opinion). Important: the routine must assign candidate values in the same order -- no matter which direction it is traveling I think that this implementation you suggested will just find the first solution avaliable in forward and backward. There might be other solutions... Please, correct-me if i'm wrong! Or else, it seems that i got to implement the DLX. Does anybody know a easier way for me to find out if a board has more then one solution? Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Fri Aug 29, 2008 6:10 am    Post subject: pedrohp wrote: Does anybody know a easier way for me to find out if a board has more then one solution? 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 Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Fri Aug 29, 2008 11:15 am    Post subject: pedrohp wrote: Does anybody know a easier way for me to find out if a board has more then one solution? You can take a look at the brute force backtracking solver code written in Visual Basic, wich is an easy language to understand, and use it as a guide for your own solver. See topic: Dancing Links and Visual Basic The code in that topic is a substitute for Dancing Links without using pointers, and is based upon the 4 line brute force solver (see topic: four line sudoku solver ) where rwaddilove wrote: Quote: Sudoku puzzles can be solved with just 4 lines of code. Here's it is: 1 sp(cell(ptr))=(sp(cell(ptr)) + 1) mod 10 2 if sp(cell(ptr))=0 then ptr=ptr+1:goto 1 3 if countnum(cell(ptr))=3 then ptr=ptr-1 4 if ptr>-1 then goto 1 Of course, it needs a bit of explanation. This is a brute force method, but it is so short and simple that it is very fast. You need to create two arrays and a pointer like this: sp(80) is the sudoku puzzle - 9 x 9 grid, 81 cells, numbered 0-80 cell(80) is a list of blank cells - when you read in the puzzle, store the blank cell numbers here ptr=points to the last blank cell in the list One other thing you need is a countnum() function. This counts how many times a number appears. It should appear once in a row, once in a column and once in a block, hence the if countnum()=3 then... That's it. You want to see some real code? Here it is in Visual Basic - I dislike goto so the structured version is a little longer: Code: While ptr > -1   sp(cell(ptr)) = (sp(cell(ptr)) + 1) Mod 10   If sp(cell(ptr)) = 0 Then     ptr = ptr + 1   Else     If CountNum(cell(ptr)) = 3 Then ptr = ptr - 1   End If Wend That's the main program loop that solves the puzzle in sp() - just print out the array afterwards to see the solution. The CountNum() function just counts the occurances like this: Code: Function CountNum(ByVal n As Integer) As Integer Dim i, j, k, r, c As Integer k = 0   'count 'check the row and column r = n \ 9   'row 0-8 c = n Mod 9   'column 0-8 For i = 0 To 8   If sp(r * 9 + i) = sp(n) Then k = k + 1   'row   If sp(c + i * 9) = sp(n) Then k = k + 1   'column Next 'check the block c = 3 * (c \ 3)   'left column of block 0/3/6 r = 3 * (r \ 3)    'top row of block 0/3/6 For i = 0 To 2   For j = c To c + 2     If sp((r + i) * 9 + j) = sp(n) Then k = k + 1   Next Next CountNum = k End Function This function could be made faster by checking the row and exiting if there's more than one, then checking the column and exiting if more than one, then checking the block. It would save some checking. However, it seems fast enough as it is. VB isn't particularly quick, but simple puzzles are solved instantaneously and the hard ones only take 5 or 10 seconds. Marc. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Fri Aug 29, 2008 2:54 pm    Post subject: pedrohp wrote: I think that this implementation you suggested will just find the first solution avaliable in forward and backward. There might be other solutions... Please, correct-me if i'm wrong! Think of it this way. Create a sorted list of all possible solutions to a puzzle. The forward search will find the first entry in the list. The backward search will find the last entry in the list. Unless the puzzle has only one solution, the first entry and the last entry will be different. My earlier note is still critical! Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Fri Aug 29, 2008 3:04 pm    Post subject: Re: Need help with my first Sudoku generator m_b_metcalf wrote: daj95376 wrote: Also, in my mind, it's possible to get to a position where you go straight from multiple solutions to zero solutions. Surely, if you're generating from a solution grid, there must always be at least one solution? If you start with a filled grid and conceal pairs of cells to generate a symmetric puzzle, Then I've never seen a proof that you are guaranteed to reduce it to where it goes from multiple solutions to a single solution. In particular, is there a multiple solution 18? If so, then I rest my case. Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Fri Aug 29, 2008 4:07 pm    Post subject: Re: Need help with my first Sudoku generator daj95376 wrote: m_b_metcalf wrote: daj95376 wrote: Also, in my mind, it's possible to get to a position where you go straight from multiple solutions to zero solutions. Surely, if you're generating from a solution grid, there must always be at least one solution? If you start with a filled grid and conceal pairs of cells to generate a symmetric puzzle, Then I've never seen a proof that you are guaranteed to reduce it to where it goes from multiple solutions to a single solution. In particular, is there a multiple solution 18? If so, then I rest my case. Right, but that's not what you said in your first statement. Most grids with concealed pairs will have multiple solutions, some combination of concealment may yield one, none can have zero. I don't understand what you mean by 'multiple solution 18'. Take any minimal 19-clue puzzle and remove any clue and you have an 18-clue pseudo-puzzle with multiple solutions. Are we talking at cross-purposes? Regards, Mike Metcalf Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Fri Aug 29, 2008 4:51 pm    Post subject: Re: Need help with my first Sudoku generator m_b_metcalf wrote: Are we talking at cross-purposes? Yes, and I'm the one who missed the boat. I'm sorry for the mix-up Danny Back to top pedrohp Joined: 26 Aug 2008 Posts: 11 : Items Posted: Sat Aug 30, 2008 5:33 pm    Post subject: daj95376 wrote: Think of it this way. Create a sorted list of all possible solutions to a puzzle. The forward search will find the first entry in the list. The backward search will find the last entry in the list. Unless the puzzle has only one solution, the first entry and the last entry will be different. My earlier note is still critical! Ok, i took another look on your last note and this worries me: daj95376 wrote: Important: the routine must assign candidate values in the same order -- no matter which direction it is traveling My generator uses random candidates. Take a look where the arrow poins: Code: bool populateCell(int * SudokuBoard, int index){      int i;      int RandValues[9]={1,2,3,4,5,6,7,8,9};            //End condition for the recurssion      if(index == 81){           return true;      }            //Shuffles the Candidates      ShuffleArray(RandValues,9);            //This is a loop to test the values      for(i=0;i<9;i++){           SudokuBoard[index]=RandValues[i];  <----------------------------           if(ValidateBoard(SudokuBoard,index)){                               if(populateCell(SudokuBoard,index+1)){                                  return true;                               }           }      }      SudokuBoard[index]=0;      return false; } My idea for the solver is: 1- Read the board 2- Calculate the Candidate Values for each blank cell 3- Use each cell candidate's array as the RandValues (without the shuffle) int the above shown algorithm to solve the board. will this be enought? 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 1, 2, 3  Next Page 1 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