Thread: Sudoku Brute Force Algorithm Help (recursion?)

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    11

    Angry Sudoku Brute Force Algorithm Help (recursion?)

    Hi all,

    I'm writing a sudoku-solver program for an intro class in C. I'm not asking for anyone to do my homework, don't worry. The function that I'm struggling with ("solve") is one of many called in my main, so let me give you a little background.

    The user first inputs 81 values, which are indexed in a 9x9 array ("puzzle[PSIZE][PSIZE]" where PSIZE = 9).

    The next function called is "validate," which goes through the array and makes sure no value occurs twice in the same row, column or box, as per sudoku rules. If the puzzle is invalid, it returns 0 and main displays an error message, if valid, it returns the value and main continues.

    The main then calls the "setSingles" function, which replaces blank cells with a value, if that value is the only one that can go there, then repeats until it can find no more cells with this characteristic.

    Next, the main copies the "puzzle" array (after the single-value-cells have been replaced) to another array called "original". I'm not sure what to do with "original" yet, but it seems like a good idea to have it around.

    Now we get to the "solve" function I'm stuck on. It's basically the "brute-force" element of my program. You'll notice that it returns the data-type "stats", which is a user-created data type that I've created. It includes the statistics on how many times a value that the brute-force-algorithm tries to put in a cell doesn't work, and how many times the function hast to backtrack. I'm not worrying about this yet, so you shouldn't either!

    Here's a quick run-down on what it does:
    It takes the "puzzle" array, finds the first 0 (empty cell), and inputs a 1 into that cell. It then calls the validate function, and if that function returns a 0 (aka the puzzle isn't valid), it starts a loop that increments that 1 and validates until it finds a value that works. After a valid value is inputted, it copies the newly-changed "puzzle" array to another array called "last", along with two variables "rowlocation" and "collocation" that indicate which index was changed. It then moves on to the next empty cell.

    If it tries every value 1-9 in a cell, and none work (in my code, represented as if(puzzle[i][j] > PSIZE) ), it backtracks by going to the "last" array, incrementing the value that we previously changed by 1, then copying that to the puzzle array, and going back into the first loop. I've gotten this to work perfectly, I don't believe there's any problem with my code.

    My issue is this: I don't know how write code which accommodates cases in which we need to backtrack more than once, moving back more than one array. An idea of mine was that you could simply copy the puzzle array to a different "last" (last1, last2, etc) array after every successful cell-replacement, but i realize this is a super inefficient fix, and also, I have no idea of knowing how many arrays I may need. Also, I could always go back to the original, and increment by 1 the first cell I find that's been changed (provided this doesn't invalidate the puzzle), but I kind of suspect that this won't always work, plus, I get the idea that I'm supposed to be able to backtrack, not just start at the beginning.

    I think this gets into the issue of recursion, which I've read a little about, but don't really know much about.

    Oh, one thing to note is that we haven't yet covered pointers in class, and thus, there should be no need for them for this program.

    Any help? It would be greatly appreciated.

    Code:
    Stats
    solve(int puzzle[PSIZE][PSIZE], int original[PSIZE][PSIZE], Stats stats)
    {
       int i,
           j,
           value = 1,
           rowlocation,
           collocation,
           redo;
    
       int last[PSIZE][PSIZE];
    
       for(i = 0; i < PSIZE; i ++)
       {
          for(j = 0; j < PSIZE; j++)
          {
             if(puzzle[i][j] == 0)
             {
                puzzle[i][j] = value;
    
                redo = validate(puzzle);
                while(redo == 0)
                {
                   puzzle[i][j]++;
    
                   redo = validate(puzzle);
    
                   if(puzzle[i][j] > PSIZE)
                   {
                     last[rowlocation][collocation]++;
                     copy(last, puzzle);
                     redo = 0;
                    }
                }
                   rowlocation = i;
                   collocation = j;
    
                  copy(puzzle, last);
    
             }
          }
       }
       return(stats);
    }
    Last edited by ridilla; 05-06-2010 at 06:48 PM. Reason: had to subscribe!

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    One easy way you could do the recursion is like this. Maintain just one puzzle[][] array, which is initially filled with the inital values. Then try setting the first unknown element to 1, 2, ..., 9 and validating (obviously you can, and should, do this more intelligently, but you can figure that out later). Every time you change one cell, perform the recursion. When the recursion returns, reset the cell.

    You see, the idea with recursion is that you change the problem you're asked to solve into a slightly smaller subproblem, and then call the same function again. As long as you always make the problem "smaller" for some sense of the word, you'll eventually hit a base case that's really easy to solve. (In this case, a base case could be a board with all of the cells known.)

    So anyway, the idea might look something like this:
    Code:
    solve(puzzle[][]) {
        if all cells are known, return success immediately
    
        for each unknown cell (x, y):
            for each possible digit 1..9:
                try setting puzzle[x][y] = digit
                if(valid(puzzle)) solve(puzzle)
                puzzle[x][y] = unknown
    }
    Let me know if that is confusing.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    11
    Thanks for the quick reply, I am a little confused though, concerning the statement "puzzle[x][y] = unknown". Is that part of the if statement? What's its purpose? I'm trying to follow the flow of execution and I kind of get lost. I see that if it's valid, it starts the solve puzzle function again and it will begin at the next unknown cell, eventually getting to the end. But what if none of the values 1 - 9 work?

    Code:
    solve(puzzle[][]) {
        if all cells are known, return success immediately
    
        for each unknown cell (x, y):
            for each possible digit 1..9:
                try setting puzzle[x][y] = digit
                if(valid(puzzle)) solve(puzzle)
                puzzle[x][y] = unknown
    }

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    You can see the puzzle solution space as a tree. If you try a '3' here, you go down this branch of the tree; if you try a '4' here, you go down another branch. Probably the vast majority of the branches will be dead ends (that is, you won't find a solution to the puzzle), but if you're doing a brute force search you need to visit all of them.

    [Side note: in the worst case this will take 9 tries per cell, over 81 cells, or 9^81 different boards that you're looking at. That's 1.9662705x10^77 boards, which is way too many -- so you'll definitely have to do something smarter in the long run.]

    Anyway, I was talking about trees. So every recursive call to the function will visit another branch of the tree. Then it will visit all possible solutions from there and return. At this point you have to reset the board so that you can visit another branch of the tree. That's the purpose of the "puzzle[x][y] = unknown" line (it's outside the if statement). Since the code just set puzzle[x][y] to try one branch of the tree, and the recursion checked all branches that lead out from there, it's time to try something else, so reset what you just tried and start with something else.

    Incidentally, I wrote a sudoku solver once, a very long time ago. All it did was look at the board, and try to apply various heuistics to come up with a correct answer. (e.g., if there is only one unknown cell in a row or column, you can immediately figure out what it is.) The point of Sudoku puzzles, of course, is that *you never need to guess*. There is only one solution. That's why brute force really doesn't make much sense in this case.

    To get on with the story: I programmed in a bunch of heuristics, and the program would try applying each one in turn; as soon as one succeeded, it would start going through the list again (because the board would have changed by this point). It was fairly good at solving puzzles -- well, almost exactly as good as I was, because I only coded the heuristics that I knew about. I could dig my program up if you're interested, but it's really more fun to write it yourself.

    By the way, an analogous problem is solving a maze. Let's say you have a starting point, a finishing point, and lots of dead ends, and you can move north, west, south, and east. To solve the maze, you want to keep track of where you've been (so that the program doesn't lock into an infinite loop). You want to try one direction, then if that doesn't work, try another direction. Sample code (I'll put braces in this time) to solve this might look like
    Code:
    enum {
        EMPTY,
        WALL,
        VISITED,
        GOAL
    };
    
    /**
        @param board Each cell of the board is EMPTY if it could be visited,
            VISITED if it has already been visited, and WALL if it cannot be visited.
    */
    void solve_maze(char board[WIDTH][HEIGHT], int xp, int yp) {
        // base case: already at the goal
        if(board[xp][yp] == GOAL) {
            // found solution
        }
        
        try_direction(board, xp-1, yp);
        try_direction(board, xp+1, yp);
        try_direction(board, xp, yp-1);
        try_direction(board, xp, yp+1);
    }
    
    void try_direction(char board[WIDTH][HEIGHT], int xp, int yp) {
        // make sure position is valid
        if(xp < 0 || yp < 0 || xp >= WIDTH || yp >= height) return;
    
        if(board[xp][yp] == EMPTY) {
            board[xp][yp] = VISITED;
            solve_maze(board, xp, yp);
            board[xp][yp] = EMPTY;  // reset map to try next direction
        }
    }
    Hmm, that ended up looking more like code than it needed to. Anyway, hopefully it gets the point across. You try one direction (if EMPTY) and take note that you've visited there (set to VISITED); then recurse to try everything from there on; and then the recursion returns so you backtrack (reset to EMPTY) and try some other direction.

    Is that any less confusing?

    [edit] Code coloured with codeform, by the way. http://dwks.theprogrammingsite.com/myprogs/cfonline.htm [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by dwks View Post
    You can see the puzzle solution space as a tree. If you try a '3' here, you go down this branch of the tree; if you try a '4' here, you go down another branch. Probably the vast majority of the branches will be dead ends (that is, you won't find a solution to the puzzle), but if you're doing a brute force search you need to visit all of them.

    [Side note: in the worst case this will take 9 tries per cell, over 81 cells, or 9^81 different boards that you're looking at. That's 1.9662705x10^77 boards, which is way too many -- so you'll definitely have to do something smarter in the long run.]

    Anyway, I was talking about trees. So every recursive call to the function will visit another branch of the tree. Then it will visit all possible solutions from there and return. At this point you have to reset the board so that you can visit another branch of the tree. That's the purpose of the "puzzle[x][y] = unknown" line (it's outside the if statement). Since the code just set puzzle[x][y] to try one branch of the tree, and the recursion checked all branches that lead out from there, it's time to try something else, so reset what you just tried and start with something else.

    Incidentally, I wrote a sudoku solver once, a very long time ago. All it did was look at the board, and try to apply various heuistics to come up with a correct answer. (e.g., if there is only one unknown cell in a row or column, you can immediately figure out what it is.) The point of Sudoku puzzles, of course, is that *you never need to guess*. There is only one solution. That's why brute force really doesn't make much sense in this case.

    To get on with the story: I programmed in a bunch of heuristics, and the program would try applying each one in turn; as soon as one succeeded, it would start going through the list again (because the board would have changed by this point). It was fairly good at solving puzzles -- well, almost exactly as good as I was, because I only coded the heuristics that I knew about. I could dig my program up if you're interested, but it's really more fun to write it yourself.

    By the way, an analogous problem is solving a maze. Let's say you have a starting point, a finishing point, and lots of dead ends, and you can move north, west, south, and east. To solve the maze, you want to keep track of where you've been (so that the program doesn't lock into an infinite loop). You want to try one direction, then if that doesn't work, try another direction. Sample code (I'll put braces in this time) to solve this might look like
    Code:
    enum {
        EMPTY,
        WALL,
        VISITED,
        GOAL
    };
    
    /**
        @param board Each cell of the board is EMPTY if it could be visited,
            VISITED if it has already been visited, and WALL if it cannot be visited.
    */
    void solve_maze(char board[WIDTH][HEIGHT], int xp, int yp) {
        // base case: already at the goal
        if(board[xp][yp] == GOAL) {
            // found solution
        }
        
        try_direction(board, xp-1, yp);
        try_direction(board, xp+1, yp);
        try_direction(board, xp, yp-1);
        try_direction(board, xp, yp+1);
    }
    
    void try_direction(char board[WIDTH][HEIGHT], int xp, int yp) {
        // make sure position is valid
        if(xp < 0 || yp < 0 || xp >= WIDTH || yp >= height) return;
    
        if(board[xp][yp] == EMPTY) {
            board[xp][yp] = VISITED;
            solve_maze(board, xp, yp);
            board[xp][yp] = EMPTY;  // reset map to try next direction
        }
    }
    Hmm, that ended up looking more like code than it needed to. Anyway, hopefully it gets the point across. You try one direction (if EMPTY) and take note that you've visited there (set to VISITED); then recurse to try everything from there on; and then the recursion returns so you backtrack (reset to EMPTY) and try some other direction.

    Is that any less confusing?

    [edit] Code coloured with codeform, by the way. http://dwks.theprogrammingsite.com/myprogs/cfonline.htm [/edit]
    It's way less than 9^81 because you are not taking into account number repetitions. The number of possibilities is more along the lines of 6.67 x 10^21.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, that's true for unique boards, but if you do the silly generation method of "pick every number from 1 to 9, recurse" then you will end up with 9^81 boards -- unless you do some validation along the way, which would be smart, of course. With minimal effort you should be able to bring it down to the number you mentioned . . . .

    . . . which is still way too many to brute force, I think. Perhaps you could do it if you gave the program quite a few numbers to begin with.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Bookmark this:
    Sudoku Programmers :: Index

    It's not busy, and not oriented for beginners, but just reading there, you could learn (or just be amazed by) some subtleties of Sudoku and programming for it.

    You won't need your original grid in the brute forcer function, because there is no need to use it. If the answer lies within the set of the space that is being searched, it WILL be found, by going forward.

    consider a row, by itself:
    Code:
    | 1 ? 3 | 4 ? 6 | 7 ? 9 |
    And for this example, let's assume we could get no other info on what the possible digits for the ? squares, could be, except the obvious:

    The answer lies in this search set:
    258
    285
    528
    582
    825
    852

    Before we finish searching this set (and testing of course), we will find the correct answer to the row, above, (or, in a full puzzle, we may find that no answer is possible).

    So in the solver, we set sqr 2 = 1, and that fails, then we increment sqr 2 to 2, and it succeeds. Go down one level and work with sqr 5. We set it for 1,2,3,4,5,6.7,8,9 (because our brute forcer is very basic and not too smart yet), and they all fail because of conflicts with the rest of the puzzle. So it returns up, one level. Now we set #2 to 3,4 - and they fail, but 5 succeeds, so we go down one level, and we're back to testing #5 sqr. 1 fails, but 2 succeeds, so we go down another level, and we're testing sqr #8.

    How would the testing for square #8 go? Using this simplified example, can you code up a recursive function that will solve this row?

    Let's say the correct answer is square 2 = 5, sqr 5 = 2, and sqr 8 = 8.

    Try and find that with a recursive function, and forget (for now), the rest of your program. This will have to be the heart of your program, since your logic is very sparse. (and no amount of logic will solve every single puzzle - although they are getting close).

  8. #8
    Registered User
    Join Date
    May 2010
    Posts
    11
    Thanks again for the response.

    Your recursion makes sense to me now, but I still can't seem to get it to work. Here's what I've coded

    Code:
    Stats
    solve(int puzzle[PSIZE][PSIZE], int original[PSIZE][PSIZE], Stats stats)
    {
       int i,
           j,
           k,
           zerocount = 0;
          
       /* CHECKS TO SEE IF THE PUZZLE IS ALREADY COMPLETED */
       for(i = 0; i < PSIZE; i ++)
       {
          for(j = 0; j < PSIZE; j++)
          {
             if(puzzle[i][j] == 0)
             {
                zerocount++;
                if(zerocount == 0)
                {
                   return(stats);
                }
             }
          }
       }
       
       /* INPUTS VALUES */ 
       for(i = 0; i < PSIZE; i++)
       {
           for(j = 0; j < PSIZE; j++)
           {
               if(puzzle[i][j] == 0)
               {
    
                for(k=1; k < 10; k++)
                 {
                     puzzle[i][j] = k;
    
                     redo = validate(puzzle);
                     if(redo !=0)
                     {
                         solve(puzzle, last, stats);
                      }
                      puzzle[i][j] = 0;
                      }
                   }
               }
           }
       return(stats);
    }
    That gives me an infinite loop. One suspicion I have: when you set puzzle[i][j] to "unknown" (the same as 0, right?), is that enough? Or do you have to set the whole array back to how it was before it started going down the other branches?

    Also, Sudokus can have more than one solution, can't they? I realize that the ones in the newspapers only have one, but if you presented someone with a blank nine-by-nine grid, or one with one value, that's a valid sudoku, and has more than one solution. That's why the brute-force equation is necessary. Also, my professor wants us to write it using first the set-singles algorithm as a function, then moving on to the brute force method.

    One more thing to consider: as I stated, this is an assignment for class, and the header files were given to us, and our teacher expects us to write functions that make use of the inputs, and spit out the same outputs. Any idea how to use the "original" array that was inputted? Remember, it's the same as puzzle[][] before puzzle gets passed to "solve" and changed.

  9. #9
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    I hate Sudoku and I honestly don't understand why Sudoku algorithmics are of any importance whatsoever besides personal fun! ... Then again I am lazy so forgive my ingnorance!
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by dwks View Post
    Well, that's true for unique boards, but if you do the silly generation method of "pick every number from 1 to 9, recurse" then you will end up with 9^81 boards -- unless you do some validation along the way, which would be smart, of course. With minimal effort you should be able to bring it down to the number you mentioned . . . .

    . . . which is still way too many to brute force, I think. Perhaps you could do it if you gave the program quite a few numbers to begin with.
    Yeah I definitely agree that brute force is a poor option here. Apparently there are several approaches that deal with Sudoku solving however, I am far from experienced in any of these so I wouldn't know
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Sudoku programs (beyond the most basic one's), keep a list of possible digits, for each sqr. So the actual number of combinations that have to be checked is kept way down.

    Naked singles and doubles are handled by logic, first (at least). Some programs do a lot more.

    Thanks to a lot of optimizations, brute force solving can be quite fast. Those using bit fields, and those using Knuth's "Dancing Links", algo, are currently, the fastest brute force solvers.

    A PROPER sudoku puzzle has just one solution, but many that you see, are not checked for that, and they can have MANY (thousands in some cases), of valid solutions. Such puzzles with multiple solutions are generally despised by Sudoka's.
    Last edited by Adak; 05-06-2010 at 08:51 PM.

  12. #12
    Registered User
    Join Date
    May 2010
    Posts
    11
    Adak: here's my code. I'm assuming that the row array has already been populated with the values you posted, that your question marks are the same thing as zeroes and that the "validate" function will return 0 if the board is invalid.

    Code:
    void
    solve(row[9])
    {
    
       int i,j;
    
       for(i = 0; i < 9; i++)
       {
          if(row[i] = 0)
          {
             for(j = 1; j < 10; j++)
             {
                row[i] = j;
                if(validate(row))
                {
                   solve(row);
                 }
             }
          }
       }
    return;
    }
    Question: what happens if there's no possible value for a cell? Imagine a sudoku where the first row is 12345678? and the last row is ????????9. Is that simply an unsolvable problem?
    Last edited by ridilla; 05-06-2010 at 08:57 PM. Reason: had to change some braces!

  13. #13
    Registered User
    Join Date
    May 2010
    Posts
    11
    quick correction to that, it should say if(row[i] == 0), not if(row[i] = 0)

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Right, that is an illegal grid for Sudoku.

    What's with all the loops? You are trying to solve ONE square, on ONE row.

    Good advice:
    Code:
    Use the force (of the recursive "loops"), Luke!
    Simple (sparse even), is best, and fast too. Don't go "Rube Goldberg" on this.
    Last edited by Adak; 05-06-2010 at 09:07 PM.

  15. #15
    Registered User
    Join Date
    May 2010
    Posts
    11
    the loops seem necessary to me, here's my reasoning. hopefully you can tell me why they're not necessary.

    the first loop is necessary to progress through the row, provided both sub-levels turn out to be valid. The second loop increments the value each time a non-valid entry is tried. I suppose you could also use row[i]++, but then how would the machine know to stop at 9? Would you have to write an out for that?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Running a Brute Force Attack Simulation...
    By Junior89 in forum C++ Programming
    Replies: 31
    Last Post: 02-13-2011, 08:52 PM
  2. 2d array Brute force test
    By grimuth in forum C++ Programming
    Replies: 5
    Last Post: 04-08-2010, 10:01 AM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

Tags for this Thread