[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Logic puzzle generation

Todd

4/2/2007 5:41:00 PM

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
5 Answers

Augie De Blieck Jr.

4/2/2007 6:46:00 PM

0

APress has a book called PROGRAMMING SUDOKU that might be up your alley:

http://www.apress.com/book/bookDisplay.html...

"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

4/2/2007 7:05:00 PM

0

On Apr 2, 1:46 pm, "Augie De Blieck Jr." <augi...@gmail.com> wrote:
> APress has a book called PROGRAMMING SUDOKU that might be up your alley:
>
> http://www.apress.com/book/bookDisplay.html...
>
> "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

4/3/2007 5:37:00 AM

0

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/w...

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 Apr 3, 2007, at 2:45 AM, Todd 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.
>
> 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
>
>

Rick DeNatale

4/5/2007 8:28:00 PM

0

On 4/3/07, John Joyce <dangerwillrobinsondanger@gmail.com> 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/w...
>

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

Eric I.

4/6/2007 7:01:00 PM

0

On Apr 2, 1:41 pm, "Todd" <toddkennethben...@yahoo.com> 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