15,882,152 members
See more:
Hi, I'm making a simple Sudoku solver, The algorithm is very simple and dumb find a block where there is only one possible place for this number in it. it worked once in easy game when I tried it using an extremely and medium difficulties it entered an infinite loop when I tried another easy game it failed!!
C++
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct maxes
{
int number;
int used;
};
bool compare_by_used(const maxes& a,const maxes& b);

class sudoku
{
public :
void take_board(); //Done  //takes the board by asking the user to enter each row one by one
void solve_game();        //solves the games completely
void show_board(); //Done //show the game board
sudoku(); //Done
~sudoku() {} // Done        //destructor do nothing

private :
enum {AVAILABLE_MOVES = 0,GAME_BOARD = 1}; // Done

//this array contains both of game board and available free boxes for each number // Done
short game[2][10][10];
vector < maxes > maxes_sorted;

inline void sort_maxes();

//returns index of the first element in a box in form of xy. for x and separately x = xy/10 y = xy%10
short get_location(const short& box_index);//Done

//find available boxes for each number
void find_availables(); //Done

//return true if the the number if the number is available in this box
bool is_available_in_box(const short& num,const short& box_index);//Done

//number of occupied places
short allocated_places; // Done

//if the number has one available place it return xy of the place else it returns 0
short is_available_here_only(const short& box_index,const short& num); // Done

//find if the number is available in this place
bool is_available_here(const short& x,const short& y,const short& num); // Done

//find next possible box for a number
inline short find_next(short i);
};

bool compare_by_used(const maxes& a,const maxes& b)
{
return ( a.used > b.used );
}

inline void sudoku::sort_maxes()
{
sort(maxes_sorted.begin(),maxes_sorted.end(),compare_by_used);
}

inline short sudoku::find_next(short i)
{
for (short j = 1; j < 10; j++)
{
if (game[AVAILABLE_MOVES][i][j] != 0)
{
return game[AVAILABLE_MOVES][i][j];
}
}
return 10;
}

void sudoku::solve_game()
{
register short i , j , place;
while (allocated_places != 81)
{
if (allocated_places == 41)
{
allocated_places = allocated_places;
}
for (i = 1; i < 10;i++)
{
if (maxes_sorted[i].used == 9)
{
continue;
}
for (j = 1; j < 10; j++)
{
if (game[AVAILABLE_MOVES][i][j] == 0)
continue;
place = is_available_here_only(game[AVAILABLE_MOVES][i][j], i);
if (place != 0)
{
game[GAME_BOARD][place/10][place%10] = i;
game[AVAILABLE_MOVES][i][j] = 0;
maxes_sorted[i].used++;
allocated_places++;
j = find_next(i);
sort_maxes();
}
}
}
}
}

void sudoku::show_board()
{
for (short i = 1; i < 10; i++)
{
if (i == 1)
cout << "+---+---+---+---+---+---+---+---+---+\n|\n";
for (short j = 1; j < 10; j++)
{
if (j == 1)
cout << "| ";
cout << int(game[GAME_BOARD][i][j]);
cout << " | ";
}
cout << endl;
cout << "\n+---+---+---+---+---+---+---+---+---+\n";
}
}

void sudoku::take_board()
{
cout << "                  1 2 3 4 5 6 7 8 9\n";
for (short i = 1; i < 10; i++)
{
cout << "Enter the " << int(i) << " row : ";
for (short j = 1; j < 10; j++)
{
cin >> game[GAME_BOARD][i][j];
if (game[GAME_BOARD][i][j] > 0)
{
maxes_sorted[ game[GAME_BOARD][i][j] ].used++;
allocated_places++;
}
}
}
find_availables();
}

bool sudoku::is_available_here(const short& x,const short& y,const short& num)
{
if (game[GAME_BOARD][x][y] != 0)
{
return false;
}
for (short i = 1; i < x; i++)
{
if (game[GAME_BOARD][i][y] == num )
return false;
}
for (short i = x+1; i < 10; i++)
{
if (game[GAME_BOARD][i][y] == num )
return false;
}
for (short i = y+1; i < 10; i++)
{
if (game[GAME_BOARD][x][i] == num )
return false;
}
for (short i = 1; i < y; i++)
{
if (game[GAME_BOARD][x][i] == num )
return false;
}
return true;
}

