# Sudoku: strategy for generating boards?

Last response: in Video Games

Related resources

Read discussions in other Video Games categories

!

Tags:

Last response: in Video Games

Anonymous

April 26, 2005 5:43:19 PM

Archived from groups: comp.ai.games (More info?)

I'm trying to generate Sudoku boards. I'm not looking for a full

solution; I'm looking for a nudge in the right direction (i.e. is this

a graph/pathfinding problem that is easily modeled and addressed in

theory, etc.). If you don't know what Sudoku is, it's a game played on

a 9x9 grid, with 9 3x3 sub-grids. Each square can hold a numerical

value between 1-9. The goal is to fill in each square according to

these rules:

- each 9-column row cannot have duplicate numbers

- each 9-row column cannot have duplicate numbers

- each 3x3 sub-grid cannot have duplicate numbers within themselves

At the beginning of each game, you as the player are presented with a

board which has some squares already filled in with valid values.

For more information, please check the Wikipedia.

Okay, so I'm trying to figure out an algorithm for generating Sudoku

boards, using random numbers where possible (i.e. a "random" board). I

tried brute forcing it, but there were complications such that I feel a

path-finding (or similar) search is required. I don't know a lot about

AI, but I had a course in it, so I know the basics. I feel like I

should be able to represent the board with a graph, and at the moment

I'm thinking that might look like: each node connected to each node in

its 3x3 sub-grid, and each node connected to each node in its row and

column. Beyond this, I'm not really sure how to go about searching

such a graph (or whatever the "correct" graph might look like, assuming

this method of solution is appropriate). Specifically, I'm not sure

how to recover if I get into a situation that requires regressing back

to a non-obvious state. For example, if you just go through each node,

starting at row 0, col 0, and moving right, by the time you get to the

second row, in the last sub-grid you can achieve deadlock -- no valid

numbers available (no valid "moves" available?). At this point, it

seems like I'd have to back up, but I have no idea how far I should

back up. Should I back up one level at a time, until things work? I

really don't know how to approach this. I feel as though any general

finger pointing in the right direction would help me immensely. Thank

you very much.

- Sean

I'm trying to generate Sudoku boards. I'm not looking for a full

solution; I'm looking for a nudge in the right direction (i.e. is this

a graph/pathfinding problem that is easily modeled and addressed in

theory, etc.). If you don't know what Sudoku is, it's a game played on

a 9x9 grid, with 9 3x3 sub-grids. Each square can hold a numerical

value between 1-9. The goal is to fill in each square according to

these rules:

- each 9-column row cannot have duplicate numbers

- each 9-row column cannot have duplicate numbers

- each 3x3 sub-grid cannot have duplicate numbers within themselves

At the beginning of each game, you as the player are presented with a

board which has some squares already filled in with valid values.

For more information, please check the Wikipedia.

Okay, so I'm trying to figure out an algorithm for generating Sudoku

boards, using random numbers where possible (i.e. a "random" board). I

tried brute forcing it, but there were complications such that I feel a

path-finding (or similar) search is required. I don't know a lot about

AI, but I had a course in it, so I know the basics. I feel like I

should be able to represent the board with a graph, and at the moment

I'm thinking that might look like: each node connected to each node in

its 3x3 sub-grid, and each node connected to each node in its row and

column. Beyond this, I'm not really sure how to go about searching

such a graph (or whatever the "correct" graph might look like, assuming

this method of solution is appropriate). Specifically, I'm not sure

how to recover if I get into a situation that requires regressing back

to a non-obvious state. For example, if you just go through each node,

starting at row 0, col 0, and moving right, by the time you get to the

second row, in the last sub-grid you can achieve deadlock -- no valid

numbers available (no valid "moves" available?). At this point, it

seems like I'd have to back up, but I have no idea how far I should

back up. Should I back up one level at a time, until things work? I

really don't know how to approach this. I feel as though any general

finger pointing in the right direction would help me immensely. Thank

you very much.

- Sean

More about : sudoku strategy generating boards

Anonymous

April 27, 2005 9:03:47 AM

sean.gilbertson@gmail.com wrote in news:1114548199.302504.115850

@o13g2000cwo.googlegroups.com:

> I'm trying to generate Sudoku boards. I'm not looking for a full

> solution; I'm looking for a nudge in the right direction (i.e. is this

> a graph/pathfinding problem that is easily modeled and addressed in

> theory, etc.).

There's a thread about Sudoku right now on rec.puzzles. Thread name is "Su

Doku", and gcrhoads describes a way to formulate Sudoku as an exact cover

problem. It may be helpful to you.

Beyond that, maybe start constructing simpler versions of the puzzle, like,

say, 3x3 boards with no sub-grids. Once you can do those, try 4x4 boards

with 2x2 sub-grids. Those will have less complexity, and may reveal

properties and techniques useful for constructing larger puzzles.

Anonymous

May 1, 2005 10:40:55 PM

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

Related resources

Read discussions in other Video Games categories

!