# SudokuSolver does not solve

• May 7th, 2013, 04:20 AM
Fafnir_42
SudokuSolver does not solve
Hi guys,

I'm coding a Sudoku Solver but it isn't finished yet. However, I've tried to run it just to see, if it works for an empty Sudoku.

Code:

```#include <iostream> typedef unsigned short ushort; using std::cout; using std::cin;    // will be needed later for input using std::endl; const ushort maxCol=9, maxRow=9; class Sudoku { private:     ushort gameField[maxRow][maxCol]; public:     Sudoku();  //ctor     void Print();     void SetNumber(ushort row, ushort col, ushort number);     void Solve();     bool CheckRow(ushort row, ushort number);     bool CheckCol(ushort col, ushort number);     bool CheckSquare(ushort row, ushort col, ushort number); }; Sudoku::Sudoku() {     for (ushort actRow=0; actRow < maxRow; actRow++)     {         for (ushort actCol=0; actCol < maxCol; actCol++)         {             SetNumber(actRow, actCol, 0);         }     } } void Sudoku::Print() {     for (ushort actRow=0; actRow < maxRow; actRow++)     {         for (ushort actCol=0; actCol < maxCol; actCol++)         {             cout << gameField[actRow][actCol] << " ";             if (actCol==2 || actCol==5)             {                 cout << "| ";             }         }         cout << endl;         if (actRow == 2 || actRow == 5)         {             cout << "------ ------- ------ " << endl;         }     }     cout << endl; } bool Sudoku::CheckCol(ushort col, ushort number) {     bool check = false;     for (ushort actRow=0; actRow < maxRow; actRow++)     {         if (gameField[actRow][col] == number)  //Checks if you find your number only one time in the column         {             check = !check; //finds it one time then check is true         }     }     return check; } bool Sudoku::CheckRow(ushort row, ushort number) {     bool check = false;     for (ushort actCol=0; actCol < maxCol; actCol++)     {         if (gameField[row][actCol] == number)  //Checks if you find your number only one time in the row         {             check = !check; //finds it one time then check is true         }     }     return check; } bool Sudoku::CheckSquare(ushort row, ushort col, ushort number) {     bool check = false;     ushort sqMinCol = col - ( col%3 );    // The smallest column in the actual square     ushort sqMinRow = row - ( row%3 );     ushort sqMaxCol = sqMinCol + 2;    //The highest column in the actual square     ushort sqMaxRow = sqMinRow + 2;     for (ushort actCol=sqMinCol; actCol <= sqMaxCol; actCol++)     {         for (ushort actRow=sqMinRow; actRow <= sqMaxRow; actRow++)         {             if (gameField[actRow][actCol] == number)             {                 check = !check;             }         }     }     return check; } void Sudoku::SetNumber(ushort row, ushort col, ushort number) {     gameField[row][col] = number; } void Sudoku::Solve() //Tries different numbers in different rows and columns {     for (ushort actRow=0; actRow < maxRow; actRow++)     {         for (ushort actCol=0; actCol < maxCol; actCol++)         {             for (ushort number=1; number <=9; number++)             {                 if ( (CheckRow(actRow, number)==true) && (CheckCol(actCol, number)==true) && (CheckSquare(actRow, actCol, number)==true))                 {                     SetNumber(actRow, actCol, number);                     break;                 }             }         }     } } int main() {     Sudoku game;     game.Print();     game.Solve();     game.Print();     return 0; }```
I don't know, why it doesn't work. CheckRow, CheckCol and CheckSquare work great.
I would appreciate any hints.
• May 7th, 2013, 06:21 AM
Fafnir_42
Re: SudokuSolver does not solve
I finally found my mistake. After that, I optimized the code a little bit and changed the Solve() Function

Code:

