The New Sudoku Players' Forum

[pj downey]

//pj downey algorithm
//written by Paul J. Downey in C++
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
short a[82]={ 0,
0,0,0,0,0,0,0,0,6,
0,3,0,2,0,0,0,0,5,
7,0,6,0,0,8,2,1,9,
0,0,0,0,0,7,3,0,0,
0,0,9,0,3,0,8,0,0,
0,0,2,1,0,0,0,0,0,
2,8,1,4,0,0,6,0,0,
6,0,0,0,0,2,0,7,0,
5,0,0,0,0,0,0,0,0};
short g,i,j,k,l,m,n,p,s,t;
short b[82][3]={},c[82][25]={},e[82]={};
int v;
v=0;
//setting up the cross checking legality array. Each box has 20 constraints
for (i=1;i<=81;i++)
{
t=0;
for(j=1;j<=9;j++)
{
s=floor((i-1)/9)*9+j;
if(s!=i)
{
t++;
c[i][t]=s;
}
}
}
for(i=1;i<=81;i++)
{
t=8;
for(j=1;j<=9;j++)
{
s=i-floor((i-1)/9)*9+(j-1)*9;
if(s!=i)
{
t++;
c[i][t]=s;
}
}
}
for(i=1;i<=81;i++)
{
t=16;
k=floor(floor((i-1)/9)/3);
l=floor((i-floor((i-1)/9)*9-1)/3);
for(m=0;m<=2;m++)
{
for(n=0;n<=2;n++)
{
s=k*27+m*9+l*3+n+1;
if(s!=i)
{
t++;
c[i][t]=s;
}
}
}
}
for(i=1;i<=81;i++)
{ t=17;
for(j=17;j<=24;j++)
{
l=0;
for(k=1;k<=16;k++)
{
if(c[i][j]==c[i][k])
{
l=1;
}
}
if(l==0)
{
c[i][t]=c[i][j];
t++;
}
}
}
for(i=1;i<=81;i++)
{
if (a[i]==0)
{
b[i][1]=1;
b[i][2]=9;
e[i]=0;
}
else
{
b[i][1]=a[i];
b[i][2]=a[i];
e[i]=1;
}
}
// this is the actual beginning of the program. It is effectively 81 nested "for" loops.
p=1;
a[1]=b[1][1];
label1:
v++;
l=1;
i=1;
while (i<=20 and l==1)
{
if(a[p]==a[c[p][i]])
{
l=0;
}
i++;
}
if(l==1)
{
p++;
if (p==82)
{
// prints the a array which holds the solution {
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
{
cout<<a[i*9+j-9]<<" ";
}
cout<<"\n";
}
//end of print
return(0);
}
a[p]=b[p][1];
}
else
{
g=0;
while (g==0)
{
a[p]++;
if (a[p]<=b[p][2])
{
g=1;
}
else
{
if (e[p]==0)
{
a[p]=0;
}
else
{
a[p]=b[p][1];
}
p--;
}
}

}
goto label1;
return (0);
}

.............................
It's pretty compact and it will solve any puzzle.