Hi everyone, I have recently written a sudoku algorithm that seems to solve the easy problems. However, in order to solve the most difficult you have to store the board and eventually make guesses, and if the guess is correct, restore the board. I have attempted this towards the bottom of the code, but this is still a work in progress. If anyone has any ideas please let me know. I plan to convert this to a java applet and upload it to a student webpage once I get it working.
Thanks in advance, Patrick.
To test what I have so far:
1. Create a text file called filenumbers in same directory as C++ file. Place your sudoku 9x9 grid similar to this:
0 7 4 0 0 0 6 5 0
5 0 0 6 0 7 0 0 3
3 0 9 0 0 0 2 0 1
0 2 0 4 1 3 0 8 0
0 0 0 8 0 5 0 0 0
0 5 0 2 7 6 0 1 0
2. Copy this code and compile it into an executable.
3. Enjoy
Code:
/*Coded by Patrick Riley... in C++ and C++ alone.Enjoy beating your friends at Sudoku in no time!
Last but not least... beware of the ukodus...they might just remember you*/
#include <cstdio>
#include <iostream>
#include <fstream>
int main()
{
using namespace std;
ifstream getnum;
int sudoku[9][9][10];
int count1,count2,count3,count4,temp,test,trial;
int remove[9][9];int ukodus[9][9][10];
int guess[9][9];
/*Get Numbers*/
getnum.open("filenumbers.txt");
for(count1=0;count1<9;count1++)
{
for(count2=0;count2<9;count2++)
{
getnum>>sudoku[count1][count2][9];
}
}
/*Output Grid*/
cout<<"You entered this grid: "<<endl;
for(count1=0;count1<9;count1++)
{
for(count2=0;count2<9;count2++)
{
cout<<sudoku[count1][count2][9]<<" ";
}
cout<<endl;
}
/*Start Trial to eliminate after possibilites eliminated*/
for(trial=0;trial<=20;trial++)
{
/*Store Possibilities*/
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
if(sudoku[count1][count2][9]==0)
{
for(count3=0;count3<=8;count3++)
{
sudoku[count1][count2][count3]=count3+1;
}
}
else
{
for(count3=0;count3<=8;count3++)
{
sudoku[count1][count2][count3]=0;
}
}
}
}
/*eliminate by looking at rows and columns*/
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
if(sudoku[count1][count2][9]!=0)
{
temp=sudoku[count1][count2][9];
temp--;
for(count3=0;count3<=8;count3++)
{
sudoku[count1][count3][temp]=0;
sudoku[count3][count2][temp]=0;
}
}
}
}
/*eliminate by looking at 3 by 3 squares (this part takes a while). Due to the fact that a 9x9 grid is made of
3x3 squares, a pattern between these grids was implemented in the for loops. However, each box of the 3x3 grids
must be delt with seperately because of differing patterns.*/
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
if(sudoku[count1][count2][9]!=0)
{
temp=sudoku[count1][count2][9];
temp--;
if(count1%3==0)
{
if(count2%3==0)
{
sudoku[count1][count2+1][temp]=0;
sudoku[count1][count2+2][temp]=0;
sudoku[count1+1][count2][temp]=0;
sudoku[count1+1][count2+1][temp]=0;
sudoku[count1+1][count2+2][temp]=0;
sudoku[count1+2][count2][temp]=0;
sudoku[count1+2][count2+1][temp]=0;
sudoku[count1+2][count2+2][temp]=0;
}
}
if(count1%3==0)
{
if(count2%3==1)
{
sudoku[count1][count2+1][temp]=0;
sudoku[count1][count2-1][temp]=0;
sudoku[count1+1][count2][temp]=0;
sudoku[count1+1][count2+1][temp]=0;
sudoku[count1+1][count2-1][temp]=0;
sudoku[count1+2][count2][temp]=0;
sudoku[count1+2][count2+1][temp]=0;
sudoku[count1+2][count2-1][temp]=0;
}
}
if(count1%3==0)
{
if(count2%3==2)
{
sudoku[count1][count2-2][temp]=0;
sudoku[count1][count2-1][temp]=0;
sudoku[count1+1][count2][temp]=0;
sudoku[count1+1][count2-1][temp]=0;
sudoku[count1+1][count2-2][temp]=0;
sudoku[count1+2][count2][temp]=0;
sudoku[count1+2][count2-1][temp]=0;
sudoku[count1+2][count2-2][temp]=0;
}
}
if(count1%3==1)
{
if(count2%3==0)
{
sudoku[count1][count2+1][temp]=0;
sudoku[count1][count2+2][temp]=0;
sudoku[count1-1][count2][temp]=0;
sudoku[count1-1][count2+1][temp]=0;
sudoku[count1-1][count2+2][temp]=0;
sudoku[count1+1][count2][temp]=0;
sudoku[count1+1][count2+1][temp]=0;
sudoku[count1+1][count2+2][temp]=0;
}
}
if(count1%3==1)
{
if(count2%3==1)
{
sudoku[count1][count2+1][temp]=0;
sudoku[count1][count2-1][temp]=0;
sudoku[count1-1][count2][temp]=0;
sudoku[count1-1][count2+1][temp]=0;
sudoku[count1-1][count2-1][temp]=0;
sudoku[count1+1][count2][temp]=0;
sudoku[count1+1][count2+1][temp]=0;
sudoku[count1+1][count2-1][temp]=0;
}
}
if(count1%3==1)
{
if(count2%3==2)
{
sudoku[count1][count2-2][temp]=0;
sudoku[count1][count2-1][temp]=0;
sudoku[count1+1][count2][temp]=0;
sudoku[count1+1][count2-1][temp]=0;
sudoku[count1+1][count2-2][temp]=0;
sudoku[count1-1][count2][temp]=0;
sudoku[count1-1][count2-1][temp]=0;
sudoku[count1-1][count2-2][temp]=0;
}
}
if(count1%3==2)
{
if(count2%3==0)
{
sudoku[count1][count2+1][temp]=0;
sudoku[count1][count2+2][temp]=0;
sudoku[count1-1][count2][temp]=0;
sudoku[count1-1][count2+1][temp]=0;
sudoku[count1-1][count2+2][temp]=0;
sudoku[count1-2][count2][temp]=0;
sudoku[count1-2][count2+1][temp]=0;
sudoku[count1-2][count2+2][temp]=0;
}
}
if(count1%3==2)
{
if(count2%3==1)
{
sudoku[count1][count2-1][temp]=0;
sudoku[count1][count2+1][temp]=0;
sudoku[count1-1][count2][temp]=0;
sudoku[count1-1][count2+1][temp]=0;
sudoku[count1-1][count2-1][temp]=0;
sudoku[count1-2][count2][temp]=0;
sudoku[count1-2][count2+1][temp]=0;
sudoku[count1-2][count2-1][temp]=0;
}
}
if(count1%3==2)
{
if(count2%3==2)
{
sudoku[count1][count2-1][temp]=0;
sudoku[count1][count2-2][temp]=0;
sudoku[count1-1][count2][temp]=0;
sudoku[count1-1][count2-1][temp]=0;
sudoku[count1-1][count2-2][temp]=0;
sudoku[count1-2][count2][temp]=0;
sudoku[count1-2][count2-1][temp]=0;
sudoku[count1-2][count2-2][temp]=0;
}
}
}
}
}
/*solving after possibilities are removed*/
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
remove[count1][count2]=0;
}
}
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
for(count3=0;count3<=8;count3++)
{
if(sudoku[count1][count2][count3]!=0)
{
remove[count1][count2]++;
}
}
}
}
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
if(remove[count1][count2]==1)
{
for(count3=0;count3<=8;count3++)
{
if(sudoku[count1][count2][count3]!=0)
{
sudoku[count1][count2][9]=sudoku[count1][count2][count3];
}
}
}
}
}
}
/*Store another array like this one for guessing
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
for(count3=0;count3<=8;count3++)
{
ukodus[count1][count2][count3]=sudoku[count1][count2][count3];
}
}
}
/*Let the guessing begin!! Begin with numbers that only have two possibilities and pick one
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
if(remove[count1][count2]==2)
{
for(count3=0;count3<=8;count3++)
{
if(ukodus[count1][count2][count3]!=0)
{
ukodus[count1][count2][9]=ukodus[count1][count2][count3];
guess[count1][count2]=ukodus[count1][count2][count3];
}
}
}
}
}
/*if we guessed right, solve this and be done with it
temp=1;
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
if(udokus[count1][count2][9]==0)
{
temp=0;
}
}
}
if(temp==1)
{
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
for(count3=0;count3<=8;count3++)
{
sudoku[count1][count2][count3]=ukodus[count1][count2][count3];
}
}
}
}
/*If we guessed wrong restore to original
if(temp==0)
{
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
for(count3=0;count3<=8;count3++)
{
ukodus[count1][count2][count3]=sudoku[count1][count2][count3];
}
}
}
}
/*guess another number
if(temp==0)
{
for(count1=0;count1<=8;count1++)
{
for(count2=0;count2<=8;count2++)
{
for(count3=0;count3<=8;count3++)
{
ukodus[count1][count2][count3]=sudoku[count1][count2][count3];
}
}
}
}
/*break if finished
if(temp==1)
{
break;
}
/*Test Row d
for(count2=0;count2<=8;count2++)
{
cout<<" Row: 4 Column: "<<count2+1<<endl;
for(count3=0;count3<=9;count3++)
{
cout<<count3+1<<"="<<sudoku[3][count2][count3]<<",";
}
cout<<endl;
} */
cout<<"Answer: "<<endl;
/*Output final grid*/
for(count1=0;count1<9;count1++)
{
for(count2=0;count2<9;count2++)
{
cout<<sudoku[count1][count2][9]<<" ";
}
cout<<endl;
}
system("Pause");
return 0;
}
Linear Mode
