View Question
Q: Solution to a puzzle game ( Answered ,   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```
 Subject: Re: Solution to a puzzle game Answered By: leapinglizard-ga on 01 Jan 2005 08:46 PST Rated:
 ```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: 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.```

 ```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.```
 ```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!```
 `leapinglizard, you rock!`
 ```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```