# Last Piece Puzzle solving program
import numpy, matplotlib, pylab
pieces = [
numpy.matrix([[1,-1,1,-1],[0,0,0,1]]),
numpy.matrix([[1,-1,1,-1],[-1,0,0,0]]),
numpy.matrix([[-1,1,0],[0,-1,0],[0,1,-1]]),
numpy.matrix([[-1,0],[1,-1],[0,1]]),
numpy.matrix([[0,-1,1],[0,1,0],[1,-1,0]]),
numpy.matrix([[-1,1,-1,1],[0,-1,0,0]]),
numpy.matrix([[1,0,0],[-1,1,-1]]),
numpy.matrix([[0,-1,0],[-1,1,-1]]),
numpy.matrix([[1,0,0],[-1,1,0],[0,-1,1]]),
numpy.matrix([[1,-1,1,0],[0,0,-1,1]]),
numpy.matrix([[1,-1,1],[-1,0,0]]),
numpy.matrix([[0,0,1,-1],[-1,1,-1,0]]),
numpy.matrix([[0,1,0,0],[1,-1,1,-1]])
]
board = numpy.zeros([8,8], dtype=int)
board[6,6]=1
board[7,6]=1
board[7,7]=1
positions = [(0,0) for piece in pieces] # starting positions of pieces
rotations = [0 for piece in pieces] # n of counterclockwise rotations [0..3]
placed = [False for piece in pieces]
curpiece = 0
def placePiece(curpiece):
"""Returns true if piece placed correctly, False if not valid position.
Doesn't check boundaries."""
# check inouty
piece = pieces[curpiece]
position = positions[curpiece]
for x in range(piece.shape[0]):
for y in range(piece.shape[1]):
if (piece[x,y] != 0 and
not inouty(position[0]+x, position[1]+y) == piece[x,y]
):
return False
if piece[x,y] != 0 and board[position[0]+x, position[1]+y] == 1:
return False
return True
def incpos(curpiece):
while True:
if rotations[curpiece] < 3:
rotations[curpiece] += 1
pieces[curpiece] = numpy.rot90(pieces[curpiece])
elif 8-positions[curpiece][1]-min(pieces[curpiece].shape)>0:
positions[curpiece] = (positions[curpiece][0], positions[curpiece][1]+1)
rotations[curpiece] = 0
pieces[curpiece] = numpy.rot90(pieces[curpiece])
elif 8-positions[curpiece][0]-min(pieces[curpiece].shape)>0:
positions[curpiece] = (positions[curpiece][0]+1, 0)
rotations[curpiece] = 0
pieces[curpiece] = numpy.rot90(pieces[curpiece])
else:
return False
# break if position valid
if (8-positions[curpiece][1]-pieces[curpiece].shape[1]>=0 and
8-positions[curpiece][0]-pieces[curpiece].shape[0]>=0):
return True
def inouty(x,y):
"""+1 if male square, -1 if female square. Anomalous square hard-coded."""
return ((x+y+1)%2)*2-1
def tobin(piece, position):
n=0L
for x in range(piece.shape[0]):
for y in range(piece.shape[1]):
if piece[x,y] != 0:
n = n | (2**((x+position[0])*8+y+position[1]))
return n
def frombin(piece, n):
mat = numpy.zeros([8,8],int)
for s in range(8**2):
if n & 2**s:
mat[s // 8, s % 8] = piece+1
return mat
allpositions = []
allpositions_cache = set()
for i in range(len(pieces)):
if placePiece(i):
n=tobin(pieces[i], positions[i])
allpositions.append((i, n))
allpositions_cache.add(n)
while incpos(i):
if placePiece(i):
n=tobin(pieces[i], positions[i])
if not n in allpositions_cache:
allpositions.append((i, n))
allpositions_cache.add(n)
fixedpiece = tobin(board, (0,0))
allpositions_sub = dict([(k, []) for k in range(64)])
for piece in allpositions:
for n in range(64)[::-1]:
if 2**n & piece[1]:
allpositions_sub[n].append(piece)
break
def findSolution(boardstate, usedpieces, usedpiecenums, uptosquare):
if len(usedpieces) == len(pieces):
return [usedpieces]
if boardstate & 2**uptosquare:
return findSolution(boardstate, usedpieces, usedpiecenums, uptosquare - 1)
else:
results = []
for piece in allpositions_sub[uptosquare]:
if uptosquare == 8**2 -1:
print ".",
if (boardstate & piece[1]) == 0 and not piece[0] in usedpiecenums:
result = findSolution(
boardstate = boardstate | piece[1],
usedpieces = usedpieces + [piece],
usedpiecenums = usedpiecenums + [piece[0]],
uptosquare = uptosquare-1)
if result != []:
results.extend(result)
return results
print "Initial setup complete. Searching..."
solutions = findSolution(fixedpiece, [], [], 8**2-1)
print "Possible solutions:"
for solution in solutions:
print sum([frombin(*piecet) for piecet in solution])
n=0
pylab.spectral()
for solution in solutions:
pylab.subplot(3,2,n+1)
pylab.matshow(sum([frombin(*piecet) for piecet in solution]),fignum=0)
pylab.colorbar()
n += 1
pylab.show()