
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 510 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 semicanonical 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 doublecolumn 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 




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
