Fastest method to generate a valid complete grid?

Phantasm4489

What other techniques are there other than mutating a static start grid?

Are there any techniques that will always produce a complete grid with no backtracking?

Lummox JR · Posted: Sun Sep 18, 2005 10:15 pm Post subject:

If you want absolutely no backtracking, you'll have to use templates like the one described here. You could eliminate candidate boards as you went along.

Otherwise, pretty much any technique will involve backtracking. Dancing links is usually the preferred method because it's quite fast. In fact, all you have to do is follow it to the first solution, so multiple-solution grids should present no problem. (In order to reduce bias, I recomend shuffling the row order for each column when using dancing links.)

The best method so for for creating puzzles seems to be just adding clues at random up to a certain number, removing clues at random as needed until the board has any solutions, then adding more until only 1 solution remains. Then, shuffling the clue order each time, keep removing clues and see if the board still has a unique solution. Once it's no longer possible to remove clues and guarantee a unique solution, you have a finished puzzle. Most of the ones I've seen by this method are generally very easy or very hard, which seems to be the curse of most puzzle generation algorithms.

dukuso · Posted: Mon Sep 19, 2005 3:52 am Post subject:

I've been using my list of 306993 "G-classes", then permuting
the 1*3-minicolumns in each band randomly until the band
is valid , with backtracking, which is fast enough.
Alternatively you could use a lookup-table for the possible 3*9-bands.

This way I get 306993 almost random nonequivalent full grids in 10-20 sec., one from each G-class (there must be a post of mine in the math-forum to explain the G-classes).

For generating sudokus,
I found it 3-4 times faster to start from these and delete clues
at random than starting from an empty grid.

It's a little biased since not all G-classes have the same number of
sudoku-grids - this could be accounted for by weigthing
the probability whether a certain grid is chosen or not.
It's also a little biased since I start from a random permutation
of the minicolumns. This could be solved with the lookup
described above.

When I start from an emptygrid I get locally minimal (no more
clue can be removed) sudokus with 23.88 clues in average.
When I start from a full grid as described above they
have 24.37 clues in average.
Has anyone found the same ? Any clue, why this is ?

Phantasm4489 · Posted: Mon Sep 19, 2005 9:51 pm Post subject:

Thanks for your replies.

I fear all this maths is way above me.

I already have a fully functional sudoku generator capable of generating puzzles to a particular difficulty level and I was hoping to find some ways of speeding it up without completely re-writing it.

Are there any details of the dancing links algorithm that dont require an A level in maths and are in a reasonably user friendly file format (ie not TEX)?

angusj · Site Admin

dukuso · Posted: Tue Sep 20, 2005 7:57 am Post subject:

here is an excert from an explanation with a C-program which
I uploaded some months ago to :
http://magictour.free.fr/suexco.txt

Given a binary matrix A(n,m) with m columns and n rows
find all subsets of the rows which sum to the all-1-vector

we could just backtrack through all subsets of the rows:

i=0;S[i]=empty subset of {1..m};I[i]=0;
m0:i++;I[i]=I[i-1];
m1:I[i]++;if(I[i]>n)goto m2;
if(Row(I[i])/\S[i-1]) nonempty) goto m1;
S[i]=S[i-1]\/Row[I[i]]
if(S[i]={1..m}) print I[1]..I[i];
goto m0;
m2:i--;if(i>0)goto m1;
return

If m is small enough, then S[i] and the rows would be variable
with m bits, intersection would be AND, union OR. If m is large
and the matrix is sparse then we would use indices from rows and
columns to the nonzero entries of the matrix instead. See below.

The above method is not very fast since it discards the
constraint that every element from {1..m} must be met,
so at any step i we can choose the column with the fewest
matching rows and only walk through these rows :
(let's say a row r and a column c are "matching", iff A(r,c)=1)

i=0;unmark all rows and columns;I[0]=0;
m0:i++;I[i]=0;
C[i]=unmarked column matching the fewest unmarked rows
if there is a column matching no unmarked row then goto m2;
m1:I[i]++;if(I[i]>n)goto m2;
if(Row I[i] is marked)goto m1;
if(Row I[i])does not match column C[i] then goto m1;
mark all rows intersecting Row I[i]
mark all columns matching any marked row
if(all columns are marked){solutions++;print I[1..i] as solution;goto m2;}
goto m0;
m2:i--;
unmark all rows matching column C[i]
unmark all columns matching one of these rows from the above line
if(i>0)goto m1;
return

Here is another formulation with a sparse matrix represented
only by the row- and column-pointers to the nonzero entries:

for a column c let Rows[c] be the number of matching rows
for a column c let Row[c][1..Rows[c]] be the indices of the matching rows

for a row r let Cols[c] be the number of matching columns
for a row r let Col[r][1..Cols[r]] be the indices of the matching columns

i=0;unmark all rows and columns;I[i]=0;
m0:i++;I[i]=0;
C[i]=unmarked column with the fewest entries matching unmarked rows
if there is a column matching no unmarked row then m2;
m1:I[i]++;if(I[i]>n)goto m2;
if(row I[i] is marked)goto m1;
if(row I[i])does not match C[i] then m1;
mark all cols matching row I[i]
mark all rows matching any of these cols, that is all rows intersecting row I[i]
if(all columns are marked) print I[1..i] as solution and then goto m2
goto m0;
m2:i--;
unmark all cols matching row I[i]
unmark all rows intersecting row I[i]
if(i>0)goto m1;
return

The exact program looks like this:

for(i=0;i<=n;i++)Ur[i]=0;
for(i=0;i<=m;i++)Uc[i]=0;
i=0;solutions=0;
m0:i++;I[i]=0;
min=n+1;for(c=1;c<=m;c++){if(Uc[c]==0){
match=0;for(r=1;r<=Rows[c];r++)if(Ur[r]==0)match++;}
if(match<min){min=match;C[i]=c;}
if(min==0)goto m2;
if(min==n+1){solutions++;goto m2;}
m1:c=C[i];I[i]++;if(I[i]>Rows[c])goto m2;
r=Row[c][I[i]];
if(Ur[r])goto m1;
for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]++;
for(k=1;k<Rows[d];k++)Ur[Row[d][k]]++;}
if(all columns are marked) print I[1..i] as solution and then goto m2
goto m0;
m2:i--;c=C[i];
r=Row[c][I[i]];
for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]--;
for(k=1;k<Rows[d];k++)Ur[Row[d][k]]--;}
if(i>0)goto m1;
return solutions;

-------------------------------------------

For a standard sudoku we have a binary matrix A(729,324).
Each row stands for a placement of one of the 9 symbols
into one of the 81 cells. The columns stand for the constraints
which must be met:
exactly one row matching a given symbol and column
exactly one symbol per column
exactly one symbol per block
exactly one symbol per block

So the row representing the placement of symbol s into
cell x,y has a one in columns

cell(x,y) = x*9-9+y
block(x,y,s) = (3*(x-1)/3+(y-1)/3)*9+s+81
row(x,s) = x*9-9+s+81*2
column(y,s) = y*9-9+s+81-3
other encodings are possible. We use an encoding based on 1..9 which
relates better to common sudoku notations rather than a system based
on 0..8 which could be better for addressing the cells and blocks.

//=================version 1=============================================

// simple and short sudoku-solver based on an exact-cover-problem-solver
// by Guenter Stertenbrink,sterten@aol.com compiled with GCC3.2
// some explanations are at : http://magictour.free.fr/suexco.doc
// DOS-executable is at : http://magictour.free.fr/suexco.exe

#include <stdio.h>
int A[10][10],Rows[325],Cols[730],Row[325][10],Col[730][5],Ur[730],Uc[325];
int C[82],I[82],Node[82];
int i,j,k,r,c,d,n=729,m=324,x,y,s;
int max,min,clues,match;
FILE *file;

