Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Filled Grids

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
Wires

Joined: 14 Mar 2006
Posts: 3
:
Location: United Kingdom

Items
PostPosted: Tue Mar 14, 2006 4:40 pm    Post subject: Filled Grids Reply with quote

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
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Mar 14, 2006 8:58 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Wires

Joined: 14 Mar 2006
Posts: 3
:
Location: United Kingdom

Items
PostPosted: Wed Mar 15, 2006 12:00 am    Post subject: Reply with quote

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
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Mar 15, 2006 1:00 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Wires

Joined: 14 Mar 2006
Posts: 3
:
Location: United Kingdom

Items
PostPosted: Wed Mar 15, 2006 12:36 pm    Post subject: Reply with quote

Cheers Ruud!

I'm going to have a play and see what I come up with!

Wires
Back to top
View user's profile Send private message
The Ostrich

Joined: 20 Apr 2006
Posts: 49
:

Items
PostPosted: Sun Apr 23, 2006 1:29 am    Post subject: Reply with quote

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
View user's profile Send private message
Frost_Byte

Joined: 20 Apr 2006
Posts: 6
:

Items
PostPosted: Tue May 02, 2006 9:17 pm    Post subject: Reply with quote

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... Very Happy

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... Wink

I've managed this by copying and modifying my recursive "guess" function, which is at the core of my solver.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron