Forum: Ruby Logic puzzle generation

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Todd (Guest)
on 2007-04-02 21:46
(Received via mailing list)
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. (Guest)
on 2007-04-02 22:47
(Received via mailing list)
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 (Guest)
on 2007-04-02 23:11
(Received via mailing list)
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
Mike M. (Guest)
on 2007-04-02 23:45
(Received via mailing list)
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
John J. (Guest)
on 2007-04-03 09:38
(Received via mailing list)
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 D. (Guest)
on 2007-04-06 00:28
(Received via mailing list)
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/
Eric I. (Guest)
on 2007-04-06 23:06
(Received via mailing list)
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
This topic is locked and can not be replied to.