Thread: Explain sudoku brute force algorithm

Get a pencil and some paper, draw a 3x3 grid and randomly place say 2,4,6,8,3,5 (leaving 1,7,9) in the boxes.

Now run through the description above.


Have you actually tried to solve any sudoku puzzles, or is it just an abstract concept to you?

Mr. Salem,
I think you mis understood..
To be specific about where I am little bit confused ...
look here..
If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell."

Take a random sudoku and Imagine you placed a number 3 there.. and went to next empty cell where none of 9 digits is allowed...
according to the above line, it goes back to 3 and is incremented by 1. how could I possibly do that without checking the rules to increment it..

I might definitely wrong in understanding that.. can you clear that..

Originally Posted by suryak

Do you mean.. I should check the other possible value in the cell that can be placed when I get back to previous cell or I should add (+1 to the number )..
ex: is 3 is present.. ( I should place 3 + 1 = 4 or next possible number.. )

Example assuming 3 is the only currently allowed number for that cell:
You check what number is there currently. You find 3. You check if 4..9 is allowed, none are.. Clear the cell and move back a step.
You find a 4. You check if 5 is allowed. It is. You move forward one cell.
You are back at the problem cell. You check 1..9 if any are allowed. Now you find that 4 is allowed. Move forward one step. Repeat..
If you ever get to the starting position and find that you have to increment a 9 then either the board is badly constructed or you made a mistake in your algorithm.

Edit/Update:

Not having tried anything similar before I decided to try writing a solver..

First attempt)
After looking over the code and thinking it was okey I ran it against an empty board..
"No solution possible"
Simple beginner's mistake. I was doing an assignment where I meant to do a comparison

Second attempt)
Empty board works fine. And so did some other simple boards I tried, so I decided to let my solver loose against wikipedia's "worst case" scenario.
Wikipedia claims it should take 30-45 minutes with their algorithm on a 3ghz cpu so I was estimating maybe 2 times longer than that, because of a 1.7ghz laptop and unoptimized code.
After about an hour running I discovered that my simple sudoku solver was in fact a very complex endless loop.
It was another typo in a comparison. '<' instead of '>'. It only triggered the bug in very specific cases so I never spotted it in my previous testing.

Third attempt)
Success! 62 seconds!
Either the evolution of optimizing compilers has made huge leaps since that wikipedia article was written, or it isn't a worst case scenario at all.
It's quite amazing the feeling of bliss you get when you manage to complete a project and get very unexpected positive results
Now to try and make it multi-threaded..

Originally Posted by _Mike

Now to try and make it multi-threaded..

I wouldn't bother. A good backtracking solver can solve a 9x9 board in about 4 milliseconds or less as it is. Surely that's fast enough.