Sign in to follow this  
Vortez

Sudoku Generation Algorithm - Need help

Recommended Posts

Hi, i've been reading this site http://davidbau.com/archives/2006/09/04/sudoku_generator.html about how to generate a sudoku grid, wich goes like this:

1. If only one number fits in a square without row, column, and box conflicts, we fill it in.
2. If a number needed by a row, column, or box can only go in one square in that row, column, or box, we fill it in.
3. If we can't fill in anything using rules 1 or 2, then we find a most-constrained place or number where we can guess (for example, two choices is better than three), and we try all the guesses.

But i don't understand the 3rd method. Anyone can explain plz?

Thx.

Share this post


Link to post
Share on other sites
1. for each row and column generate a random number between 1 and 9
2. make sure that number is valid (no other same number on the same row or column) otherwise keep generating
3. all fields are now filled but you consider them hidden, so depending on the sudoku difficulty start marking random fields as visible, but make sure you show the same number of fields in each 3x3 block

this should do it easily (hoping i didn't missed something)

Share this post


Link to post
Share on other sites
Even though the OP said "generate a sudoku grid", the algorithm he posted actually solves a given sudoku puzzle. The third rule is a backtracking step. I don't know what part of it you don't understand. But perhaps reading about some more straight-forward backtracking algorithms (e.g., depth-first tree search) would help you.

Share this post


Link to post
Share on other sites
OP, note above those three points in that HTML, there is a paragraph,

"First, we need a [b]Sudoku solver.[/b] My solver uses three simple strategies to solve a board; they are simple to implement and seem fast enough."

Share this post


Link to post
Share on other sites
The "most constrained" cells are the ones with the least possible values (i.e. most constrained by already known cells); they are the best choice for arbitrary guessing because if you guess wrong you eliminate a much larger portion of the potential solution space (e.g. half if possible numbers were 2, only one tenth for a completely unconstrained cell) and because the worst case number of attempts to fill that cell is smaller.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this