Explain sudoku brute force algorithm

can you explain the sudoku brute force algorithm in detail please ( Not Code).

I read the algorithm in wikipedia : Sudoku algorithms - Wikipedia, the free encyclopedia
but still missing something.

In wikipedia, they said that :

" Briefly, a brute force program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell, and places a "1" in that cell. When checking for violations, it is discovered that the "1" is not allowed, so the value is advanced to a "2". 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."

this specific part I'm not clear about..

can you please explain . .

Also if you could, please try to explain backtracking algorithm...

and finally which one best brute force or backtracking

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..

Quote:

---

Originally Posted by suryak

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..

---

You have to check the rules when incrementing it. Then if you find that no other number is allowed you move back one more step and start incrementing again.

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.. )

Your program could have a list of possibles, for every unsolved square, and only consider those. Or you could go "whole hog" with brute force, and just increment and check, increment and check, increment and check.

It's quite surprising how few lines of code you need, for a very simple brute force solver. Sudoku is full of subtle clues for human solvers, but a brute force solver can be a real simpleton.

Sudoku solving with a program is a lot of fun. There are SO many little tricks you can use to speed up your solver, once you get to know the puzzle (and programming better).

And then there is Knuth's "Dancing Links"/"Algorithm X", which is such a beauty, but mind-blowing, as well.

Working with a 4 X 4 mini board, is a great way to start. Big thumbs up on that!

Quote:

---

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 :D
Now to try and make it multi-threaded..

Quote:

---

Now to try and make it multi-threaded..

---

Nice idea.
Would having them follow totally different (never crossing) paths be sufficient to ensure that the solution is correct?

Quote:

---

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.

Quote:

---

Originally Posted by iMalc

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.

---

I know. But it might be a good learning experience. I've never done any multi threading programming before.