Printable View
hey, i am making a sudoku solver and was going to see if i could get some help.
i will be replacing the guess1, guess2, guess3,.... with an array and will update my code as people give me ideas.
also, for some reason it doesnt work, if anyone can find out why it just repeats on one square please tell me!!!! i will be so happy :D
my solver is pretty big so i put it in an attachment.
The code, gotos and all, for those wanting to...well, whatever.
You should put your code in code tags in your post, not attach it as a text file.Code:#include <iostream>
#include <cstdlib>
using namespace std;
void makeboard();
bool boardtest();
void solver();
int sudokuboard[9][9];
void enternumber(bool g1, bool g2, bool g3, bool g4, bool g5, bool g6, bool g7, bool g8, bool g9, int x4, int y4);
int main()
{
cout << "this program solves a sudoku puzzle. to enter a new puzzle type the\nnumbers as you would read them, putting 0 for an empty space" << endl;
makeboard(); // note that the x and y are oriented the same way they are in a graph
solver();
cout << "here is the solved board";
for(int x2 = 0; x2 < 9; x2++)
{
for(int y2 = 0; y2 < 9; y2++)
{
cout << sudokuboard[x2][y2] << " ";
}
cout << endl;
}
cout << "the program was a success" << endl;
return 0;
}
void makeboard()
{
while(1)
{
cout << "enter the numbers please" << endl;
int x = 0;
int y = 0;
while(x >= 0 && x < 9)
{
y = 0;
while(y >= 0 && y < 9)
{
cin >> sudokuboard[x][y]; // note that the x and y axes are oriented the same way they are in a graph
y++;
}
x++;
}
if(boardtest() == true)
{
cout << "the board tested ok" << endl;
return;
}
else
{
cout << "there was an error with the input of the program. please enter your numbers again." << endl;
}
}
}
bool boardtest()
{
int x = 0;
int y = 0;
cout << "testing the board...";
while(x >= 0 && x < 9)
{
y = 0;
while(y >= 0 && y < 9)
{
if(sudokuboard[x][y] >= 0 && sudokuboard[x][y] < 10)
{;}
else
{
return false;
}
y++;
}
x++;
}
return true;
}
void solver()
{
bool solvedtest[81];
for(int starter = 0; starter < 81; starter++)
{
solvedtest[starter] = 0;
}
int solvetestnumber;
int x = 0;
int y = 0;
int ytester = 0;
int xtester = 0;
int xbox[3], ybox[3];
bool guess1 = false, guess2 = false, guess3 = false, guess4 = false, guess5 = false, guess6 = false, guess7 = false, guess8 = false, guess9 = false;// tests for 1,2,3,4,5,6,7,8,9
bool completelysolved = false;
bool completelysolved2 = false;
beginning:;
while(completelysolved2 == false)
{
completelysolved2 = true;
for(int x3 = 0; x3 < 9; x3++)
{
for(int y3 = 0; y3 < 9; y3++)
{
for(; solvetestnumber < 81; solvetestnumber++)
if(sudokuboard[x3][y3] != 0)
{
solvedtest[solvetestnumber] = 1;
}
for(int starter = 0; starter < 81; starter++)
{
if(solvedtest[starter] == 0)
{
completelysolved = false;
}
else
{
completelysolved = true;
}
if(completelysolved == false)
{
completelysolved2 = false;
}
if(!completelysolved2)
{
goto beginning;
}
}
}
}
x = 0;
for(; x < 9; x++)
{
y = 0;
for(; y < 9; y++)
{ // the following lines should be indented one tab less but idk how to do it all at once so they arent, feel free to change this.
if(sudokuboard[x][y] == 0) // makes sure the square is not filled already
{
cout << "attempting to solve square (" << x + 1 << "," << y + 1 << ")." << endl;
while(ytester < 9) //sets a limit on ytester
{ // this is the part that tests the row/column x
switch(sudokuboard[x][ytester]) //tests what it is & elimminates the corresponding guess if it is a number
{
case 1:
{
guess1 = true;
break;
}
case 2:
{
guess2 = true;
break;
}
case 3:
{
guess3 = true;
break;
}
case 4:
{
guess4 = true;
break;
}
case 5:
{
guess5 = true;
break;
}
case 6:
{
guess6 = true;
break;
}
case 7:
{
guess7 = true;
break;
}
case 8:
{
guess8 = true;
break;
}
case 9:
{
guess9 = true;
break;
}
}
ytester++;
}
while(xtester < 9) //sets a limit on yline
{ // this is the part that tests the y row/column
switch(sudokuboard[xtester][y])//tests what it is & elimminates the corresponding guess if it is a number
{
case 1:
{
guess1 = true;
break;
}
case 2:
{
guess2 = true;
break;
}
case 3:
{
guess3 = true;
break;
}
case 4:
{
guess4 = true;
break;
}
case 5:
{
guess5 = true;
break;
}
case 6:
{
guess6 = true;
break;
}
case 7:
{
guess7 = true;
break;
}
case 8:
{
guess8 = true;
break;
}
case 9:
{
guess9 = true;
break;
}
}
xtester++;
}
switch(x) // this finds the box's x paremeter
{
case 1:{}
case 2:{}
case 3:
{
xbox[1] = 0;
xbox[2] = 1;
xbox[3] = 2;
break;
}
case 4:{}
case 5:{}
case 6:
{
xbox[1] = 3;
xbox[2] = 4;
xbox[3] = 5;
break;
}
case 7:{}
case 8:{}
case 9:
{
xbox[1] = 6;
xbox[2] = 7;
xbox[3] = 8;
break;
}
}
switch(y) // this finds the boxs y paremeter
{
case 1:{}
case 2:{}
case 3:
{
ybox[1] = 0;
ybox[2] = 1;
ybox[3] = 2;
break;
}
case 4:{}
case 5:{}
case 6:
{
ybox[1] = 3;
ybox[2] = 4;
ybox[3] = 5;
break;
}
case 7:{}
case 8:{}
case 9:
{
ybox[1] = 6;
ybox[2] = 7;
ybox[3] = 8;
break;
}
}
for(int xlimit = 0; xbox[xlimit] < 3; xlimit++) // this will test the 3x3 square box
{
for(int ylimit = 0; ybox[ylimit] < 3; ylimit++)
{
switch(sudokuboard[xbox[xlimit]][ybox[ylimit]]) //tests what it is & elimminates the corresponding guess if it is a number
{
case 1:
{
guess1 = true;
break;
}
case 2:
{
guess2 = true;
break;
}
case 3:
{
guess3 = true;
break;
}
case 4:
{
guess4 = true;
break;
}
case 5:
{
guess5 = true;
break;
}
case 6:
{
guess6 = true;
break;
}
case 7:
{
guess7 = true;
break;
}
case 8:
{
guess8 = true;
break;
}
case 9:
{
guess9 = true;
break;
}
}
}
}
// i need to add a test chassis to put in numbers if the program has solved it.
enternumber(guess1, guess2, guess3, guess4, guess5, guess6, guess7, guess8, guess9, x, y);
if(sudokuboard[x][y] != 0)
{
goto beginning;
}
}
}
}
}
x = 0;
y = 0;
return;
}
void enternumber(bool g1, bool g2, bool g3, bool g4, bool g5, bool g6, bool g7, bool g8, bool g9, int x4, int y4)
{
int gnumber[9];
for(int a = 0; a < 9; a++)
{
gnumber[a] = 0;
}
if(!g1)
{
gnumber[0] = 1;
}
if(!g2)
{
gnumber[1] = 2;
}
if(!g3)
{
gnumber[2] = 3;
}
if(!g4)
{
gnumber[3] = 4;
}
if(!g5)
{
gnumber[4] = 5;
}
if(!g6)
{
gnumber[5] = 6;
}
if(!g7)
{
gnumber[6] = 7;
}
if(!g8)
{
gnumber[7] = 8;
}
if(!g9)
{
gnumber[8] = 9;
}
bool solved1;
int solved2;
for(int b = 0; b < 9; b++)
{
if(gnumber[b] == 0)
{
solved1 = 1;
}
if(solved1)
{
solved2++;
}
solved1 = 0;
}
if(solved2 > 1)
{}
else if(solved2 < 1)
{
for(int c = 0; c < 9; c++)
{
switch(gnumber[c])
case 0:
{
sudokuboard[x4][y4] = (c + 1);
break;
}
}
}
return;
}
sorry, i just thought it was a little big
It doesn't work because it doesn't use backtracking or any advanced rules.
Basically you've assumed that as long as there is an unfilled cell on the board, that there must be a cell which can contain only one possible value according to the basic unique values in each row/column/box rule.
This assumption will only hold true for the absolute simplest of "easy" boards.
To get closer to solving it you need to either:
1. Use more advanced rules such as x-wing etc, or
2. Use backtracking, which basically means picking a value and filling it in, then trying to see if the board can still be solved and if that fails, reverting and trying a different value.
3. Both 1 and 2.
(Option number 1 is not guaranteed to solve every possible board either)
You also need to switch to arrays where you're got a lot of copy and paste code, and you should consider changing your representation to keep track of what values are remaining to be tried in each cell, or something along those lines.
i can set up a backtracking program pretty easily and i will set up a limit to how many times it can test the board like i have it.
what i really need help with is getting it to stop repeating.
i will put in the board as
0 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8
which is a true board with only one blank but it will just output
testing square (1,1)
testing square (1,1)
testing square (1,1)
and not go anywhere.