Problem in infinite loop in a sudoku solver

Question

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 1-Jul-15 19:41pm

Samuel Shokry

Add a Solution

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

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

nv3 · Answer 1 · 2015-07-01T20:40:00

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.