Click here to Skip to main content
15,882,152 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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
Comments
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.

1 solution

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.
 
Share this answer
 
Comments
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.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900