FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    To add a solver or not add a solver? Goto page Previous  1, 2          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Sat Jan 24, 2009 5:11 pm    Post subject: I do not know why my images are not loading here. I am uploading my images to my google web account, and then I copy the image link. Also, if you guys give me a either until tonight or maybe Monday, I will try to convert my last step into C. This way maybe somebody can see what I am doing wrong. Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Sat Jan 24, 2009 8:16 pm    Post subject: BigPapa wrote: If I understand correctly, the puzzle will be ready for a player to solve this puzzle after the following steps below are completed. Am I correct on this? 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 Yes, you are correct. Quote: If am correct, then this is the procedure of what I have done so far... 1. First I initiated a two-dimensional list, which is similar to a two-dimensional array. This is so that it can hold 9 rows and 9 columns. For example, if you wanted to see cell 15, then list would look like this... value = PuzzleSoduko[2][6] --this is equivalent to what is inside of cell 15 or row 2 column 6. Note that in a list, and not like in an array, the first element in a list starts at 1 instead of 0 like in other languages do. OK, so you refer to each cell with both row and column indexes and your rows and columns are both numbered 1 to 9. Quote: 2. Once the list has been initialized, I built a generator that will fill all the cells legally. This is done by picking a random unsolved cell and looping through the numbers 1 to 9. When it finds a legal number, then it stores that number inside the proper row and col of the list and moves onto the next random unsolved cell. That’s OK, but you must keep track of the order of the randomly picked cells. This is needed for the backtracking portion of your generator. Quote: 3. if the generator cannot fit any of the numbers 1-9, then it backtracks to a different random cell that has been already solved, deletes that cell, and goes back to step 2 I do hope you don’t randomly pick a cell from those that allready are filled to delete !!! You must ALLWAYS delete the previous filled cell when backtracking, therefore you must keep track of the order of the randomly picked cells. Another thing: When backtracking to a previous cell, you must try out all other unused candidates first for that cell and not just delete it. Suppose that at a certain point no candidate can be placed at the last randomly picked cell. Then you must backtrack to the cell you altered before the current cell, that is the previous cell. Now if that previous cell was set to value 7, you still have to try out values 8 and 9 for that cell. If you look very closely, that’s what the four line brute force solver does. So you can use that 4-line solver for generating purposes as well. Quote: in pseudo-code 1. repeat while an empty cell still exists 1.a. pick a random empty cell 1.b. set a variable called noCollision to false 1.c. set another variable called origNumIndex -- this will hold the last number that was used when counting from 1 to 9 1.c. repeat while noCollision = false or origNumIndex = currIndex 1.c.a. set currIndex to (currIndex + 1) mod 9 1.c.b. check if currIndex already exists in its row, col, and 3x3 region => true then go back to 1.c => false set noCollision to true and breakout of 1.c loop and move back to step 1. 1.c.c. if at any chance you have stepped through all 9 numbers then origNumIndex will be equal to currIndex and that means you go to step 2. 2. Do backtracking by doing the following... 2.a. pick a random cell that has already been solved 2.b. delete that cell 2.c. go to step 1 As i mentioned, you need to keep track of the cells that are randomly picked at 1.a. To do this, you need another list (array), in fact, since you are using row and column indexes to adress the cells, you need 2 lists. The first list must keep track of the rows and the second list must keep track of the columns. Since there are 81 cells, both lists must have 81 elements (1 to 81), AND… you need ‘ptr’ as well. These could be the lists: RowTrack[] (81 elements) ColumnTrack[] (also 81 elements) So before you start the loop… A. All values within the lists PuzzleSudoku[row][column], RowTrack[] and ColumnTrack[] must be set to 0 B. set ptr to value 81 Now here is the loop…(similar to the 4-line solver) Repeat while ptr>0 1. If RowTrack[ptr] = 0 then (note: it doesn’t matter if you use RowTrack[ptr] or ColumnTrack[ptr], if the one is 0 then the other is also 0) 1.a. Pick a random empty(*) cell 1.b. Store the row index at RowTrack[ptr] 1.c. Store the column index at ColumnTrack[ptr] 2. Set value in PuzzleSudoku[RowTrack[ptr]][ ColumnTrack[ptr]] to ((PuzzleSudoku[RowTrack[ptr]][ ColumnTrack[ptr]] + 1) mod 9) 3.a If PuzzleSudoku[RowTrack[ptr]][ ColumnTrack[ptr]] is 0 then 3.a.a set value in ptr to ptr+1 3.b. Else 3.b.a. Count occurences of PuzzleSudoku[RowTrack[ptr]][ ColumnTrack[ptr]] in row, col and 3x3 region, and put the sum in variable CountNum 3.b.b. If CountNum=3 then set value in ptr to ptr-1 At this point you will have a randomly filled in grid. So you can move on to Step 2: Concealing cells and so on.... (*) Note that in fact an empty cell at 1.a. means more than just a cell without a valid value (value=0), it must be a cell that was not allready processed in the loop. So, when randomly picking a row and column, you must check if both row and column are not allready listed in both RowTrack[] and ColumnTrack[] with the same index. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top BigPapa Joined: 12 Jan 2009 Posts: 14 : Items Posted: Mon Jan 26, 2009 3:45 am    Post subject: Marc, I really appreciate your help in explaining your previous post. However, I do have a question. You have quoted... Lunatic wrote: I do hope you don’t randomly pick a cell from those that allready are filled to delete !!! You must ALLWAYS delete the previous filled cell when backtracking, therefore you must keep track of the order of the randomly picked cells. Why do you say that I should not pick a random solved cell when backtracking. I got this concept from a website which is in VB. Although I had to make minor adjustments, you can take a look at the site by going here http://www.aspfree.com/c/a/VB.NET/Create-a-Sudoku-Puzzle-Generator-using-VBNET/2/ After converting to Lingo and testing it, the generator does work and randomly fills an empty 9x9 grid from scratch. I think maybe you were confused, thinking that my generator is not working? Is that what you were thinking? If so, then I apologize for the mix-up. In my last post, I was trying to explain that I did not understand what the 4-line brute force solver really is suppose to do. At first, I was thinking it is used to keep track of multiple solutions. However, after posting, I realize that the 4-line brute force solver is not used for keeping track of multiple solutions. Instead, it just fills the concealed cells. Back to top Lunatic Joined: 11 Mar 2007 Posts: 166 : Location: Ghent - Belgium Items Posted: Mon Jan 26, 2009 7:59 pm    Post subject: BigPapa wrote: Why do you say that I should not pick a random solved cell when backtracking. I got this concept from a website which is in VB. Although I had to make minor adjustments, you can take a look at the site by going here http://www.aspfree.com/c/a/VB.NET/Create-a-Sudoku-Puzzle-Generator-using-VBNET/2/ After converting to Lingo and testing it, the generator does work and randomly fills an empty 9x9 grid from scratch. OK, i took a look at the source, and came to the conclusion that indeed this approach will work. However, it's not really a very logic approach. You could compare that approach with trying to find the way out of a maze by luck. Eventually, you will find the exit, but probably walked many times the same path inside the maze. My approach is the logical way to get your way out of that maze by trying each path only once until you find the exit. That's what the 4-line solver does. Quote: I think maybe you were confused, thinking that my generator is not working? That's exactly what i thought. Quote: However, after posting, I realize that the 4-line brute force solver is not used for keeping track of multiple solutions. Instead, it just fills the concealed cells. It takes just a minor adjustment to let the 4-line solver keeping track of multiple solutions: Code: CountSolutions=0 Boundary = ptr + 1 While ptr < Boundary   If ptr=-1 then      CountSolutions = CountSolutions +1      ptr = ptr +1   End If   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 CountSolutions then will tell you exact how many solutions were encountered. _________________ Marc ~~~<><~~~<><~~~<><~~~<><~~~ Back to top lkSudoku Joined: 16 May 2009 Posts: 60 : Items Posted: Sat May 16, 2009 10:37 am    Post subject: It is possible to generate puzzles with a unique solution with a modification of a generator without a solver, Once you generated a puzzle, you can check for multiple solutions by generating a new full puzzle starting at that puzzle, and perform backtracking and random choices even after you have generated one full puzzle. If you can generate 2 different full puzzles starting at your puzzle, then it has multiple solutions A solver can increase efficiency 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 Page 2 of 2   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