Logic puzzle generation

[Todd]

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

 

[Augie De Blieck Jr.]

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

 

[Todd]

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

Thanks for the reply, but what I really want to do is generate the
puzzle, not solve one that already exists.

Todd

 

[John Joyce]

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!

 

[Rick DeNatale]

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.

 

[Eric I.]

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