SudokuSolver does not solve
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: SudokuSolver does not solve

  1. #1
    Join Date
    Apr 2013
    Posts
    4

    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.

  2. #2
    Join Date
    Apr 2013
    Posts
    4

    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?

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  4. #4
    Join Date
    Apr 1999
    Posts
    27,427

    Re: SudokuSolver does not solve

    Quote Originally Posted by Fafnir_42 View Post
    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

  5. #5
    Join Date
    Apr 2013
    Posts
    4

    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)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center