sudoku solver

> is it best to use a 2D array to do this

Always difficult to call something the best way to solve something. But if I'd create a Sudoku puzzle or application to solve a Sudoku, I'd indeed use a class named Grid which holds a 2D array of Cell objects.

> and how does recurrsion help in solving this?

I don't understand: recusrion is just a technique to solve it.

There's a nice opensource project at Sourceforge: http://sudoku.sourceforge.net/

You can download the source and have a peek to see how they did it.

prometheuzza at 2007-7-13 8:30:34 >

Recursion isn't just used for brute force methods. I wrote a SuDoku solver that doesn't use brute force. For most puzzles, it can solve them without having to resort to recursion. For very difficult ones, it gets to a state where it cannot make any more progress. In these cases, I resort to recursion. It takes the first square where two choices are possible and picks one of those choices and generates a new SuDoku puzzle which has all the grids which have been fixed so far and this one guess filled in and attempts to solve this new puzzle. If this new puzzle is solved, it is the solution to the original one. If this new puzzle reaches an unsolvable state, it was a wrong guess and you go back to the original puzzle and try the other number that could have gone into that grid.

My original algorithm immediately allowed for n levels of recursion. This was a bad idea because you can spend a lot of time pursuing a bad guess. I changed it to open up one level at a time and now it can solve anything very quickly. By opening up one level at a time, I mean that it will check all squares which can take one of two values first before it allows recursion to a third level where one of the puzzles generated as a guess can generate another guess puzzle. I made this change to the algorithm early on and since then I haven't seen a puzzle that had to go beyond level 3. I used the "evil" category puzzles from the www.websudoku.com to test the program.

Gita_Weinera at 2007-7-13 8:30:34 >

>I wrote a SuDoku solver that doesn't use brute force. (Good!)

But in my post I mentioned clearly, "One way to Solve Sudoku puzzle is to use 'Brute Force' algorithm."

Brute force recursive method tries all possibilities to solve the puzzle and this technique is more natural. But for sure, you can do it in your own way.

An Algorithm For 9*9 grid Sudoku Puzzle:

solve(int location)

If location == gridSize // puzzle has been solved

display_solution;

return true;

else

Check each integer v between 1 and 9

if v is OK in location //meaning that row, col and square conditions are met

set location to v

return solve(nextEmptyLocation(l))

else return false

Thank You!

buteForcea at 2007-7-13 8:30:34 >

>I don't see how this algorithm can work.

The same chunk of key recursive algorithm worked for us, when Sudoku was our Java assignment. But, we had to refine it before get it working.

>When you get to that location, what do you do when you find that the only OK number has already been used?

Very simple try another possibility.

>>>More questions about solving Sudoku using a brute force recursive method?

Please Google it.

Thanx.

buteForcea at 2007-7-13 8:30:34 >

I just did this for a Compsci project, and it the algorithm isn't really too bad if the Sudoku is well formed.

My code was pretty inefficient, but it worked, and fast.

I started with a multidimensional array consisting of row, column, and then another array of values 0-9. When reading my input, 0 was unknown.

I read in the file one row at a time, removing the value (if not = 0) from every cell in the same row, column, and 3*3 square it was in.

After reading in my file, there were several squares that could "only" be a certain number - say, 0 and 5 - it would have to be 5.

Loop your algorithm and remove these values as they are added.

If the puzzle is misformed or there are multiple solutions, then go recursive. Try a value from your "possible" list and see if you can solve the puzzle using it. If not, try the next, and so on.

It seems daunting at first, but with some good commenting, the code isn't too bad.

Siegelja at 2007-7-13 8:30:34 >

I've also writen a Sudoku solver that solves just about any puzzle very quickly.I also have 0 indicating empty cells. Basically I have a large while loop that keeps going as long as progress is being made. Within the loop, it calls methods to do the following:

1. Check each empty cell to see if only one number can be placed into it. If that is the case, put that number into the cell.

2. Loop through all the rows, columns and subgrids. For each such unit, see if any of the number which haven't yet been placed into the unit, can only go into one cell. If you find any such number, place them into that cell.

3. Loop through all the rows, columns and subgrids and see if any two numbers which haven't yet been placed into that unit are both only allowed in the same two cells. If it finds this situation, it means that both these cells must hold one of these two number and therefore can't hold any other numbers. Now check if numbers which are no longer possible in these two cells are now only possible in one other cell in this unit.If it finds a number which is now only possible in one other cell in the unit, place it into that cell.

For most puzzles (all except the most difficult), this logic will solve the puzzle and the loop will be exited when the puzzle is solved. For very difficult puzzles, this logic is insufficient and I had to resort to recursion. If it goes through the loop once without making further progress, it falls out and tries recursion. What is does is generate a new puzzle whose initial state is the current state of the puzzle plus one extra square filled in. It takes the squares with 2 possible values and starts trying them as the extra square. It only opens up one level of recursion at a time to avoid wasting a lot of time on a wrong guess.

Gita_Weinera at 2007-7-13 8:30:34 >

Using the na飗e brute force paradigm is far more inefficient than other techniques.

Excellent and efficient open source sudoku solvers:

http://www.stolaf.edu/people/hansonr/sudoku/

http://www.sudokusolver.co.uk/

You may get tips on programming sudoku here: http://www.setbb.com/phpbb/?mforum=sudoku

alta at 2007-7-13 8:30:34 >