FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    How to generate random sudoku array? Goto page 1, 2, 3, 4  Next          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message popo_john Joined: 14 Oct 2005 Posts: 2 : Location: Beijing Items Posted: Fri Oct 14, 2005 6:55 am    Post subject: How to generate random sudoku array? HI, every one here, i've seen some topics in the forum, but i cant find some good approach to generate sudoku array. who can help me good idea? thx. Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Fri Oct 14, 2005 12:05 pm    Post subject: there is a list of 306693 so-called G-classes at http://magictour.free.fr/sudogan.gz pick one of these at random, permute the minicolumns randomly, but such that you get a valid sudoku-grid. This way you can get a sudokugrid from any of the ~5e9 equivalence classes. Back to top noeldillabough Joined: 12 Oct 2005 Posts: 16 : Items Posted: Sat Oct 15, 2005 1:33 am    Post subject: G-Classes Cool resource, but where can I read more about these G-Classes and what they are, how they work etc? Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sat Oct 15, 2005 2:18 am    Post subject: http://www.setbb.com/phpbb/viewtopic.php?t=194&mforum=sudoku I could make a program to print one sudokugrid from each S-class, some few will be printed twice, about 6 billion grids, requiring a 500GB file to store them and running for some days. Or a program which prints all T-classes for a given G-class. (again some few doublettes may occur) Back to top mrcl Joined: 01 Dec 2005 Posts: 3 : Items Posted: Sat Dec 03, 2005 12:57 am    Post subject: Re: How to generate random sudoku array? popo_john wrote: i cant find some good approach to generate sudoku array. who can help me good idea? thx. i think it is possible by using of the results stated in http://www.sudoku.com/forums/viewtopic.php?t=44&postdays=0&postorder=asc&start=55 to construct truly random sudoku grids. for box (B1,B2,B4,B5,B3,B7,B6,B8,B9) we have at most (9!,12096,12096,448,3!^3,3!^3,8,8,1) selections. this gives about 7*10^22 possibilities to select a grid of random. there are about 7*10^21 sudoku grids (http://www.sudoku.com/forums/viewtopic.php?t=44&postdays=0&postorder=asc&start=138, http://www.sudoku.com/forums/viewtopic.php?t=44&postdays=0&postorder=asc&start=41) so there is a chance about 1/10 that such a randomly selected grid is a sudoku grid. _________________ guenter Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sat Dec 03, 2005 7:55 am    Post subject: one of these programs which count all sudokugrids can probably be modified to generate a truly random sudokugrid. You could also generate about a million random latin squares with Jacobson-Matthews(sp?) and choose the first of these which happens to be a sudokugrid 6.67e21 sudokugrids 5.5e27 9*9 latin squares Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Mon Dec 05, 2005 10:07 am    Post subject: Here's a bit of pseudo-code for completely random grid generation. No need to use big memory arrays or anything. Basically it selects a random number for cell 1, checks the grid is valid (always true), selects a number for cell 2, checks the grid is valid, selects a number for cell 3, checks the grid is valid, etc.. When the grid isn't valid a different random number is tried in that cell. When all values have been tried in that cell the recursion backs up one, and other values are tried in the previous cell. The algorithm carries on going forwards and backwards like that until it reaches the 81st cell, at which point the grid is complete. The code is very quick, but there are obviously optimisations to be made. In the interest of readability I haven't included any below. (edit)in case you were wondering, generation can be <0.5ms per board depending on how you write the BoardValid function. Code: PopulateBoard() {  PopulateCell(0) } bool PopulateCell(index) {  if (index==81   return true; // the board is full!!  // try setting each possible value in cell  set cellorder = {1..9} // Note this list contains 1..9 in a *random* order  for (i=0; i<9; i++)  {   // set this test value   set cell[index] = cellorder[i]   // is this board still valid?   if(BoardValid())   {    // it is so try to populate next cell    if (PopulateCell(index+1))    {     // if this cell returned true, then the board is valid     return true;    }   }  }  // rollback this cell  return false; } bool BoardValid() {  // test constraints  if (constraintsValid)   return true;  else   return false; } _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ Back to top tifs Joined: 19 Dec 2005 Posts: 5 : Items Posted: Mon Dec 19, 2005 12:49 am    Post subject: I wrote an implementation of this pseudo-code in pascal, but I'm having trouble with the boardvalidate function. Could you help? The function starts by checking whether a number is repeated in a row or column, and if so, the function returns false. However, the program enters an infinite loop because (i think): When an invalid number is entered for cell[i], ie when no number fits, the algorithm backtracks to cell[i-1] and tries to change that value. However, because cell[i] still contains an invalid number, cell[i-1] becomes invalid. The 2 possible solutions I can think of: 1) write boardvalid() so it only checks up to cell[i] 2) clear all cells after cell[i] before executing boardvalid() I had a go at both of these ways with no luck - suggestions appreciated Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Mon Dec 19, 2005 10:56 am    Post subject: Hi tifs, You're on the right lines with rolling that cell back before steping back in the recursion. i.e. where the comment says... Code: // rollback this cell ...you want to set the cell's value to null before the function returns in the recursion. Your two suggestions should also work fine though. Perhaps you could view the algorithm as it goes along and just slow it down with a sleep() to see what it's doing? _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ Back to top tifs Joined: 19 Dec 2005 Posts: 5 : Items Posted: Thu Dec 22, 2005 1:08 am    Post subject: Thanks for the help! I did what you suggested but it still went into a loop, so either I put the rollback command in the wrong place, or something else is wrong. I used 'cells[1..81] : integer' for the board, and the following code for the populatecell() function. Note the version of pascal I'm using doesn't support "return" - a boolean function returns true or false based on the setting of the function's name when the function has reached completion. The boardvalid code so far only checks for repetition in a row or column. Code: function populatecell(count:integer) : boolean; begin   if count <> 82 then begin         //set 1-9 in random order     triedvals := '';     for i := 1 to 9 do begin       repeat         n := (Random(9)+1);       //note pos(string1,string2) returns -1 if string2 is not present in string1       until pos(triedvals,integertostring(n)) = -1;       vals[i] := n; // vals[1..9] contains 1 to 9 in a random order       triedvals := triedvals + integertostring(n);     end;     k := 1;     valok := FALSE;         repeat       cells[count] := 0;       cells[count] := vals[k]; //try a test value       if boardvalid = TRUE then if populatecell(count+1) = TRUE then valok := TRUE;       if valok = FALSE then cells[count] := 0;       k := k + 1;     until valok = TRUE;     count := count + 1;   end; populatecell := TRUE; end; Making the program show what it's doing once gave this: 385612479 946851732 291478563 514927386 127394851 000000000 000000000 000000000 000000000 As you can see, the algorithm fails on the last number (1), which should be a 6 according to the row, but can't be according to the column. This shows it either isn't backtracking correctly, or setting cells[count] to 0 is misplaced. Note 6 is also present in the 8th column. Did I understand your populatecell code correctly? [/code] Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Thu Dec 22, 2005 8:25 am    Post subject: Hi tifs, I'm no pascal expert, but I don't think your second repeat until loop will ever terminate. What you need to do is to get populatecell to return a false value if none of it's 9 possibilities lead to a valid board. So somewhere you're going to need Code: populatecell := FALSE; Actually, maybe the following will work better... Code: function populatecell(count:integer) : boolean; begin   valok := FALSE;   if count <> 82 then begin         //set 1-9 in random order     triedvals := '';     for i := 1 to 9 do begin       repeat         n := (Random(9)+1);       //note pos(string1,string2) returns -1 if string2 is not present in string1       until pos(triedvals,integertostring(n)) = -1;       vals[i] := n; // vals[1..9] contains 1 to 9 in a random order       triedvals := triedvals + integertostring(n);     end;     k := 1;     valok := FALSE;         repeat       cells[count] := vals[k]; //try a test value       if boardvalid = TRUE then if populatecell(count+1) = TRUE then valok := TRUE;       k := k + 1;     until k > 9 || valok = TRUE;     if valok = FALSE then cells[count] := 0;   else     valok = TRUE; // i.e. if we are at cell 82, the board must be valid   end; populatecell := valok; end; In this case the second repeat loop will just try the 9 values until a valid board is found (vakok=true). If a valid board isn't found then the loop exits with valok = to false. The current value is then reset to 0 if valok is false. Finally the function returns whether or not this cell has resulted in a valid board (populatecell := valok) Note that you don't need count := count+1 inside the loop because you already add 1 to count when you call the next recursion of the function. _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ Back to top Fyska Joined: 08 Nov 2005 Posts: 10 : Items Posted: Mon Jan 02, 2006 2:15 pm    Post subject: I'm also having problems with the BoardValid() function I split the problem up into validating the 9 grids, rows and columns seperately, in 3 functions. I've checked each function separately, and they work fine - just checking the grids gives me 9 grids with 1-9 in the same place, just checking the rows gives me 1-9 along the rows. But when I call all 3 (or indeed, just 2), it completely screws up - the first grid of 3x3 is always full of the last number of cellorder..... set cellorder = {1..9} // Note this list contains 1..9 in a *random* order And the second grid has this same number everywhere except the [3,3]. Any ideas? Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Tue Jan 03, 2006 12:33 pm    Post subject: Fyska wrote: set cellorder = {1..9} // Note this list contains 1..9 in a *random* order And the second grid has this same number everywhere except the [3,3]. Any ideas? Difficult to say without seeing your code. I think there's two things to check here. Firstly test your boardvalid function by using some input which you already know is a valid board Code: 123456789 456789123 789123456 234567891 567891234 891234567 345678912 678912345 912345678 Next, make sure that your recursive function is actually recursive. For example, check that it occasionally returns false. The fact that your algorithm completes with an invalid board is not a good sign, because presumably boardvalid is returning false, which means it should never have got past the first cell which created an invalid board. This algorihtm depends entirely on the ability to backup when it reaches a cell which it can't fill in. So if it's tried all of {1..9} in a cell, and it can't get a valid board, the algorithm then needs to go back to the previous cell and try a different value. To do this the recursive function returns false, which tells the previous cell to try a different value. If that last paragraph doesn't make sense, keep reading it until it does, because that's the crux of this method. Good luck, and if you have any problems, feel free to drop me a message or post your code here. _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ Back to top Fyska Joined: 08 Nov 2005 Posts: 10 : Items Posted: Tue Jan 03, 2006 12:54 pm    Post subject: I checked whether it returns false, and it does. This is my FillBoard method [C#]: Code:         protected bool FillBoard(int index)         {             if (index == NUMROWS * NUMCOLUMS)                 return true; //board is full             int[] randomvalues = GenerateRandomNums();             //todo: change all numbers to constants             for (int i = 0; i < NUMROWS; i++)             {                 _BoardNumbers[index] = randomvalues[i];                 if (BoardIsValid())                     if (FillBoard(index + 1))                         return true; //board is valid             }             return false;         } Having another look at it, I decided to add in a 'return false' here: Code:                 if (BoardIsValid())                     if (FillBoard(index + 1))                         return true; //board is valid                     else                         return false; And the output is slightly better - it looks like: http://fyska.ireallydontcare.com/images/sudoku%20error.png which is an improvement on it being all the same number, I suppose... But still, it's a bit borked. Back to top dom Joined: 10 Nov 2005 Posts: 42 : Items Posted: Tue Jan 03, 2006 1:13 pm    Post subject: Fyska wrote: Code:                 if (BoardIsValid())                     if (FillBoard(index + 1))                         return true; //board is valid                     else                         return false; I'd change that to this just to make sure... if if else is a classic case of difficult to compile code... Code:                 if (BoardIsValid())                 {                     if (FillBoard(index + 1))                         return true; //board is valid                     else                         return false;                 } {EDIT}But you shouldn't need the else return false; bit anyway. And actually, I'm certain that'll break the algorithm...{/EDIT} {EDIT2}Actually, scratch that. Remove your additional return false;, but before you return false, make sure you do this Code: _BoardNumbers[index] = 0; Otherwise your board will be left with dud values when the algorithm goes backwards, which will definitely stop the algorithm completing. {/EDIT2} _________________ Orangeminds Sudoku http://www.orangeminds.com/sudoku/ Last edited by dom on Tue Jan 03, 2006 1:21 pm; edited 2 times in total 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, 4  Next Page 1 of 4   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