Any guru here can explain algorithm for Sudoku?

[dullboy]

I posted it in algorithm forum but it is too quiet there so I decide to post it here. After all I am planning to implment it using C++. The algorithm includes sudoku solver, sudoku generator and difficulty analysis. I searched online but the algorithm is still not clear to me . Please help me by explaining the algorithm step by step. Thanks for your inputs.

[monarch_dodra]

There are basically 2 algorithms:
1 - Brute force.
This is easy: just place numbers as as you can, and if you see that the sodoku can't be solved, just backtrack and try the next number. This is actually very easy to implement.
2 - Smart methods. This is much harder. You basically have to translate in code what you do in your head when you solve by hand.

Regardless of algorithm, what counts is how you model your sudoku.

I'd recommend a class that wraps a 9x9 grid of placed values, and a 9x9x9 boolean grid that represents legal values that an empty cell can hold.

[dullboy]

Thanks for your response. I like to start from the easy one: brute force. Can you explain more how to backtrack once the placed number can't solve the sudoku? Thanks for your inputs.

There are basically 2 algorithms:
1 - Brute force.
This is easy: just place numbers as as you can, and if you see that the sodoku can't be solved, just backtrack and try the next number. This is actually very easy to implement.
2 - Smart methods. This is much harder. You basically have to translate in code what you do in your head when you solve by hand.

Regardless of algorithm, what counts is how you model your sudoku.

I'd recommend a class that wraps a 9x9 grid of placed values, and a 9x9x9 boolean grid that represents legal values that an empty cell can hold.

[Paul McKenzie]

Thanks for your response. I like to start from the easy one: brute force. Can you explain more how to backtrack once the placed number can't solve the sudoku? Thanks for your inputs.

The same way if you did this technique by hand.

You start out with a board of numbers, and then starting from the first empty square, you try the first available number. If the board is OK, that number you chose is no longer available and you go to the next square, try the first available number. If the board is still OK, etc. etc.

If you get to a square where no available number works so that the board is in a valid state, you go back one square and start from that square, remove the number you tried, and, try the next available number. If that square can't be corrected, you go back to the square before that and make a correction, etc.

That is called backtracking -- you go back one square and make the correction because the current square you're trying doesn't make the board valid, regardless of the number you have chosen.

It is easy to implement, but very slow to execute. All you're doing is trying a number, checking the board, and then either going back a square (if the board is invalid no matter what number you choose), or you go forward to the next square if the board is still OK.

Regards,

Paul McKenzie

[kempofighter]

I think that he means start over from cell 1 and repeat algorithm. I could be wrong. Solving suduko manually, I usually start with the upper left corner and start analyzing cells until I find one where I can fill in the value. Once you get from start to finish and have filled in a bunch you repeat. By then some others will become obvious. You know the rules of the game so the brute force method is not that hard. Every cell belongs to a 3x3 table, row, and column.

Actually that isn't entirely true as far as what I do manually. I do that for the really hard ones but for some of the easier ones I can just glance at the table and recognize immediately some areas of the puzzle that I can fill in quickly. I think that the harder algorithm would have to have some way of quickly identifying the areas that can be filled in more easily where brute force you start from one end and analyze every cell until finished regardless of the initial gameboard and then repeat until the game is complete.

[dullboy]

The same way if you did this technique by hand.

You start out with a board of numbers, and then starting from the first empty square, you try the first available number. If the board is OK, that number you chose is no longer available and you go to the next square, try the first available number. If the board is still OK, etc. etc.

If you get to a square where no available number works so that the board is in a valid state, you go back one square and start from that square, remove the number you tried, and, try the next available number. If that square can't be corrected, you go back to the square before that and make a correction, etc.

That is called backtracking -- you go back one square and make the correction because the current square you're trying doesn't make the board valid, regardless of the number you have chosen.

It is easy to implement, but very slow to execute. All you're doing is trying a number, checking the board, and then either going back a square (if the board is invalid no matter what number you choose), or you go forward to the next square if the board is still OK.

Regards,

Paul McKenzie

Thanks for your response. I like to start from Solver algorithm first, which means the board is totally empty when I start. I tried brute force by hand and I think it would be very slow. For example, I select 1 for first square and 2 for second square and .... Probably I don't realize 2 for second square is wrong until I try to fill in 75th square. And then I have to backtrack to second square and do it all over again. How does the smart way work? Thanks for your inputs.

[GCDEF]

I think that he means start over from cell 1 and repeat algorithm.

Backtracking algorithms don't usually start over. It makes sense to go as far as you can but only back up the least amount necessary to avoid the dead end.

[monarch_dodra]

Last time I tried brute solving an empty sudoku, it was pretty much instantaneous, so performance is not really an issue.

It is the back-tracking that's actually "kind of" hard. I found that the easiest way to do it is to create a new copy of your entire sudoku every time you place a number. If after a while you see your sudoku is bad, you just pop your last sudoku, and try with the next number.

The "smart" algorithms consists in trying to find 100% sure numbers. For examples, if inside a single cell, the only legal value is 3, then you know you have to place a 3 inside that cell.

Or, you can scan a row, and if only a single cell allows 3, then you know 3 is inside that row. (or column, or square).

But again, I stress that the smart method is harder.

[dullboy]

Last time I tried brute solving an empty sudoku, it was pretty much instantaneous, so performance is not really an issue.

It is the back-tracking that's actually "kind of" hard. I found that the easiest way to do it is to create a new copy of your entire sudoku every time you place a number. If after a while you see your sudoku is bad, you just pop your last sudoku, and try with the next number.

The "smart" algorithms consists in trying to find 100% sure numbers. For examples, if inside a single cell, the only legal value is 3, then you know you have to place a 3 inside that cell.

Or, you can scan a row, and if only a single cell allows 3, then you know 3 is inside that row. (or column, or square).

But again, I stress that the smart method is harder.

Can you explain the algorithm for sudoku generator based on a solved sudoku? I know we can also use back track but don't know how? Thanks for your inputs.

[dullboy]

I have created a Sudoku generator. But my generator can at least leave 30 numbers on board. So I guess I need to strength my algorithm in order to improve its difficulty level. Can we discuss how to refine the algorithm? Thanks for your inputs.