Google Answers Logo
View Question
 
Q: Solution to a puzzle game ( Answered 5 out of 5 stars,   4 Comments )
Question  
Subject: Solution to a puzzle game
Category: Sports and Recreation > Games
Asked by: hastings-ga
List Price: $10.00
Posted: 31 Dec 2004 10:08 PST
Expires: 30 Jan 2005 10:08 PST
Question ID: 449715
What's the solution to the Great American Puzzle Factory puzzle called
"One Tough Puzzle".  It has 9 pieces, like a jigsaw, but there is only
one way to arrange them.  There are 300,000 wrong ways.  Each piece
has two shapes cut out and two shapes which interlock.  The edges
should have 6 interlocks that extend beyond the border and 6 that are
inside the border.  I can't find any pattern.  Help.

Request for Question Clarification by leapinglizard-ga on 31 Dec 2004 13:14 PST
I'd like to help you with the puzzle, but first I have to understand
more clearly the rules for completing it.

I know from your description and from looking at pictures of the
puzzle that each of the nine pieces has two holes and two projecting
bits -- let's call these pegs. Are you saying that in its finished
state, the jigsaw has a total of six pegs lying outside the square,
while there are six holes inside the square?

Is there any other restriction at all? Because if there isn't, then it
seems to me that the following picture illustrates the solution.

http://www.unclesgames.com/images/products/thumbs/010563001208_1.jpg

If that image does not contain a valid solution, please explain to me why not.

leapinglizard

Request for Question Clarification by leapinglizard-ga on 31 Dec 2004 15:31 PST
Crythias states in a comment below that the link I gave doesn't work
for him, perhaps because his browser doesn't show images unless
they're wrapped in a web page. If you're also having trouble, use the
following link instead.

http://plg.uwaterloo.ca/~mlaszlo/answers/one_tough_puzzle.html

Is that the solution to your puzzle?

leapinglizard

Clarification of Question by hastings-ga on 01 Jan 2005 01:57 PST
Hello and happy new year from Scotland.  The image you showed is the
one on the box, and it is bogus.  Doesn't work.  The only other rule
in the puzzle is that there should be no holes in the middle.  6 pegs
outside the square, and 6 holes on the outside edge only.  Linda

Request for Question Clarification by leapinglizard-ga on 01 Jan 2005 03:59 PST
In what way is the depicted configuration bogus? Are those not the
nine pieces in the puzzle?

If I am to solve it with a computer program, I'll have to know exactly
how the pieces can fit together. Judging from the illustration, each
side of an individual piece has one of eight types, which I'll denote
with the following codes.

    spade peg   +S         spade hole   -S
    heart peg   +H         heart hole   -H
    club peg    +C         club hole    -C
    diamond peg +D         diamond hole -D

We can characterize each piece with a 4-tuple whose elements denote,
in clockwise order, the type of each side. Tuples are thus equivalent
under rotation, so (+H, +H, -D, -H) describes the same piece as (+H,
-D, -H, +H).

According to the illustration, the nine pieces of the puzzle are as follows.

  1. (+H, +H, -D, -H)
  2. (+H, +H, -C, -H)
  3. (+H, +D, -D, -H)
  4. (+D, -D, -H, +H)
  5. (+C, -S, -S, +D)
  6. (+D, -S, -H, +S)
  7. (+H, -D, -S, +C)
  8. (+S, -C, -S, +D)
  9. (+H, -C, -S, +C)

If this is not accurate, then please provide a true description of the
puzzle pieces using the same notation. Once I have this information,
I'll be able to feed it into a computer program to compute the
solution.

leapinglizard

Clarification of Question by hastings-ga on 01 Jan 2005 06:27 PST
The puzzle box has the same illustration and I tried this, and it
doesn't work.  I give below all the pieces, in the notation you used.

+H    +D    -C    -C
+D    +C    -C    -D
+C    +H    -D    -C
+S    +D    -H    -D
+C    +H    -S    -H
+S    +D    -S    -H
+S    +S    -H    -C
+H    +D    -D    -H
+H    +S    -S    -C

Have fun....

Linda
Answer  
Subject: Re: Solution to a puzzle game
Answered By: leapinglizard-ga on 01 Jan 2005 08:46 PST
Rated:5 out of 5 stars
 
Dear hastings,

Using the pieces you gave above, the solution is the following.

   +H      +D      +S   
 -C  +D  -D  +C  -C  +S 
   -C      -C      -H   

   +C      +C      +H   
 -C  +H  -H  +H  -H  +D 
   -D      -S      -D   

   +D      +S      +D   
 +S  -H  +H  -S  +S  -S 
   -D      -C      -H   

Below is the Python script I wrote to compute this solution.

Regards,

leapinglizard



#!/usr/bin/python

import sys, os, string, re
import time

pieces = [['+H','+D','-C','-C'], ['+D','+C','-C','-D'], ['+C','+H','-D','-C'],
          ['+S','+D','-H','-D'], ['+C','+H','-S','-H'], ['+S','+D','-S','-H'],
          ['+S','+S','-H','-C'], ['+H','+D','-D','-H'], ['+H','+S','-S','-C']]

i2p = [(1, 1),
       (1, 0), (0, 1), (1, 2), (2, 1),
       (0, 0), (0, 2), (2, 2), (2, 0)]
p2i = {}
for i in range(len(i2p)):
    p2i[i2p[i]] = i

dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
co = [2, 3, 0, 1]
count = [0]
maxi = [0]

used = 9*[0]
config = []
for i in range(3):
    config.append(3*[['<>', '<>', '<>', '<>']])

