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.
Sudoku Generation Algorithm - Need help
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)
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)
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.
OP, note above those three points in that HTML, there is a paragraph,
"First, we need a Sudoku solver. My solver uses three simple strategies to solve a board; they are simple to implement and seem fast enough."
"First, we need a Sudoku solver. My solver uses three simple strategies to solve a board; they are simple to implement and seem fast enough."
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
