FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Generating large sudoku full grids          Sudoku Programmers Forum Index -> Exotic sudoku View previous topic :: View next topic   Author Message mrmarky2 Joined: 13 Jan 2007 Posts: 64 : Items Posted: Fri Apr 03, 2009 9:01 am    Post subject: Generating large sudoku full grids My program at the minute can generate up to 5x5 grids, but this takes about 5-10 seconds or so, I am hoping to improve my generator so that it can generate a full grid in a sensible time so I can go onto bigger puzzles. Here is my method for generating 5x5: 1. Fill in the grid 1 row at a time in groups of 5. 2. Fill in each row going across with a number, and if when you get to the end the row isn't full then restart the row. 3. If you have to restart too many times in a row, then restart the whole block of 5. Here is a quote that Mike posted on a previous post Quote: I decided instead to generate a grid by filling its first row with the nine digits in a random order, obtained using random_number, and then adding subsequent rows of randomly arranged digits, sorting their order as necessary to avoid clashes with digits already in place on previous rows or already in the current box. If this cannot be done, a fresh set of random numbers is used. For the third and sixth rows, an additional check is required that the box constraint is also fulfilled. Also, a deadlock condition can arise when the three digits missing from an almost completed box have already been assigned to a single column above the box. If this occurs, the program restarts. This program worked rather slowly but on looking at it again after a very long summer break, I realized that the sorting algorithm took account of the clash of a digit only in its original position, and not in its possible intended new one. When this was corrected, the program was able to generate a valid grid in less that 1msec. Since it had been written in a parameterized way, it worked too for any square grid from 4 x 4 upwards. Thus it could generate 16 x 16 grids in about 4msecs as well as 25 x 25 in about 60msecs. (All timings are with CVF 6.6C with high optimization on a 1.4GHz PC.) The method slows down beyond that, 36 x 36 grids taking a few seconds and more massive ones being still a ‘work in progress’. (Larger grids not only require more computation, but contain ever more complicated potential deadlock conditions.) Can anyone help me improve my generation process? Perhaps help implement these deadlock situations into my generation process. Thanks Mark Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Fri Apr 03, 2009 11:47 am    Post subject: Re: Generating large sudoku full grids mrmarky2 wrote: Here is a quote that Mike posted on a previous post Quote: The method slows down beyond that, 36 x 36 grids taking a few seconds and more massive ones being still a ‘work in progress’. (Larger grids not only require more computation, but contain ever more complicated potential deadlock conditions.) If I might update that old document, things have improved a little in the last three years. A 36x36 now takes only 0.3s, and the method works, erratically, for 49x49. It can be modified to produce 64x64 and 100x100 by incorporating a semi-canonical approach, whereby each even row is the reverse of the preceding odd row (which can be obscured by some shuffling). As for the deadlocks, you simply need to add the appropriate code to handle them, restarting at the first row of the current box where necessary. Regards, Mike Metcalf Back to top mrmarky2 Joined: 13 Jan 2007 Posts: 64 : Items Posted: Fri Apr 03, 2009 2:14 pm    Post subject: Hey Quote: As for the deadlocks, you simply need to add the appropriate code to handle them, restarting at the first row of the current box where necessary. I'm not sure when or how to deal with them in the generation process. you also said that larger grids not only require more computation, but contain ever more complicated potential deadlock conditions. Is there anywhere I can read up on deadlocks, or anyway I can implement them into the code? Do I need to identify each possible deadlock and program it in? Thanks Mark Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Fri Apr 03, 2009 4:23 pm    Post subject: mrmarky2 wrote: I'm not sure when or how to deal with them in the generation process. you also said that larger grids not only require more computation, but contain ever more complicated potential deadlock conditions. I've never seen them mentioned elsewhere, but here's a quick guide. The basic deadlock is: Code: 1 . . 2 . . 3 . . ----- 4 5 6 7 8 9 ? ----- This simple one can be extended to higher sizes. From 16x16 a double-column deadlock arises: Code:  1  .  .  .  2  .  .  .  3  .  .  .  .  .  .  . -------  .  1  .  .  .  2  .  .  .  3  .  .  .  .  .  . -------  4  5  6  7  8  9 10 11 12 13 14 15 16  ?  .  . ------ For 25x25, this covers 3 columns, etc. Further, from 16x16 another type arises: Code:  1  .  .  .  2  .  .  .  3  .  .  .  4  .  .  . -------  5  .  . .  6  .  .  .  7  .  .  .  8  .  .  . -------  9 10 11 12 13 14 15 16 ?  .  .  . .  .  .  . ------ And so on, for each increase in size. Either you must code to detect the deadlocks and restart at the beginning of the box in question, or you must avoid the deadlock happening by preventing such patterns from building up. HTH Mike Metcalf Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Sat Apr 04, 2009 6:16 am    Post subject: I neglected to point out that a completely different approach is to write a backtracking solver for abitrary size and to use that to solve partial (or even empty) grids, solving, of course, in random order. Regards, Mike Metcalf Back to top mrmarky2 Joined: 13 Jan 2007 Posts: 64 : Items Posted: Sat Apr 04, 2009 8:49 am    Post subject: Thanks, i'll see if I can get to work on it now. Mark Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Exotic sudoku All times are GMT Page 1 of 1   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