def disp_config(config):
    for r in range(3):
        for c in range(3):
            sys.stdout.write('  %s  ' % config[r][c][0])
        sys.stdout.write('\n')
        for c in range(3):
            sys.stdout.write('%s  %s' % (config[r][c][3], config[r][c][1]))
        sys.stdout.write('\n')
        for c in range(3):
            sys.stdout.write('  %s  ' % config[r][c][2])
        sys.stdout.write('\n')


def doit(config, i):
    maxi[0] = max(maxi[0], i)
    if i == 9:
        disp_config(config)
        count[0] += 1
        return
    (r, c) = i2p[i]
    new_config = []
    for row in config:
        new_config.append(row[:])
    for j in range(9):
        if used[j]:
            continue
        piece = pieces[j]
        for k in range(4):
            piece = piece[1:]+piece[:1]
            kosher = 1
            for l in range(4):
                (rr, cc) = (r+dd[l][0], c+dd[l][1])
                if (rr < 0 or rr > 2) or (cc < 0 or cc > 2):
                    continue
                (here, there) = (piece[l], config[rr][cc][co[l]])
                if there == '<>':
                    continue
                if here[0] == there[0] or here[1] != there[1]:
                    kosher = 0
                    break
            if kosher:
                new_config[r][c] = piece
                used[j] = 1
                doit(new_config, i+1)
                used[j] = 0

for i in range(9):
    config[1][1] = pieces[i][:]
    used[i] = 1
    doit(config, 1)
    used[i] = 0

Request for Answer Clarification by hastings-ga on 01 Jan 2005 10:27 PST
Can you just spell out for me in plain English how the program worked?
 Just for fun.  I am so pleased with the result.

Clarification of Answer by leapinglizard-ga on 01 Jan 2005 11:54 PST
Thank you for the kind words and tip.

I can certainly give you a brief explanation of how this program
works. It's not a very smart program, really, since it just tries
every possible way of laying out the pieces.

At the beginning of the script are some lists of numbers that I use to
calculate directions and positions in the puzzle, which starts out as
an empty 3x3 grid. The search is initiated by the little loop at the
end, which reads as follows.

for i in range(9):
    config[1][1] = pieces[i][:]
    used[i] = 1
    doit(config, 1)
    used[i] = 0

This says to take each of the nine pieces in turn, place it in the
center of the grid, mark it as used, and call the function named
doit().

The first few instructions in doit() ask whether we are done yet. If
we are, we call print_config() to print out the contents of the grid
in a manner intelligible to the human eye.

    if i == 9:
        disp_config(config)

Otherwise, we consider the possible ways to fill a currently empty
cell in the grid. The following three lines say that we should take
each piece in turn and consider whether it has been used already. If
so, let's skip it.

    for j in range(9):
        if used[j]:
            continue

Otherwise, let's take this piece and rotate it four times so that we
consider every orientation.

        piece = pieces[j]
        for k in range(4):
            piece = piece[1:]+piece[:1]

Now we check whether we can legitimately place the current piece in
its current orientation into the currently empty cell. We look at each
of the cell's neighbors, which can lie in one of four directions with
respect to the current cell. In some of these directions, there is
only empty space.

            kosher = 1
            for l in range(4):
                (rr, cc) = (r+dd[l][0], c+dd[l][1])
                if (rr < 0 or rr > 2) or (cc < 0 or cc > 2):
                    continue

For non-empty neighbors, we consider the sides that share a common
border, letting "here" be the side of the current cell and "there" be
the side of its neighbor. The burning question now is whether "here"
is compatible with "there".

                (here, there) = (piece[l], config[rr][cc][co[l]])
                if there == '<>':
                    continue
                if here[0] == there[0] or here[1] != there[1]:
                    kosher = 0
                    break

If our current choice of piece for the empty cell is compatible with
its neighbors, we insert it into the grid, mark it as used, and call
doit() again to look at possibilities for the next empty cell.

            if kosher:
                new_config[r][c] = piece
                used[j] = 1
                doit(new_config, i+1)
                used[j] = 0
 
And that's the whole bag of tricks.

leapinglizard
hastings-ga rated this answer:5 out of 5 stars and gave an additional tip of: $2.00
Over and above the call of duty.  It's absolutely brilliant that there
was a personal computer program to calculate this.  I am astounded.

Comments  
Subject: Re: Solution to a puzzle game
From: crythias-ga on 31 Dec 2004 12:26 PST
 
I have the same puzzle in three formats. I'm tempted to write a
program to solve it... I haven't done that, yet, but I'm leaving a
message here just in case I come back to it.
Subject: Re: Solution to a puzzle game
From: crythias-ga on 31 Dec 2004 15:07 PST
 
leapinglizard-ga, your RFC made me realize that, though I have a
similar 9 piece puzzle, I don't have *that* puzzle. Likewise, I seem
to be unable to resolve the link you have given to that picture. It
seems to return to UnclesGames.com home page.

http://www.unclesgames.com/product_info.php/products_id/5491, and
click the "click to enlarge" in the bottom middle.

hastings-ga, please accept leapinglizard-ga's RFC as the answer. 

Happy New Year!
Subject: Re: Solution to a puzzle game
From: crythias-ga on 01 Jan 2005 13:15 PST
 
leapinglizard, you rock!
Subject: Re: Solution to a puzzle game
From: rhapsody-ga on 19 Jan 2005 14:02 PST
 
I too have this puzzle, and was frustrated by the lack of a solution.
I wrote a solution in Pascal (actually with Delphi 6) that employs
pretty much the same strategy as that of leapinglizard's solution -
i.e. a recursive brute-force approach, and then (with some elementary
modifications) applied the same algorithm to another puzzle called
"Professor McBrainy's Zany To The Extreme Puzzle". This one is a
four-by-four grid with 523,069,747,250 combinations and one solution.

Takes on average about 3 seconds to find the solution on my Athlon 2600!

If anyone would like the source, just ask.

TTFN

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy