Killer Su Doku Solver

locutus243 · Posted: Wed Sep 07, 2005 10:22 am Post subject: Killer Su Doku Solver

I noticed that the people on this site are amazingly gifted when it comes to programming. I myself have no clue about it but was wondering if it was even possible to make a solving program for the new Killer Su Doku's that are appearing in the Times.

Any thoughts would be most welcome

Thankyou

Mark

dukuso · Posted: Thu Sep 08, 2005 7:40 am Post subject:

can you briefly describe these "Killers" for the non- "Times" -readers ?

chuckfresno · Posted: Thu Sep 08, 2005 4:01 pm Post subject:

Samunamupure (Sum Number Place)

Numbers are the sum of the cells in the dotted lined enclosures.
IMPORTANT! No digit may appear twice within any of the numbered areas. The TIMES left out this rule and have not responded to requests for clarification. This example puzzle has mulitple solutions if this rule is ignored.

Samunamupure is the hybrid of two of the most popular graphic logic puzzles in Japan -- Number Place (Sudoku) and Cross Sums (Kakro).

This puzzle is also published with PRODUCTS instead of SUMS.

chuckfresno · Posted: Thu Sep 08, 2005 5:24 pm Post subject:

There is a solver here:

http://homepage3.nifty.com/funahashi/game/game676eng.html

I've tested it on two puzzles. It took only a 10 or 15 seconds to solve the one above, but it took many minutes to solve the "Deadly" one here: http://www.timesonline.co.uk/article/0,,7-1757275_2,00.html

dukuso · Posted: Fri Sep 09, 2005 2:06 pm Post subject:

I can't modify my solver for these.
No exact cover problem with sums.
Can't see how to convert it into a SAT-problem either.

But it's a "constraint programming" problem. It should be
possible to solve it with "eclipse" or such.

gaby · Posted: Fri Sep 09, 2005 5:50 pm Post subject:

My girlfriend has started doing these as well. I considered modifiying my solver for them but couldn't be bothered to define a nice clean syntax or an easy representation of the sum sets.

My initial thoughts are that the sum sets can provide further candidate reduction. For instance, {[r3c1],[r4c1]}=6, therefore this can only be {1,5} or {2,4}. Likewise {[r9c3],[r9c4]}=14 can only be {6,8} or {5,9}. Carry on and use these numbers to build your initial candidate list from a blank grid, rather than starting with candidates 1-9 in all the cells. This then opens up the board to standard solving techniques.

However, I'm not getting drawn into this or I'll want to make my solver do them. Once I've cracked tabling or ultracolouring I'll consider moving on to these. Not yet though Smile

_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

dukuso · Posted: Fri Sep 09, 2005 6:20 pm Post subject:

look for a sum with the fewist possible combinations of summands
compare this with the constraint with fewest candidates
choose the smallest
walk through all possibilities
continue

OK, this _is_ an exact cover problem, but with lots of rows.
Each possible combination of summands gives a row,
so the matrix has upto 1e5 or 1e6 rows and 324 columns.
Hmm, could be doable, I'll try...

... but not today

gaby · Posted: Fri Sep 09, 2005 6:35 pm Post subject:

I'm intrigued by the way that you refer to Sudoku as an exact cover problem. I've had a google around for this but I'm still a little mystified as to the nature of an exact cover problem. Do you have any good references relating to this? Can you inform the uninformed (me) with an overview of how it relates to Sudoku puzzles? I would be very interested in more information...
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

dukuso · Posted: Fri Sep 09, 2005 7:59 pm Post subject:

Gaby,
there had been some discussion here, also how to encode it
as SAT-instances (hmm, not sure. If not someone should post it)
You can see my source in the software-area.
I once wrote some explanation at
http://magictour.free.fr/suexco.txt or/and
http://magictour.free.fr/suexco.doc
could be updatable - give feedback what should be added/changed.

Many people also just say "dancing links" here,
referring to a paper by Knuth, which you'll easily
find typing these keywords into google.
His explanation is more detailed, with other
examples like polyominoes,n-queens,...
which can all be solved by the method.

