please wait
- Forum
- General C++ Programming
- backtracking algorithm
backtracking algorithm
Jun 10, 2009 at 2:24amHi,
Need help with some code for a backtracking algorithm to solve sudoku puzzles. Been searching far and wide and all I have come across are a 1000 other people asking the question only to be given the "man, that's every where. All over the internet, just go and find it". All I see it's lots of talk, no action! The code, or at least a very in depth description of the code has been swallowed by all these other requests/replies. I've been to Wiki and this doesn't really explain it well enough for me.
I recently went to a job interview where I was asked to read a sudoku puzzle from a file, solve it, write it back to file. ime limit was 4 hours.
Here's what I did:
1. Read sudoku puzzle into 3D array (9 rows, 10 depth, 9 cols)
2. Traverse the suduku puzzle which is the front 2D array. Each cell behind the fron grid contains all the possible values of the the cell at the front (the actual puzzle)
3. Everytime I traversed the grid I check the row, the col, and the area (the little 3x3 square) and any numbers that were present got changed to zero in the depth array sitting behind the cell on the grid. Then there is a check if the depth array has 8 zeros. If true the number left over is assigned to the cell on the front grid (the puzzle). This is wrapped in a do while loop until it is solved
4. Write back to file
It works for simple sudoku puzzles. But as soon as you get a harder puzzle that needs to try different combinations of numbers, it won't work. Suffice to say I didn't get the job.
I then went to the internet and learnt that a recursive backtracking algorithm needs to be used. Also leant that it's quite common and can be used for 8-Queens problem and Knapsack problem. Done a lot of searching but can't find one.
Can anyone help me?
Also, apart from the backtracking algorithm, is there a better way structurally to solve sudoku puzzles? I did consider make a class called Grid that holds a 2D array and then another class called PossibleNumbers. Possible number holds a 1D array holding the possible numbers for each cell. A loop would traverse the 2D array and each time instantiate an object of Possible Numbers. Is this a better way of doing it?
Jun 10, 2009 at 2:52am
Instead of using an array for PossibleNumbers, I'd use a bitset.
I wrote this exact program. It solved top-left to bottom-right, columns first then rows. Using the brute-force approach I found that the program would solve any puzzle I fed to it virtually instantaneously, so I didn't think it was necessary to implement any more heuristics (of which there are many).
Basically, you have a function that is given the grid and a cell. The function computes what values could possibly go in the cell. It then puts the first number in the cell and calls itself recursively with the modified grid and the next open cell. If the function call returned, it meant that the grid was unsolvable, so it then tried the next number, and so forth until it was solved. In my simplistic implementation, I basically had to throw an exception when the grid was solved, as that was the only way to unwind the stack at that point.
I wrote this exact program. It solved top-left to bottom-right, columns first then rows. Using the brute-force approach I found that the program would solve any puzzle I fed to it virtually instantaneously, so I didn't think it was necessary to implement any more heuristics (of which there are many).
Basically, you have a function that is given the grid and a cell. The function computes what values could possibly go in the cell. It then puts the first number in the cell and calls itself recursively with the modified grid and the next open cell. If the function call returned, it meant that the grid was unsolvable, so it then tried the next number, and so forth until it was solved. In my simplistic implementation, I basically had to throw an exception when the grid was solved, as that was the only way to unwind the stack at that point.
Jun 10, 2009 at 3:27am
excellent. Thanks both for the replies. Looks like exactly what I'm after.
Jun 10, 2009 at 4:30am
hey guys, I am a lover of sudoku too.
:)) I got the main idea of your algorithm - I have been hovering around that idea too - can you post some code? I would gladly read it, if it is no secret!
| Using the brute-force approach I found that the program would solve any puzzle I fed to it virtually instantaneously |
:)) I got the main idea of your algorithm - I have been hovering around that idea too - can you post some code? I would gladly read it, if it is no secret!
Jun 10, 2009 at 12:05pm
Last night while I couldn't fall asleep, I was thinking that a randomized solver on an empty matrix could be used as a generator.
Jun 11, 2009 at 7:19pm
Wow, rough interview. I wonder what it was for. Who cares about solving suduko puzzles? Sounds like something one would do for fun in their spare time but what good is it?
Jun 11, 2009 at 7:54pm
It's actually not such a bad idea to gauge how much the programmer knows.
If he has some experience with recursion, he should be able to put a brute force solve together in two hours, at most. I wrote one yesterday in 1 hour. 100 lines, give or take. I could have taken 30 minutes, but I was missing a *3 in the check() routine and spent the other thirty minutes debugging the wrong function.
Like jsmith said, brute force can solve any solvable set almost immediately. Mine solved Wikipedia's "near worst case" in thirty seconds on my computer.
Remember kids: http://www.busindre.com/archivos/bruteforce.jpg
If he has some experience with recursion, he should be able to put a brute force solve together in two hours, at most. I wrote one yesterday in 1 hour. 100 lines, give or take. I could have taken 30 minutes, but I was missing a *3 in the check() routine and spent the other thirty minutes debugging the wrong function.
Like jsmith said, brute force can solve any solvable set almost immediately. Mine solved Wikipedia's "near worst case" in thirty seconds on my computer.
Remember kids: http://www.busindre.com/archivos/bruteforce.jpg
Last edited on Jun 11, 2009 at 8:01pm
Jun 12, 2009 at 9:23am
It was for a grad position. I can't complain as obviously a better coder than myself could do it and that's what they were after. I did have some experience with recursion but obviously not enough. I didn't immediately recognise this as being able to be solved recursively. I was more thinking along the lines of replicating how I solve the puzzles manually. They also wanted me to read in a file and write back to file. I usually just copy and paste my standard read/write code and tweak it accordingly. Does anyone write this sort of code from scratch rather than just c&p it from another project?
Topic archived. No new replies allowed.