short sudoku::is_available_here_only(const short& box_index,const short& num)
{
if (box_index == 0)
{
return 0;
}
short place = get_location(box_index);
short available_place = 0;
short counter = 0;
for (short x = place / 10 ; x <= (place / 10 + 2); x++)
{
for (short y = place % 10 ; y <= (place % 10 + 2); y++)
{
if ( is_available_here(x,y,num) )
{
counter++;
if (counter > 1)
{
return 0;
}
available_place = ( x * 10 ) + y;
}
}
}
if (counter != 1)
{
return 0;
}
return available_place;
}

bool sudoku::is_available_in_box(const short& num,const short& box_index)
{
int place = get_location(box_index);
for (short i = place / 10; i <= (place/10 + 2); i++)
{
for (short j = place % 10; j <= (place%10 + 2); j++)
{
if ( game[GAME_BOARD][i][j] == num )
{
return false;
}
}
}
return true;
}

void sudoku::find_availables()
{
short i,j;
for (i = 1; i < 10; i++) // number
{
for (j = 1; j < 10; j++) // box
{
if (is_available_in_box(i,j))
{
game[AVAILABLE_MOVES][i][j] = j;
}
}
}
sort_maxes();
}

inline short sudoku::get_location(const short& box_index)
{
switch (box_index)
{
case 1:
return 11;
break;
case 2:
return 14;
break;
case 3:
return 17;
break;
case 4:
return 41;
break;
case 5:
return 44;
break;
case 6:
return 47;
break;
case 7:
return 71;
break;
case 8:
return 74;
break;
case 9:
return 77;
break;
default :
return 0;
break;
}
}

sudoku::sudoku()
{
short i = 0,k = 0,j = 0;
allocated_places = 0;
maxes_sorted.resize(10);
for (int i = 0; i < maxes_sorted.size(); i++)
{
maxes_sorted[i].number = i;
maxes_sorted[i].used = 0;
}
for (k = 0; k < 2; k++)
{
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
game[int(k)][int(i)][int(j)] = 0;
}
}
}
}

int main()
{
sudoku my_game;
my_game.take_board();
my_game.show_board();
my_game.solve_game();
cout << endl << endl;
my_game.show_board();
}```

Where is the problem ? why this algorithm failed ? what are better algorithms ??

Thanks, Samuel.
Posted
Samuel Shokry 2-Jul-15 1:43am
I'm very sorry for that relatively long code
Sergey Alexandrovich Kryukov 2-Jul-15 1:52am
This is not a problem at all, please don't be sorry. Your biggest problem is hard-coded immediate constants as in "case 4: return 41...". Never do such things.
To solve your problem: 1) re-write code in a neat way; 2) use the debugger.
—SA
Samuel Shokry 2-Jul-15 11:48am
Yes, I though I had to rewrite it in a better way, I have a lot to learn about code design and alogrithms. Thanks a lot.

## Solution 1

Your infinite loop seems to be in the solve_game function (use the debugger to verify):

C++
```while (allocated_places != 81)
{
if (allocated_places == 41)
{
allocated_places = allocated_places; // doesn't do anything!
}
...
}
```

In the code marked by the ellipsis it is not guaranteed that allocated_places is increased. In that case you are entering an infinite loop. And the statement in the fifth line doesn't do anything. What were you trying to accomplish there?

Finding a solver algorithm on the Internet is not difficult: A google search with "Sudoku algorithm C++" delivered some 400.000 hits. For example:

https://en.wikipedia.org/wiki/Sudoku_solving_algorithms[^]

For your progress in programming skills I think you need to work on two things: Learn more about C++ and learn to use the debugger. Without using a debugger you will not get really far.

Samuel Shokry 2-Jul-15 11:46am
I used this if statement in my debugging no more.
Yes, I need more work I have just been programming for 2 months, I'd work hard.
Thanks a lot for help.