suduku solver help

This is a discussion on suduku solver help within the C++ Programming forums, part of the General Programming Boards category; hey, i am making a sudoku solver and was going to see if i could get some help. i will ...

  1. #1
    Registered User bobknows's Avatar
    Join Date
    Jan 2011
    Location
    SD
    Posts
    87

    Question suduku solver help

    hey, i am making a sudoku solver and was going to see if i could get some help.

    i will be replacing the guess1, guess2, guess3,.... with an array and will update my code as people give me ideas.

    also, for some reason it doesnt work, if anyone can find out why it just repeats on one square please tell me!!!! i will be so happy
    my solver is pretty big so i put it in an attachment.
    Attached Files Attached Files

  2. #2
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,655
    The code, gotos and all, for those wanting to...well, whatever.

    Code:
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    void makeboard();
    bool boardtest();
    void solver();
    int sudokuboard[9][9];
    void enternumber(bool g1, bool g2, bool g3, bool g4, bool g5, bool g6, bool g7, bool g8, bool g9, int x4, int y4);
    
    int main()
    {
        cout << "this program solves a sudoku puzzle. to enter a new puzzle type the\nnumbers as you would read them, putting 0 for an empty space" << endl;
    
        makeboard();     // note that the x and y are oriented the same way they are in a graph
        solver();
        cout << "here is the solved board";
        for(int x2 = 0; x2 < 9; x2++)
        {
    
            for(int y2 = 0; y2 < 9; y2++)
            {
                cout << sudokuboard[x2][y2] << " ";
            }
            cout << endl;
    
        }
    
        cout << "the program was a success" << endl;
    
    
    
        return 0;
    }
    
    void makeboard()
    {
        while(1)
        {
            cout << "enter the numbers please" << endl;
            int x = 0;
            int y = 0;
            while(x >= 0 && x < 9)
            {
                y = 0;
                while(y >= 0 && y < 9)
                {
                    cin >> sudokuboard[x][y]; // note that the x and y axes are oriented the same way they are in a graph
                    y++;
                }
                x++;
            }
            if(boardtest() == true)
            {
                cout << "the board tested ok" << endl;
    
                return;
            }
            else
            {
                cout << "there was an error with the input of the program. please enter your numbers again." << endl;
            }
        }
    
    }
    
    bool boardtest()
    {
        int x = 0;
        int y = 0;
        cout << "testing the board...";
        while(x >= 0 && x < 9)
        {
            y = 0;
            while(y >= 0 && y < 9)
            {
                if(sudokuboard[x][y] >= 0 && sudokuboard[x][y] < 10)
                {;}
                else
                {
                    return false;
                }
                y++;
            }
        x++;
        }
        return true;
    }
    
    void solver()
    {
        bool solvedtest[81];
        for(int starter = 0; starter < 81; starter++)
        {
            solvedtest[starter] = 0;
        }
        int solvetestnumber;
    
        int x = 0;
        int y = 0;
        int ytester = 0;
        int xtester = 0;
        int xbox[3], ybox[3];
        bool guess1 = false, guess2 = false, guess3 = false, guess4 = false, guess5 = false, guess6 = false, guess7 = false, guess8 = false, guess9 = false;// tests for 1,2,3,4,5,6,7,8,9
        bool completelysolved = false;
        bool completelysolved2 = false;
        beginning:;
        while(completelysolved2 == false)
        {
            completelysolved2 = true;
            for(int x3 = 0; x3 < 9; x3++)
            {
                for(int y3 = 0; y3 < 9; y3++)
                {
                    for(; solvetestnumber < 81; solvetestnumber++)
                    if(sudokuboard[x3][y3] != 0)
                    {
                        solvedtest[solvetestnumber] = 1;
                    }
                    for(int starter = 0; starter < 81; starter++)
                    {
                        if(solvedtest[starter] == 0)
                        {
                            completelysolved = false;
                        }
                        else
                        {
                            completelysolved = true;
                        }
                        if(completelysolved == false)
                        {
                            completelysolved2 = false;
                        }
                        if(!completelysolved2)
                        {
                            goto beginning;
                        }
                    }
                }
            }
    
            x = 0;
            for(; x < 9; x++)
            {
                y = 0;
                for(; y < 9; y++)
                {                                                     // the following lines should be indented one tab less but idk how to do it all at once so they arent, feel free to change this.
                        if(sudokuboard[x][y] == 0)                    // makes sure the square is not filled already
                        {
                            cout << "attempting to solve square (" << x + 1 << "," << y + 1 << ")." << endl;
                            while(ytester < 9)                        //sets a limit on ytester
                            {                                         // this is the part that tests the row/column x
                                switch(sudokuboard[x][ytester])       //tests what it is & elimminates the corresponding guess if it is a number
                                {
                                    case 1:
                                    {
                                        guess1 = true;
                                        break;
                                    }
                                    case 2:
                                    {
                                        guess2 = true;
                                        break;
                                    }
                                    case 3:
                                    {
                                        guess3 = true;
                                        break;
                                    }
                                    case 4:
                                    {
                                        guess4 = true;
                                        break;
                                    }
                                    case 5:
                                    {
                                        guess5 = true;
                                        break;
                                    }
                                    case 6:
                                    {
                                        guess6 = true;
                                        break;
                                    }
                                    case 7:
                                    {
                                        guess7 = true;
                                        break;
                                    }
                                    case 8:
                                    {
                                        guess8 = true;
                                        break;
                                    }
                                    case 9:
                                    {
                                        guess9 = true;
                                        break;
                                    }
    
                                }
                                ytester++;
                            }
                            while(xtester < 9)                        //sets a limit on yline
                            {                                         // this is the part that tests the y row/column
                                switch(sudokuboard[xtester][y])//tests what it is & elimminates the corresponding guess if it is a number
                                {
                                    case 1:
                                    {
                                        guess1 = true;
                                        break;
                                    }
                                    case 2:
                                    {
                                        guess2 = true;
                                        break;
                                    }
                                    case 3:
                                    {
                                        guess3 = true;
                                        break;
                                    }
                                    case 4:
                                    {
                                        guess4 = true;
                                        break;
                                    }
                                    case 5:
                                    {
                                        guess5 = true;
                                        break;
                                    }
                                    case 6:
                                    {
                                        guess6 = true;
                                        break;
                                    }
                                    case 7:
                                    {
                                        guess7 = true;
                                        break;
                                    }
                                    case 8:
                                    {
                                        guess8 = true;
                                        break;
                                    }
                                    case 9:
                                    {
                                        guess9 = true;
                                        break;
                                    }
    
                                }
                                xtester++;
                            }
    
                            switch(x)                                 // this finds the box's x paremeter
                            {
                                    case 1:{}
                                    case 2:{}
                                    case 3:
                                    {
                                        xbox[1] = 0;
                                        xbox[2] = 1;
                                        xbox[3] = 2;
                                        break;
                                    }
                                    case 4:{}
                                    case 5:{}
                                    case 6:
                                    {
                                        xbox[1] = 3;
                                        xbox[2] = 4;
                                        xbox[3] = 5;
                                        break;
                                    }
                                    case 7:{}
                                    case 8:{}
                                    case 9:
                                    {
                                        xbox[1] = 6;
                                        xbox[2] = 7;
                                        xbox[3] = 8;
                                        break;
                                    }
    
                                }
                            switch(y)                                 // this finds the boxs y paremeter
                            {
                                    case 1:{}
                                    case 2:{}
                                    case 3:
                                    {
                                        ybox[1] = 0;
                                        ybox[2] = 1;
                                        ybox[3] = 2;
                                        break;
                                    }
                                    case 4:{}
                                    case 5:{}
                                    case 6:
                                    {
                                        ybox[1] = 3;
                                        ybox[2] = 4;
                                        ybox[3] = 5;
                                        break;
                                    }
                                    case 7:{}
                                    case 8:{}
                                    case 9:
                                    {
                                        ybox[1] = 6;
                                        ybox[2] = 7;
                                        ybox[3] = 8;
                                        break;
                                    }
                                }
    
                            for(int xlimit = 0; xbox[xlimit] < 3; xlimit++) // this will test the 3x3 square box
                            {
                                    for(int ylimit = 0; ybox[ylimit] < 3; ylimit++)
                                    {
                                        switch(sudokuboard[xbox[xlimit]][ybox[ylimit]])   //tests what it is & elimminates the corresponding guess if it is a number
                                        {
                                        case 1:
                                        {
                                            guess1 = true;
                                            break;
                                        }
                                        case 2:
                                        {
                                            guess2 = true;
                                            break;
                                        }
                                        case 3:
                                        {
                                            guess3 = true;
                                            break;
                                        }
                                        case 4:
                                        {
                                            guess4 = true;
                                            break;
                                        }
                                        case 5:
                                        {
                                            guess5 = true;
                                            break;
                                        }
                                        case 6:
                                        {
                                            guess6 = true;
                                            break;
                                        }
                                        case 7:
                                        {
                                            guess7 = true;
                                            break;
                                        }
                                        case 8:
                                        {
                                            guess8 = true;
                                            break;
                                        }
                                        case 9:
                                        {
                                            guess9 = true;
                                            break;
                                        }
    
                                    }
                                }
                            }
    
                                          // i need to add a test chassis to put in numbers if the program has solved it.
                            enternumber(guess1, guess2, guess3, guess4, guess5, guess6, guess7, guess8, guess9, x, y);
                            if(sudokuboard[x][y] != 0)
                            {
                                goto beginning;
                            }
                        }
    
                }
            }
        }
        x = 0;
        y = 0;
    
        return;
    }
    
    void enternumber(bool g1, bool g2, bool g3, bool g4, bool g5, bool g6, bool g7, bool g8, bool g9, int x4, int y4)
    {
        int gnumber[9];
        for(int a = 0; a < 9; a++)
        {
            gnumber[a] = 0;
        }
        if(!g1)
        {
            gnumber[0] = 1;
        }
        if(!g2)
        {
            gnumber[1] = 2;
        }
        if(!g3)
        {
            gnumber[2] = 3;
        }
        if(!g4)
        {
            gnumber[3] = 4;
        }
        if(!g5)
        {
            gnumber[4] = 5;
        }
        if(!g6)
        {
            gnumber[5] = 6;
        }
        if(!g7)
        {
            gnumber[6] = 7;
        }
        if(!g8)
        {
            gnumber[7] = 8;
        }
        if(!g9)
        {
            gnumber[8] = 9;
        }
        bool solved1;
        int solved2;
        for(int b = 0; b < 9; b++)
        {
            if(gnumber[b] == 0)
            {
                solved1 = 1;
            }
            if(solved1)
            {
                solved2++;
            }
            solved1 = 0;
        }
        if(solved2 > 1)
        {}
        else if(solved2 < 1)
        {
            for(int c = 0; c < 9; c++)
            {
                switch(gnumber[c])
                case 0:
                {
                    sudokuboard[x4][y4] = (c + 1);
                    break;
                }
    
            }
        }
    
    
        return;
    
    }
    You should put your code in code tags in your post, not attach it as a text file.

  3. #3
    Registered User bobknows's Avatar
    Join Date
    Jan 2011
    Location
    SD
    Posts
    87
    sorry, i just thought it was a little big

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    It doesn't work because it doesn't use backtracking or any advanced rules.
    Basically you've assumed that as long as there is an unfilled cell on the board, that there must be a cell which can contain only one possible value according to the basic unique values in each row/column/box rule.
    This assumption will only hold true for the absolute simplest of "easy" boards.

    To get closer to solving it you need to either:
    1. Use more advanced rules such as x-wing etc, or
    2. Use backtracking, which basically means picking a value and filling it in, then trying to see if the board can still be solved and if that fails, reverting and trying a different value.
    3. Both 1 and 2.
    (Option number 1 is not guaranteed to solve every possible board either)

    You also need to switch to arrays where you're got a lot of copy and paste code, and you should consider changing your representation to keep track of what values are remaining to be tried in each cell, or something along those lines.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User bobknows's Avatar
    Join Date
    Jan 2011
    Location
    SD
    Posts
    87
    i can set up a backtracking program pretty easily and i will set up a limit to how many times it can test the board like i have it.

    what i really need help with is getting it to stop repeating.
    i will put in the board as
    0 2 3 4 5 6 7 8 9
    4 5 6 7 8 9 1 2 3
    7 8 9 1 2 3 4 5 6
    2 3 4 5 6 7 8 9 1
    5 6 7 8 9 1 2 3 4
    8 9 1 2 3 4 5 6 7
    3 4 5 6 7 8 9 1 2
    6 7 8 9 1 2 3 4 5
    9 1 2 3 4 5 6 7 8
    which is a true board with only one blank but it will just output

    testing square (1,1)
    testing square (1,1)
    testing square (1,1)

    and not go anywhere.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Puzzle game solver with the Best-First algoritm
    By LordMX in forum C Programming
    Replies: 17
    Last Post: 08-11-2008, 11:00 AM
  2. Target Solver
    By P4R4N01D in forum C Programming
    Replies: 4
    Last Post: 01-14-2008, 05:49 PM
  3. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  4. Linear Equation Solver
    By EvilGuru in forum C++ Programming
    Replies: 7
    Last Post: 10-22-2005, 11:10 AM
  5. New Contest: Solitaire Solver!!
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 09-12-2002, 02:03 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21