Solve (jigsaw, fill tile) puzzle by backtracking

readme.md

Puzzle must have tiles and a final state.

Example:

SMALL_GAME_FINAL = (
    'RB',
    'BR'
)
BLOCKS = (
    (('R', ' '), ('B', 'R')),
    (('B', ' '), (' ', ' '))
)
sol = PuzzleSolver()
sol.solve(SMALL_GAME_FINAL, BLOCKS)


FINAL = (
    'BRBRR',
    'RBBRB',
    'RBBRB',
    'RRRBB',
    'BBRBR',
)
BLOCKS = (
    (('R', ' '), ('B', 'B')),
    (('B', 'B'), ('R', ' ')),
    (('R', 'B'), (' ', ' ')),
    (('B', 'B'), (' ', ' ')),
    (('B', 'R'), (' ', ' ')),
    ((' ', 'R'), ('R', 'B')),
    (('R', 'R'), (' ', 'B')),
    (('R', 'B'), (' ', ' ')),
    (('B', 'R'), (' ', 'B')),
    (('R', 'R'), (' ', ' '))
)
sol = PuzzleSolver()
sol.solve(FINAL, BLOCKS)


FINAL = (
    '11111',
    '11111',
    '11111',
)
BLOCKS = (
    (('1', '1', '1'), ),
    (('1', '1'), ('1', '1')),
    (('1', '1'), ('1', '1')),
    (('1', ' ', ' '), ('1', '1', '1')),
)
sol = PuzzleSolver()
sol.solve(FINAL, BLOCKS)

solver.py

from collections import deque
from typing import Tuple, Any
from functools import lru_cache

class PuzzleSolver():    
    @lru_cache(maxsize=None)
    def rotate(self, block):
        """Rotate a block clockwise 3 times.
        """
        angles_nums = [0, 90, 180, 270]
        angles = [(0, block)]
        for i in range(3):
            block = tuple(zip(*block[::-1]))
            angles.append((angles_nums[i], block))
        return angles                
    
    def verify(self, board, final):
        rows = len(board)
        cols = len(board[0])
        for row in range(rows):
            for col in range(cols):
                if board[row][col] != final[row][col]:
                    return False
        return True
    
    def solve(self, final, original_blocks: Tuple[Any], allow_skip=3, allow_overlap=False):
        self.final = final
        rows = len(final)
        cols = len(final[0])
        board = [[' '] * cols for i in range(rows)]
        blocks_detail = {}  # Store blocks info like index, rotation
        blocks = deque([(block, index) for index, block in enumerate(original_blocks)])
        
        def canplace(block, row, col):
            blockrows =  len(block)
            blockcols = len(block[0])
            for br in range(blockrows):
                for bc in range(blockcols):
                    if block[br][bc] == ' ':
                        continue
                    if row + br >= rows or col + bc >= cols:
                        return False
                    if block[br][bc] != final[row + br][col + bc] or board[row + br][col + bc] != ' ':
                        return False 
            return True
            
        def place(block, row, col, blockindex, angle):
            blockrows =  len(block)
            blockcols = len(block[0])
            for br in range(blockrows):
                for bc in range(blockcols):
                    if block[br][bc] == ' ':
                        continue
                    board[row + br][col + bc] = block[br][bc]
                    blocks_detail[(row + br, col + bc)] = (blockindex, angle)
            
        def remove(block, row, col):
            blockrows =  len(block)
            blockcols = len(block[0])
            for br in range(blockrows):
                for bc in range(blockcols):
                    if block[br][bc] == ' ':
                        continue
                    board[row + br][col + bc] = ' '
                    blocks_detail.pop((row + br, col + bc), None)
                    
        def print_solution():
            print('Yay, found a solution')
            for row in range(rows):
                for col in range(cols):
                    print(board[row][col], end='\t')
                print()
            print()
            for row in range(rows):
                for col in range(cols):
                    if (row, col) in blocks_detail:
                        index, angle = blocks_detail[(row, col)]
                        print(index, end='\t')
                    else:
                        print('?', end='\t')
                print()
            print()
            for index, block in enumerate(original_blocks):
                print(index)
                for row in block:
                    print('\t\t', row)
        
        def backtrack(row, col, skipped=0):
            """Try to place a block at row, col
            """
            # No more blocks left
            if not blocks and self.verify(board, final):
                print_solution()
                return True
                
            if skipped > allow_skip:
                return False
                
            if col >= cols:
                col = 0
                row += 1
            if row >= rows:
                return False
                
            blockleft = len(blocks)
            for i in range(blockleft):
                block, blockindex = blocks.popleft()
                for angle, rotated in self.rotate(block):
                    if canplace(rotated, row, col):
                        place(rotated, row, col, blockindex, angle)
                        if backtrack(row, col + 1, 0):
                            pass #return True
                        if allow_overlap and backtrack(row, col, 0):
                            return True
                        remove(rotated, row, col)
                blocks.append((block, blockindex))
                
            return backtrack(row, col + 1, skipped + 1)
        
        backtrack(0, 0)