Tuesday, January 29, 2008

Sudoku

I finally got my sudoku-solving program to work. For easy problems. I'm not really familiar with "advanced techniques" of solving sudokus, so my program can just do what I can do.
Here's the full cpp code:

#include
#include
#include
#include
#include
#include

using namespace std;

/*global variables*/
int cell[9][9];int i,j,k,x,y,a,b,c,d,first,second;
set CellSet;
set::iterator it;bool changed, assigned;

/*exit the program function*/
void exitme()
{
system ("PAUSE");
}

/*finding combinations in the squares*/
void squareMe(int &b, int &c)
{
if ((cell[c][b]!=0)&&(CellSet.count(cell[c][b])>0)) {
CellSet.erase(cell[c][b]);
changed=true;
}
}

void squareIt(int &b){
for (d=0;d<3;d++) {
if (i==0+3*d) {
for (c=i;c<(i+3);c++) squareMe(b,c);
}
else if (i==1+3*d) {
for (c=i-1;c<(i+2);c++) squareMe(b,c);
}
else if (i==2+3*d) {
for (c=i-2;c<=i;c++) squareMe(b,c);
}
}
}

int main ()
{
/*declare local variables*/
bool solved=true;
char InCell[]="";
/*clear variables*/
i=0;
j=0;
k=0;
x=0;
y=0;
a=0;
b=0;
c=0;
changed=false;
/*read the data*/
cout << "SUDOKU\n" << "Enter the problem:\n";
for (i=0;i<9;++i) {
for (j=0;j<9;++j) {
cout << "cell(" << i+1 << "," << j+1 << ") = ";
cin >> InCell[0];
if (isdigit(InCell[0])) {
cell[i][j]=atoi(InCell);
if (cell[i][j]==0) solved=false;
}
else {
cout << "Wrong data!\n";
exitme();
}
}
}
/*is there anything to solve?*/
if (solved==true) {
cout << "The problem is solved already!\n";
exitme();
}
/*general calcualtions*/
for (k=1;k<10;k++) CellSet.insert(k);
k=0;
assigned=true;
while ((solved==false)&&(assigned==true)) {
assigned=false;
for (i=0;i<9;i++) {
for (j=0;j<9;j++) {
for (k=1;k<10;k++) CellSet.insert(k);
k=0;
again:
if (cell[i][j]==0) {
changed=false;
for (k=0;k<9;k++) {
if ((cell[i][k]!=0)&&(CellSet.count(cell[i][k])>0)) CellSet.erase(cell[i][k]);
if ((cell[k][j]!=0)&&(CellSet.count(cell[k][j])>0)) CellSet.erase(cell[k][j]);
}
if (CellSet.size()==0) {
cout << "Wrong data. Impossible to solve.";
exitme();
}
if (CellSet.size()==1) {
it=CellSet.begin();
cell[i][j]=*it;
changed=false;
assigned=true;
}
for (a=0;a<3;a++) {
if (j==(0+3*a)) {
for (b=j;b<=(j+2);b++) squareIt(b);
}
if (j==(1+3*a)) {
for (b=(j-1);b<=(j+1);b++) squareIt(b);
}
if (j==(2+3*a)) {
for (b=(j-2);b<=j;b++) squareIt(b);
}
}
if (changed==true) goto again;
}
}
}
solved=true;
for (x=0;x<9;x++) {
for (y=0;y<9;y++) {
if (cell[x][y]==0) solved=false;
}
}
}

/*last step-output*/
cout << "SOLUTION:\n";
for (i=0;i<9;i++) {
for (j=0;j<9;j++) {
cout << "cell(" << i+1 << "," << j+1 << ")=" << cell[i][j] << "\n";
}
}
exitme();
}

So the program basically works, it just doesn't know things I don't know.
I am now working on creating windows applications in c++. Just exploring. We'll see where it leads.

3 comments:

Zhanar said...

At the beginning of the code, when listing the library items, the blog doesn't display the "<" and ">" signs. So in between those signs there were:
iostream;
stdio.h;
stdlib.h;
ctype.h;
string;
set;

GeekTeach said...

As a cheap workaround you can put the preformatting tag:

< pre >
code
< /pre >

to save the formatting and I think it will display those and other items literally.

This is really great.. I would like you to walk Ethan and Max us through it onscreen if you could when you next are in that 2nd period. Maybe even next Monday? second half of the double?

Is it good programming style to put so much of the package into the main()?

I like that you are using some comments.. PLEASE keep up that habit.. it separates the real programmers from the trial and error ones.

~Richard

Ethan Lawrence said...

I can show you some "advanced" techniques... though, they're not too different from the basics.
Anyway, I'm looking forward to it.