A colleague went to San Francisco for WWWDC08, and brought back a nice puzzle as a omiyage.
The big letters announcing a very hard puzzle were too tempting. Here is the idea :
You get 36 tiles. Each of the tile contains 4 different symbols, one on each of its corner. The number of possible symbols is 7. You need to arrange those tiles in a 6x6 square so that each all corners.
#!/usr/bin/python
from copy import deepcopy
corners = [(0,0),(1,0),(1,1),(0,1)]
def compute_grid(N):
return [ (i,j) for i in range(N) for j in range(N) ]
def add(u,v):
(ux,uy) = u
(vx,vy) = v
return (ux+vx, uy+vy)
def turn(piece,rot):
rot = (rot%4 + 4) % 4
return piece[rot:] + piece[:rot]
def compute_snail(N):
res = []
dirs = [ (0,-1),(1,0),(0,1),(-1,0), ]
d,cur = 0, ((N-1)/2, (N-1)/2)
for i in range(N*N):
res.append(cur)
tryturn = add(cur, dirs[(d+1)%4])
if tryturn not in res:
d,cur = (d+1)%4, tryturn
else:
d,cur = d, add(cur, dirs[d])
return res
def game(N, pieces, path):
board = compute_grid(N)
def solver(board, remaining, path):
def put(el,pos):
def compatible(c):
val, pt = c
return (pt not in board) or (board[pt] == val)
def put(couples):
new_board = deepcopy(board)
for (val,pt) in couples:
new_board[pt] = val
return new_board
couples = [ (el[i], add(pos,corners[i])) for i in range(4)]
if all(map(compatible,couples)):
return put(couples)
else:
return None
if remaining == []:
return [board]
else:
res = []
cur, new_path = path[0], path[1:]
candidates = [(piece,rot) for piece in remaining for
rot in range(4)]
for (piece,rot) in candidates:
el = turn(piece,rot)
new_board = put(el,cur)
if new_board is not None:
new_rem = deepcopy(remaining)
new_rem.remove(piece)
res += solver(new_board, new_rem, new_path)
return res
return solver({}, pieces, path)
from random import randrange
from random import shuffle
def create_game(N=6,K=7):
d = {}
for pos in compute_grid(N+1):
d[pos] = randrange(K)
elements = map(lambda pos: [ d[add(pos, v)] for v in corners],
compute_grid(N))
elements = map(lambda t: turn(t,randrange(4)), elements)
shuffle(elements)
return elements
N=5
print game(N,create_game(N,N+1), compute_grid(N))
