Closed Solved

C++ Sudoku Solver

12 answers Last reply Best Answer
More about sudoku solver
  1. Best answer
    I remember doing something like this is java a year or so ago in college, it was a pretty fun assignment.

    What we did was use a recursive backtracking solution (aka a brute force solution). It was fairly simply to write once you understood what was going on, and didn't require any advanced knowledge of how to solve sudokus.

    That second piece of code you posted seems to be using a backtracking solution.

    The basics of solving a sudoku this was is:

    1. start at the first empty cell, and put 1 in it.
    2. Check the entire board, and see if there are any conflicts
    3. If there are coflicts on the board, increase the number in the current cell by 1 (so change 1 to 2, 2 to 3, etc)
    4. If the board is clean move, start at step one again.
    5. If all nine possible numbers on a given cell cause a conflict in the board, then you set this cell back to empty, go back to the previous cell, and start again from step 3 (this is where the 'backtracking' comes in).

    Once every cell have a number in it and there are no conflicts on the board, you have a solved sudoku.

    I would recommend understanding this concept, and planning a way to solve it (in my opinion, recursion lends itself nicely to this solution). Once you have that, then start coding it, and post back if you run into any specific problems in your code (My forewarning - you should no that no one here is going to write your code for you, especially for school work)

    Good luck :)
  2. All right, thank you for your input. How well is recursive backtracking implemented into a class? Is that fairly simple?
  3. It is, you just need to make sure you understand how all this works.

    What you have to remember is that when using recursion, it is naturally 'unwinding'. In this sudoku problem for example, if you get through all 9 numbers on a given cell, and then let the current recursive call finish without calling another one, the you will end up right where you left off at the previous function (aka where you made this recursive call from).

    This is why recursion makes a very natural solution for backtracking problems. Because of the nature of recursion, it can pretty much take care of the actual 'backtracking' part of the solution for you.

    The main code used to solve this isn't very long at all. Just insure you make good use of helper methods (such as checking if the board has any conflicts in it, etc). It may help you to write up the actually backtracking solution in pseudo code first, and then write up the actual code complete with all the helper methods.

    Good luck :)
  4. Update:

    Well, I tried many different variations on the second and third ones, and decided to go with the third one, seeing as how it's the only one I can get to work. I have not yet implemented a class, but I can do that. Thank you, kyeana, for your recommendations, but I couldn't get the other one working.

    Btw, I am in an advanced college programming class with almost no programming experience, so now you may understand why I couldn't get a simple recursive program working. :) Although I did not use your recommendation, I am selecting it as best answer because it was a good one, and because no one else even posted anything.
  5. WTF??? The best answer button is not working, I tried it like 8 times, and refreshed the page and everything. I will try again later.
  6. Best answer selected by randomizer.
  7. Thanks, randomizer.
  8. Ha, no worries :) If you do run in to any trouble you can always post back here for specific help.

    Good luck
  9. THAT post should be a reference for all people that would like help for school assignments. Thanks Bruceification73 for giving me back some faith in future coworkers.
  10. Zenthar said:
    THAT post should be a reference for all people that would like help for school assignments. Thanks Bruceification73 for giving me back some faith in future coworkers.


    Well, unfortunately I won't be working in Montreal any time soon, but thanks for your kind words. I am thinking of getting a summer job at a computer repair shop in town, but that's here in Colorado, U.S.
  11. Check this out...



    #include <iostream.h>
    #include <conio.h>
    int array[9][9];
    int outputArray[9][9];
    int input_value(int x, int y, int value)
    {
    int i,j;
    for (i = 0; i < 9; i++)
    {
    if (value == outputArray[y] || value == outputArray[x])
    {
    return 0;
    }
    }
    if (x < 3)
    {
    if (y < 3)
    {
    for (i = 0; i < 3; i++)
    {
    for (j = 0; j < 3; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    else if (y < 6)
    {
    for (i = 0; i < 3; i++)
    {
    for (j = 3; j < 6; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    else
    {
    for (i = 0; i < 3; i++)
    {
    for (j = 6; j < 9; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    }
    else if (x < 6)
    {
    if (y < 3)
    {
    for (i = 3; i < 6; i++)
    {
    for (j = 0; j < 3; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    else if (y < 6)
    {
    for (i = 3; i < 6; i++)
    {
    for (j = 3; j < 6; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    else
    {
    for (i = 3; i < 6; i++)
    {
    for (j = 6; j < 9; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    }
    else
    {
    if (y < 3)
    {
    for (i = 6; i < 9; i++)
    {
    for (j = 0; j < 3; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    else if (y < 6)
    {
    for (i = 6; i < 9; i++)
    {
    for (j = 3; j < 6; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    else
    {
    for (i = 6; i < 9; i++)
    {
    for (j = 6; j < 9; j++)
    {
    if (value == outputArray[j])
    {
    return 0;
    }
    }
    }
    }
    }
    return value;
    }
    int backtrack(int x, int y)
    {
    int temp,i,j;
    if (outputArray[x][y] == 0)
    {
    for (i = 1; i < 10; i++)
    {
    temp = input_value(x,y,i);
    if (temp > 0)
    {
    outputArray[x][y] = temp;
    if (x == 8 && y == 8)
    {
    return 1;
    }
    else if (x == 8)
    {
    if (backtrack(0,y+1))
    return 1;
    } else {
    if (backtrack(x+1,y)) return 1 ;
    }
    }
    }
    if (i == 10) {
    if (outputArray[x][y] != array[x][y]) outputArray[x][y] = 0;
    return 0;
    }
    } else {
    if (x == 8 && y == 8) {
    return 1;
    } else if (x == 8) {
    if (backtrack(0,y+1)) return 1;
    } else {
    if (backtrack(x+1,y)) return 1;
    }
    }
    return 0;
    }
    void main()
    {
    clrscr();
    int i,j;
    cout<<"Original outputArray\n";
    for (i = 0; i < 9; i++)
    {
    for (j = 0; j < 9; j++)
    {
    cin>>array[j];
    }
    }
    clrscr();
    cout<<"Puzzle is \n";
    for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
    outputArray[j] = array[j];
    }
    }
    for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
    cout<<"\t"<<array[j];

    }
    cout<<"\n";
    }
    if (backtrack(0,0)) {
    cout<<"Soln is :\n";
    for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
    cout<<"\t"<< outputArray[j];
    }
    cout<<"\n";
    }
    } else
    cout<<"No Soln\n";
    getch();
    }
  12. This topic has been closed by Area51reopened
Ask a new question

Read More

Programming Apps Displays