/*
we have a binary n*m matrix whose rows are indexed with r and columns with c.
At step i a row and column is chosen from that matrix and an entry
into the sudoku-matrix A[][] is computed from them.

A[1..9][1..9] contains the sudoku-grid. A[x][y]=0 iff the cell (x,y) is empty
Rows[c] is the number of rows matching column c in the binary exactcover-matrix
Row[c][i] , i=1..Rows[c] is the index of the i-th row which matches column c
Cols[r] is the number of columns matching row r in the binary exactcover-matrix
Col[r][i] , i=1..Cols[c] is the index of the i-th column which matches row r
Ur[r] is zero, iff row r has not yet been marked forbidden
Uc[c] is zero, iff column c has not yet been marked forbidden
C[i] is the column chosen at step i
I[i] is the row chosen at step i
Node[i] counts how often A[][] was filled with i new entries in the process

int main(int argc,char*argv[]){
if(argc<2){m5:printf("\nusage:suexco file\n\n");
printf(" prints the number of solutions of the sudoku-puzzle in file\n");
printf(" empty cells are -.* or 0 , other nondigit-characters are");
printf(" ignored\n");exit(1);}

// ---------------read the input-file into array A[][]----------------------
if((file=fopen(argv[1],"rb"))==NULL)
{fclose(file);printf("\nfile-error\n\n");goto m5;}
i=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++){
m1:if(feof(file)){
printf("\nonly %i sudoku-entries found in file %s\n",i,argv[1]);goto m5;}
c=fgetc(file);if(c=='-' || c=='.'|| c=='0' || c=='*')c=48;
if(c<48 || c>57)goto m1;
A[x][y]=c-48;if(A[x][y]<0 || A[x][y]>9)goto m1;
i++;};

// --------------generate the basic binary exact-cover-matrix,
// -----that is, not the matrix itself but the rows and columns
r=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++)for(s=1;s<=9;s++){
r++;Cols[r]=4;Col[r][1]=x*9-9+y;Col[r][2]=(3*((x-1)/3)+(y-1)/3)*9+s+81;
Col[r][3]=x*9-9+s+81*2;Col[r][4]=y*9-9+s+81*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
x=Col[r][c];Rows[x]++;Row[x][Rows[x]]=r;}

// --------------do the initial markings required by the given clues----------
for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
for(x=1;x<=9;x++)for(y=1;y<=9;y++)
if(A[x][y]){clues++;r=x*81-81+y*9-9+A[x][y];
for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]++;
for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}}}

// -------------backtrack through all subsets of the rows-----------------
i=0;
m2://------next level. Compute the next entry------------------
i++;I[i]=0;
// ------find the column c=C[i] with fewest matching rows, if empty column
// is found, then backtrack
min=n+1;
for(c=1;c<=m;c++){
if(Uc[c]==0){match=0;for(r=1;r<=Rows[c];r++)if(Ur[Row[c][r]]==0)match++;
if(match<min){min=match;C[i]=c;}}}
if(min==0 || min>n)goto m4;
m3://--------walk through all unmarked rows r matching column c=C[i]
c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
r=Row[c][I[i]];if(Ur[r])goto m3;
//x=(r-1)/81+1;y=((r-1)%81)/9+1;s=(r-1)%9+1;A[x][y]=s;if(clues+i==81)output;
// ----delete all columns which match row r and all rows which match
//any of these columns
for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]++;
for(k=1;k<=Rows[d];k++)Ur[Row[d][k]]++;}
// -------entry was made, matrix was updated, goto the next level---------
Node[i]++;goto m2;
m4:// ----backtrack. Goto previous level, take back the last move
// restore the data as they were before that move and make the next
// available move at that level
i--;c=C[i];r=Row[c][I[i]];
for(j=1;j<=Cols[r];j++){d=Col[r][j];Uc[d]--;
for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]--;}}
if(i>0)goto m3;
printf("\n%i solutions\n",Node[81-clues]);
}

Agent Allen · Posted: Sat Oct 01, 2005 6:50 pm Post subject: Broken Link to dancingcolor.pdf

I'd love a copy of dancingcolor.pdf but the link provided is broken.
Any chance of a post directly on this site? Very Happy

_________________
Agent A

angusj · Site Admin

Agent Allen · Posted: Sun Oct 02, 2005 8:59 pm Post subject: Thanks Very Much

Thanks Very Much. Very Happy

_________________
Agent A