Sudoku: strategy for generating boards?

Hi,
I think there is no need to have such a complex data structure as
you have described. All you need is a 9x9 array of integers to
represent the board. You an initialize the board by assigning zero
value to all the elements suggesting that the board is empty. Now as
you said, lets assume that you want to make a board where "N"
random board positions are occupied (in accordance to all the rules).

You can start with first randomly selecting the board positions that
will be filled, and saving the locations (a 2 dimensional array of
length "N" will do it). Now we will try to assign random values
(between 1 and 9) to this selected location and select one (or all) of
the locations that are consistent with the rules of the game. Thus you
have "9^N" possible board positions to search from. The search
space can be though of as a tree structure where the root node is an
empty board. The next level will be the nine possible state of the
board when we try to populate the first position of the board from the
list of randomly selected board positions. The 2nd level of the tree
will be all the possible state of the board with the first two randomly
selected positions are filled. You can do a DFS search by a recursive
function that take a current board position, the list of random board
positions to be filled and N. The function will try to populate the
appropriate board position and check if it is consistent with the
rules. When it finds such a board position, it will change the board to
reflect the changes and call function recursively. If the function
finds that all the positions it can generate (9 in total) are
inconsistent with the rules, then it's a deadlock and the function
returns with a failure. The function will also have to keep track of
what values when assigned to the board resulted in the recursive call
called in failure so at to not to try same value again which had
resulted in failure before.

int** generate_random(int board[][9], locations_to_be_filled[][2], int
N, int current_location);


Here the board state is stored in board[9][9], "N" is the number of
board positions to be filled, where locations are stored in
locations_to_be_filled. For example lets say we want to generate a
board with three positions been filled and we randomly select the
positions to be top left corner, bottom right corner and center, then N
will be 3 and locations to be filled will be { 0,0},{4,4},{8,8}.


Hope this helps,

Bhavesh Goswami
 >> Stay informed about: Sudoku: strategy for generating boards?