solve_puzzle.py

from scipy.signal import convolve2d
import sys
import multiprocessing
import numpy as np

shapes = [
    np.array([
        [1, 0, 0, 1],
        [1, 0, 0, 1],
        [1, 1, 1, 1],
    ]),
    np.array([
        [1, 0],
        [1, 0],
        [1, 1],
        [1, 1],
        [1, 1],
    ]),
    np.array([
        [0, 1, 0],
        [0, 1, 0],
        [1, 1, 1],
        [1, 1, 1],
    ]),
    np.array([
        [1, 1],
        [1, 1],
        [1, 1],
        [1, 1]
    ]),
    np.array([
        [1, 1, 0],
        [1, 1, 1],
        [1, 1, 1],
    ]),
    np.array([
        [0, 1, 1],
        [0, 1, 1],
        [1, 1, 0],
        [1, 1, 0],
    ]),
    np.array([
        [1, 0, 0],
        [1, 0, 0],
        [1, 1, 1],
        [1, 1, 1],
    ]),
    np.array([
        [0, 1, 1, 0],
        [0, 1, 1, 0],
        [1, 1, 1, 1],
    ])
]

shapes = [sh.astype(int) for sh in shapes]
rotated_shapes = [[np.rot90(sh, k=k) for k in range(4)] for sh in shapes]

initial_board = np.zeros((8, 8), dtype=int)

min_remaining = 8


def main():
    p = multiprocessing.Pool(8)
    try:
        p.map(solve, ([0], [1], [2], [3], [4], [5], [6], [7]))
    except (Exception, KeyboardInterrupt):
        p.terminate()
        p.join()


def solve(start_shapes, board=None, placed=None, remaining=None):
    global min_remaining
    if board is None:
        board = initial_board
    if placed is None:
        placed = []
    if remaining is None:
        remaining = np.arange(len(shapes))

    if len(remaining) == 0:
        with open('placed.txt', 'w') as f:
            print_board(placed, f)
            raise Exception('done!')

    if len(remaining) < min_remaining:
        min_remaining = len(remaining)
        print 'min_remaining', min_remaining

    candidates = start_shapes if len(placed) == 0 else remaining
    for i in candidates:
        new_remaining = [j for j in remaining if j != i]
        for r in range(4):
            s = rotated_shapes[i][r]
            h, w = s.shape
            conv = convolve2d(board, s[::-1, ::-1], mode='valid')
            for y, x in zip(*np.where(conv == 0)):
                new_placed = placed + [(i, r, y, x)]
                board[y:y + h, x:x + w] += s
                solve(start_shapes, board, new_placed, new_remaining)
                board[y:y + h, x:x + w] -= s


def print_board(placed, f=sys.stdout):
    board = np.zeros((8, 8), dtype=int)
    for i, r, y, x in placed:
        s = np.rot90(shapes[i], k=r)
        h, w = s.shape
        board[y:y + h, x:x + w] += (s * (i + 1))

    for y in range(8):
        for x in range(8):
            if board[y, x] == 0:
                f.write('.')
            else:
                f.write(chr(64 + board[y, x]))
        f.write('\n')


if __name__ == '__main__':
    main()