```#include <iostream> typedef unsigned short ushort; using std::cout; using std::cin;    // will be needed later for input using std::endl; const ushort maxCol=9, maxRow=9; class Sudoku { private:     ushort gameField[maxRow][maxCol]; public:     Sudoku();  //ctor     void Print();     void SetNumber(ushort row, ushort col, ushort number);     bool CheckRow(ushort row, ushort number);     bool CheckCol(ushort col, ushort number);     bool CheckSquare(ushort row, ushort col, ushort number);     bool Solve(ushort index); }; Sudoku::Sudoku() {     for (ushort actRow=0; actRow < maxRow; actRow++)     {         for (ushort actCol=0; actCol < maxCol; actCol++)         {             SetNumber(actRow, actCol, 0);         }     } } void Sudoku::Print() {     for (ushort actRow=0; actRow < maxRow; actRow++)     {         for (ushort actCol=0; actCol < maxCol; actCol++)         {             cout << gameField[actRow][actCol] << " ";             if (actCol==2 || actCol==5)             {                 cout << "| ";             }         }         cout << endl;         if (actRow == 2 || actRow == 5)         {             cout << "------ ------- ------ " << endl;         }     }     cout << endl; } bool Sudoku::CheckCol(ushort col, ushort number) {     for (ushort actRow=0; actRow < maxRow; actRow++)     {         if (gameField[actRow][col] == number)  //Checks if you find your number only one time in the column         {             return true;         }     }     return false; } bool Sudoku::CheckRow(ushort row, ushort number) {     for (ushort actCol=0; actCol < maxCol; actCol++)     {         if (gameField[row][actCol] == number)  //Checks if you find your number only one time in the row         {             return true;         }     }     return false; } bool Sudoku::CheckSquare(ushort row, ushort col, ushort number) {     ushort sqMinCol = col - ( col%3 );    // The smallest column in the actual square     ushort sqMinRow = row - ( row%3 );     ushort sqMaxCol = sqMinCol + 2;    //The highest column in the actual square     ushort sqMaxRow = sqMinRow + 2;     for (ushort actCol=sqMinCol; actCol <= sqMaxCol; actCol++)     {         for (ushort actRow=sqMinRow; actRow <= sqMaxRow; actRow++)         {             if (gameField[actRow][actCol] == number)             {                 return true;             }         }     }     return false; } void Sudoku::SetNumber(ushort row, ushort col, ushort number) {     gameField[row][col] = number; } bool Sudoku::Solve(ushort index) {     ushort actCol = index % 9;     ushort actRow = index / 9;     if (index==81)     {         return true;     }     if (gameField[actCol][actRow]==0)     {         for (ushort number=1; number <=9; number++)         {             if ( (CheckRow(actRow, number)==false) && (CheckCol(actCol, number)==false) && (CheckSquare(actRow, actCol, number)==false))             {                 SetNumber(actRow, actCol, number);                 if (Solve(index+1)==true)                 {                     return true;                 }                 else                 {                     SetNumber(actRow, actCol, 0);                 }             }         }     }     else     {         if (Solve(index+1)==true)         {             return true;         }     }     return false; } int main() {     Sudoku game;     game.Print();     game.Solve(0);     game.Print();     return 0; }```
But now, I get a wrong output. For example the second row and first column should be 4, but it is 0.
Do you have an idea?
• May 7th, 2013, 07:20 AM
2kaud
Re: SudokuSolver does not solve
Have you designed the program first before you started to code and does your code follow your program design? What debugging of the program have you done? Have you stepped through using the debugger to find where the code deviates from the design expectations? Have you checked your design by walking through it using pen/paper? As the program designer, you are the best person to find why it doesn't work as expected. Sorry can't be more specific but to find the problem we'll have to first understand your code design and then find where it goes wrong - the same process that you'll need to follow. Being able to debug a program (especially one written yourself) is an essential programmer skill which needs to be acquired. If during debugging you find something happening you don't understand then if you ask a specific question we'll try to provide more specific guidance.:thumb:
• May 7th, 2013, 10:21 AM
Paul McKenzie
Re: SudokuSolver does not solve
Quote:

Originally Posted by Fafnir_42
But now, I get a wrong output. For example the second row and first column should be 4, but it is 0. Do you have an idea?

Yes, the idea is that your program has a bug. What do programmers do when they have a bug? They debug the program.

So you're asking us to do the debugging work that you're required to do. Programming isn't just about writing code, compiling/linking, and then running. It is also about debugging.

No one writes a perfect program every time -- when the program isn't perfect, it's the programmers job (especially a programmer who wrote the code themselves) to debug what they wrote. You had a plan in mind, you wrote the C++ code to follow this plan, so when you debug (not just run, but also debug), where does the program go against the plan you had? What line, function, etc. is supposed to perform "x", when it is actually doing "y"?

Regards,

Paul McKenzie
• May 7th, 2013, 04:11 PM
Fafnir_42
Re: SudokuSolver does not solve
Okay, you are right, I am sorry.
If anyone is interested in the problem, here it is:

if (gameField[actCol][actRow]==0)

should be:

if (gameField[actRow][actCol]==0)