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