View previous topic :: View next topic |
Author |
Message |
| Wires
| Joined: 14 Mar 2006 | Posts: 3 | : | Location: United Kingdom | Items |
|
Posted: Tue Mar 14, 2006 4:40 pm Post subject: Filled Grids |
|
|
I've been browsing this site for ideas, but have so far failed to find the answer to my question. I am setting sudoku, but by a relatively simple means in that I will use the solver to determine the level of the puzzle.
I need to create a basic sudoku grid, completely filled in, at random. This would be easy but for the 1 to 9 in the box constraint. Does anyone have a suggestion for a simple method of creating a filled starting grid?
I am using PHP to implement this.
Thanks,
Wires |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Tue Mar 14, 2006 8:58 pm Post subject: |
|
|
Hi Wires,
welcome to the forum.
I have described a method here: http://www.setbb.com/sudoku/viewtopic.php?p=1811&mforum=sudoku#1811
Other methods can be found in the same topic. This forum has several topics that explain methods of generating complete grids. Some come with complete program code. Not in PHP, I'm afraid.
Ruud. |
|
Back to top |
|
|
| Wires
| Joined: 14 Mar 2006 | Posts: 3 | : | Location: United Kingdom | Items |
|
Posted: Wed Mar 15, 2006 12:00 am Post subject: |
|
|
Thanks Ruud.
I follow what you're doing there, but there are a couple of questions I'd like to ask about it....
a) You say configure the solver to the difficulty level - does this mean you set your exposed cells as you go in which case how do you determine which cells are exposed and which are white?
b) How do you process the effects of an entry using your solver when the grid is incomplete? For instance if I start with a blank grid and enter a single digit in a random cell, I know that is not going to invalidate the grid because it is the first value and cell. If I do this later in the process, the remaining cells may still have plenty of options available, but manually placing values (using the cells with the lowest possibilities first) through to the end always eventually leads me to an invalid grid!
Cheers, Wires |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Wed Mar 15, 2006 1:00 am Post subject: |
|
|
Quote: | a) You say configure the solver to the difficulty level - does this mean you set your exposed cells as you go in which case how do you determine which cells are exposed and which are white? |
I have a configurable solver. The user can determine what techniques he/she wants to see in the sudoku. When the solver is used to generate sudokus, it cannot solve sudokus that require more than the configured techniques, so it will not generate those (as solving is part of the generation process).
However, there is no guarantee that the selected techniques will appear in the generated puzzle. This is one of the problems that every sudokumaker has to face, you just have to try until a nice sudoku is generated. This is the reason that we have sudoku libraries and we want our generators to be extremely fast.
The exposed cells (clues or givens in sudolulingo) are set by the generator, the white (empty) cells are those that the solver could solve.
Quote: | b) How do you process the effects of an entry using your solver when the grid is incomplete? For instance if I start with a blank grid and enter a single digit in a random cell, I know that is not going to invalidate the grid because it is the first value and cell. If I do this later in the process, the remaining cells may still have plenty of options available, but manually placing values (using the cells with the lowest possibilities first) through to the end always eventually leads me to an invalid grid! |
This is part of the algorithm. When your generator places a digit, it calls the solver. There are 3 possibilities:
1. There are multiple solutions, the human-style solver cannot complete the puzzle (need more clues)
2. There is no solution, a conflict is found (backtrack or restart, see 2 options below)
3. There is a single solution (you are finished)
There are 2 options when there is no solution: either you build a backtracking mechanism, or you restart the generation process with a new empty grid. My experience is that 3 or 4 restarts on average are required to generate a valid puzzle. Not worth the effort to build a backtracking algorithm.
If you decide to use backtracking in stead of restarting, make sure your algorithm can track-back multiple steps.
Ruud. |
|
Back to top |
|
|
| Wires
| Joined: 14 Mar 2006 | Posts: 3 | : | Location: United Kingdom | Items |
|
Posted: Wed Mar 15, 2006 12:36 pm Post subject: |
|
|
Cheers Ruud!
I'm going to have a play and see what I come up with!
Wires |
|
Back to top |
|
|
| The Ostrich
| Joined: 20 Apr 2006 | Posts: 49 | : | | Items |
|
Posted: Sun Apr 23, 2006 1:29 am Post subject: |
|
|
Ruud,
One very obvious trick is while your sudoku program is running, set a separate thread going to produce the next 2 sudokus of each difficulty category, and store them. This doesn't work if the user can pick exactly any subset of all known logical techiques of course, but then again I don't see what would... |
|
Back to top |
|
|
| Frost_Byte
| Joined: 20 Apr 2006 | Posts: 6 | : | | Items |
|
Posted: Tue May 02, 2006 9:17 pm Post subject: |
|
|
I have tackled with this problem today, I'll try to give a simple explanation to "how to create a filled sudoku grid/board".
The answer is simple: By finding a solution to an empty grid/board...
But the solver should be able to employ guessing/back-tracking. Also, the solver should guess randomly among candidates (and obviously, should not select the same candidate after backtracking). After these slight modifications, you may stop the solver after finding the first answer. Store this filled grid and use it as you want...
I've managed this by copying and modifying my recursive "guess" function, which is at the core of my solver. |
|
Back to top |
|
|
|