I was wondering if anyone here could point me in the direction of some books/articles/etc. that talk about algorithms for logic puzzle generation (i.e. Sudoku). What I'm looking for is a way to generate puzzles, much like Sudoku, that have one and only one solution and also can absolutely be solved with logic. For example, I'm frustrated with Minesweeper because of conditions like this in the end game (F = already flagged, ? = unknown, each character is in a box) F F F 3 ? 4 1 ? F You have to guess! Any material on this would be great. Thanks, Todd

on 2007-04-02 21:46

on 2007-04-02 22:47

APress has a book called PROGRAMMING SUDOKU that might be up your alley: http://www.apress.com/book/bookDisplay.html?bID=10111 "This is a fun, intriguing read whether you're a novice or advanced programmer. It acknowledges the.NET platform as a base, but you'll find this book interesting whatever your programming background. The core techniques in the book enable you to solve Sudoku on any programming platform." -Augie

on 2007-04-02 23:11

```
On Apr 2, 1:46 pm, "Augie De Blieck Jr." <removed_email_address@domain.invalid>
wrote:
> -Augie
Thanks for the reply, but what I really want to do is generate the
puzzle, not solve one that already exists.
Todd
```

on 2007-04-02 23:45

On 4/2/07, Todd <removed_email_address@domain.invalid> wrote: > > programming platform." > > > > -Augie > > Thanks for the reply, but what I really want to do is generate the > puzzle, not solve one that already exists. While I haven't read the book, it does seem to cover how to program the puzzle, not just solve it. You may want to download the VB.NET code and see if it help you before you dismiss it entirely. It has a SudokuPuzzle class with a GetPuzzle method that generates new puzzles. Here are a couple URLs that might also be helpful: http://sudoku.rubyforge.org/ http://www.rubyquiz.com/quiz43.html http://www.xprogramming.com/xpmag/OkSudoku.htm http://www.google.com/search?q=sudoku+ruby Todd

on 2007-04-03 09:38

Just read the rules for Sudoku. You can develop your own program. The rules pretty much give you the things you need to create your algorithm. start with the nice article at wikipedia http://en.wikipedia.org/wiki/Sudoku You could do it many ways, but consider multi-dimensional arrays or something similar. These correspond well to a grid. 3 x 3, each containing a 3 x 3 grid. Make sure that any given row or column follows the rules. You could get more creative to speed your generation times: Generate first a list of the sub-grids, there is a finite number of them. Label each one. Perhaps use a label that is descriptive of the contents, very simply: 123456789, or 235149876 as an example if you read each subgrid from left to right, starting in the top right another method would be to give each combination of 3 digits from 1-9 some sort of symbolic label. Then assign 6 of these to each sub grid (3 horizontal, 3 vertical) Anyway, once you have each sub-grid it becomes very simple to develop matching/not matching combinations. Now the hard part is deciding which numbers to reveal or leave hidden and yet keep the puzzle solveable!

on 2007-04-06 00:28

On 4/3/07, John J. <removed_email_address@domain.invalid> wrote: > Just read the rules for Sudoku. > You can develop your own program. > The rules pretty much give you the things you need to create your > algorithm. > start with the nice article at wikipedia > http://en.wikipedia.org/wiki/Sudoku > > > Now the hard part is deciding which numbers to reveal or leave hidden > and yet keep the puzzle solveable! Which is really, after all, the OP's question. -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/

on 2007-04-06 23:06

On Apr 2, 1:41 pm, "Todd" <removed_email_address@domain.invalid> wrote: > I was wondering if anyone here could point me in the direction of some > books/articles/etc. that talk about algorithms for logic puzzle > generation (i.e. Sudoku). > > What I'm looking for is a way to generate puzzles, much like Sudoku, > that have one and only one solution and also can absolutely be solved > with logic. Well if we were to come up with a general technique, I'd probably do something like this. I'll use Sudoku as an example, but this technique is probably pretty general. For a specific puzzle, however, it may be more efficient to use a tailored technique. 1. Write/run a program that generates a solved puzzle, such that it meets all the requirements. 2. Remove some subset of the numbers. You could do this randomly or using heuristics. You could even use human input. 3. Write/run a program that solves the puzzle. The program should produce all possible solutions. If more than one exists, then you know there's not a unique solution. 4. As a refinement of #3, you could write the program so that rather than doing an exhaustive search, it solves it step-wise like a human would. Each step uses one of the techniques that a person would use. You could even rate the techniques by degree of difficulty. If you can solve the puzzle with techniques that are "easy" then you've created an easy puzzle. If you have to use more advanced techniques, then you've created a more advanced puzzle. Eric