Also, sudoku is a "constraint programming" problem,
you'll also find a lot with these keywords.
See the paper by Simonis in the math-forum in the papers - thread

-Guenter

dukuso · Posted: Sat Sep 10, 2005 8:02 pm Post subject:

// solves killer-sudokus, this software is public domain
// report bugs and improvement suggestions to sterten@aol.com
// compiled with gcc3.2, executable at
// http://magictour.free.fr/killer.exe
#include <stdio.h>
#include <time.h>
#define N 30000
#define M 325
#define Sr 444
#define Sc 11111

int Rows[M],Cols[N],Row[M][Sc],Col[N][Sr],Ur[N],Uc[M],V[M];
int S[88],C[82],I[82],Node[82],Match[325],X[88],Y[88],B[88];
int f,b,a,p,i,j,k,r,c,d,n=729,m=324,x,y,s;
int maxr=0,maxc=0,A[88][88];
int sums,nodes,max,solutions=0,min,clues,match,t1;
char L[65]="-123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#*~";
FILE *file;

char EG[843]="
input file example:
25=number of sums
30=sum , 6 = number of cells , 1,2,3,10,12,19 cells, enumerated 1..81

25
30,6,1,2,3,10,12,19
14,2,4,5
13,2,6,15
11,4,7,8,9,18
21,5,11,20,21,22,30
10,2,13,14
21,3,16,17,25
15,4,23,24,32,33
26,4,26,27,35,36
7,2,28,37
16,2,29,38
17,5,31,40,41,42,51
7,2,34,43
12,2,39,48
6,2,44,53
11,2,45,54
19,4,46,47,55,56
26,4,49,50,58,59
31,5,52,60,61,62,71
15,3,57,65,66
25,6,63,70,72,79,80,81
20,4,64,73,74,75
17,2,67,76
6,2,68,69
9,2,77,78

or just:

25,30,6,1,2,3,10,12,19,14,2,4,5,13,2,6,15,11,4,7,8,9,18,21,5,11,20,21,22,30,10,2,13,14,21,3,16,17,25,15,4,23,24,32,33,26,4,26,27,35,36,7,2,28,37,16,2,29,38,17,5,31,40,41,42,51,7,2,34,43,12,2,39,48,6,2,44,53,11,2,45,54,19,4,46,47,55,56,26,4,49,50,58,59,31,5,52,60,61,62,71,15,3,57,65,66,25,6,63,70,72,79,80,81,20,4,64,73,74,75,17,2,67,76,6,2,68,69,9,2,77,78

";

int main(int argc,char*argv[]){ t1=rawclock();
if(argc<2){printf("\nusage:killer file \n\n");
printf(" prints solutions of the killer sudoku in file\n");
exit(1);}

if((file=fopen(argv[1],"rb"))==NULL){fclose(file);printf("%s",EG);exit(1);}

fscanf(file,"%i,",&sums);
for(i=1;i<=sums;i++){
fscanf(file,"%i,",&A[i][0]);
fscanf(file,"%i,",&S[i]);
for(j=1;j<=S[i];j++)fscanf(file,"%i,",&A[i][j]);}
fclose(file);

//for(i=1;i<=sums;i++){for(j=1;j<=S[i];j++)printf("%i ",A[i][j]);printf("=%i\n",A[i][0]);}

i=0;k=3;for(x=1;x<=9;x++)for(y=1;y<=9;y++){i++;X[i]=x;Y[i]=y;B[i]=k*((x-1)/k)+(y-1)/k+1;}

n=0;for(f=1;f<=sums;f++){

for(i=1;i<=9;i++)V[i]=0;i=0;k=2;
h1:i++;I[i]=0;if(i>S[f])goto h3;
h2:I[i]++;if(I[i]>9)goto h4;
if(V[I[i]])goto h2;
m=S[f]-i;s=0;for(j=1;j<=i;j++)s+=I[j];if(s+m*(m+1)/k>A[f][0])goto h2;
V[I[i]]=1;goto h1;
h3:s=0;for(j=1;j<=S[f];j++)s+=I[j];if(s!=A[f][0])goto h4;
n++;Cols[n]=0;
for(j=1;j<=S[f];j++){s=I[j];i=A[f][j];x=X[i];y=Y[i];b=B[i];
Cols[n]++;Col[n][Cols[n]]=x*9-9+y;
Cols[n]++;Col[n][Cols[n]]=x*9-9+s+81;
Cols[n]++;Col[n][Cols[n]]=y*9-9+s+81*2;
Cols[n]++;Col[n][Cols[n]]=b*9-9+s+81*3;}
i=S[f]+1;if(Cols[n]>maxr)maxr=Cols[n];
h4:i--;V[I[i]]=0;if(i>0)goto h2;
} // next f

//printf("n=%i\n",n);

m=324;

for(i=1;i<=m;i++)Rows[i]=0;
for(i=1;i<=n;i++)for(j=1;j<=Cols[i];j++)
{c=Col[i][j];Rows[c]++;Row[c][Rows[c]]=i;}
for(i=1;i<=m;i++)if(Rows[i]>maxc)maxc=Rows[i];

for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
for(i=1;i<=81;i++)Node[i]=0;

i=0;solutions=0;nodes=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[Row[c][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]]++;}

for(k=1;k<Cols[r];k+=4){j=9;x=1+(Col[r][k]-1)/j;y=1+(Col[r][k]-1)%j;s=1+(Col[r][k+1]-82)%j;A[x][y]=s;}
if(i>=sums){for(x=1;x<=9;x++){for(y=1;y<=9;y++)printf("%i",A[x][y]);printf("\n");}printf("\n");}

Node[i]++;nodes++;if(nodes==100000000){nodes=0;for(j=1;j<=81;j++)printf("%i ",Node[j]);printf("\n");}
goto m0;
m2:i--;if(i<=0)goto m8;
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;
m8:printf("nodes:");for(i=1;i<=sums;i++)printf("%i ",Node[i]);printf(" , %i ticks \n",rawclock()-t1);
printf("n=%i m=%i Sr=%i Sc=%i\n",n,m,maxr,maxc);
}

roger888 · Posted: Thu Sep 15, 2005 1:47 pm Post subject:

dukuso · Posted: Thu Sep 15, 2005 2:00 pm Post subject:

hi roger88,

sorry for that. Yes, there is no error checking , so when you have a wrong data-file, the program might hang.
I never had this so far , but might include some error checking
now that you say this.

I assume you have a wront file which holds the data of the killer sudoku.

can you post that file ?

one example for the data file = killer-encoding
was given in the program:

25
30,6,1,2,3,10,12,19
14,2,4,5
13,2,6,15
11,4,7,8,9,18
21,5,11,20,21,22,30
10,2,13,14
21,3,16,17,25
15,4,23,24,32,33
26,4,26,27,35,36
7,2,28,37
16,2,29,38
17,5,31,40,41,42,51
7,2,34,43
12,2,39,48
6,2,44,53
11,2,45,54
19,4,46,47,55,56
26,4,49,50,58,59
31,5,52,60,61,62,71
15,3,57,65,66
25,6,63,70,72,79,80,81
20,4,64,73,74,75
17,2,67,76
6,2,68,69
9,2,77,78

this is for the puzzle mentioned earlier in this thread.
Do you see, how it is created ?

roger888 · Posted: Thu Sep 15, 2005 2:32 pm Post subject:

Hi

Yes, I understand the format of the target file. I created a text file as a test containing the sample you gave, and the program solved it OK. But now I cannot delete, move, rename killer.exe without getting a sharing violation. Interestingly, what I can do is copy it somewhere else... but I can't delete, move, rename the copy file either.

roger888 · Posted: Thu Sep 15, 2005 2:50 pm Post subject:

dukuso

I've managed to zap it with a utility called Delete Doctor. It didn't like it though Wink

dukuso · Posted: Thu Sep 15, 2005 4:33 pm Post subject:

I don't know, what might have happened.
Which operation system ?
I run it in a DOS - box under Windows-XP.

The program terminated correctly ?
How much memory do you have ?

When you can't delete a file, that might indicate that it is in use
by another process.
But I'm really no expert here.

I have no idea, how killer.exe itself might have caused this.