29.10.2016, 09:23
(
Последний раз редактировалось SyS; 31.10.2016 в 01:39.
)
Sudoku solver using Recursive Backtracking Algorithm - pawn version
This was one of my favourite programs that i did in c++ .I decided to port it to pawn. It can be useful for making mini games like sudoku.
Gist Link
PHP код:
/*
Sudoku solver using
Recursive Backtracking algorithm
pawn version by Sreyas
*/
UAN(a[][9],&i,&j)
{
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(a[i][j]==0)
return 1;
return 0;
}
ROW(a[][9],in,num)
{
for(new i=0;i<9;i++)
if(a[in][i]==num)
return 1;
return 0;
}
COL(a[][9],in,num)
{
for(new i=0;i<9;i++)
if(a[i][in]==num)
return 1;
return 0;
}
GRID(a[][9],i,j,num)
{
for(new u=0;u<3;u++)
for(new y=0;y<3;y++)
if(a[i+u][j+y]==num)
return 1;
return 0;
}
safe(a[][9],i,j,num)
{
if(!ROW(a,i,num)&&!COL(a,j,num)&&!GRID(a,i-i%3,j-j%3,num))
return 1;
return 0;
}
solve(a[][9])
{
new i,j;
if(!UAN(a,i,j))
return 1;
for(new k=1;k<=9;k++)
{
if(safe(a,i,j,k))
{
a[i][j] = k;
if(solve(a))
return 1;
a[i][j] = 0;
}
}
return 0;
}
main()
{
//initialize the below matrix with your sudoku assuming empty space as 0
new a[9][9] =
{
{0,8,0, 7,1,2, 0,9,0},
{0,0,0, 0,0,0, 7,1,0},
{0,0,0, 0,9,4, 2,6,0},
{0,0,0, 3,6,0, 4,0,5},
{5,0,0, 0,0,0, 0,0,9},
{7,0,6, 0,2,5, 0,0,0},
{0,5,8, 2,7,0, 0,0,0},
{0,1,7, 0,0,0, 0,0,0},
{0,6,0, 9,4,1, 0,5,7}
};
if(solve(a))
{
for(new i=0;i<9;i++)
{
for(new j=0;j<9;j++)
{
printf("%d ",a[i][j]);
if((j+1)%3==0)printf(" ");
}
printf("\n");
if((i+1)%3==0)printf("\n");
}
}
else printf("NO solution");
}