G
Guest
Guest
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