How to resolve the algorithm Pentomino tiling step by step in the Python programming language

Published on 12 May 2024 09:40 PM
#Python

How to resolve the algorithm Pentomino tiling step by step in the Python programming language

Table of Contents

Problem Statement

A pentomino is a polyomino that consists of 5 squares. There are 12 pentomino shapes, if you don't count rotations and reflections. Most pentominoes can form their own mirror image through rotation, but some of them have to be flipped over.

A Pentomino tiling is an example of an exact cover problem and can take on many forms. A traditional tiling presents an 8 by 8 grid, where 4 cells are left uncovered. The other cells are covered by the 12 pentomino shapes, without overlaps, with every shape only used once. The 4 uncovered cells should be chosen at random. Note that not all configurations are solvable.

Create an 8 by 8 tiling and print the result.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Pentomino tiling step by step in the Python programming language

The provided Python code uses a recursive backtracking algorithm, known as the Dancing Links algorithm, to solve a particular type of tiling puzzle. The algorithm solves the puzzle by iterating through possible combinations of tiles to find a valid solution.

Here's a breakdown of the code:

  1. Data Initialization:

    • minos is a list of tuples representing different types of tiles. Each tuple contains three values: a number representing the tile's shape, and the number of rows and columns it spans.
    • boxchar_double_width and boxchar_single_width are lists of characters used to draw the borders and interiors of the tiles.

  2. Tile Generation:

    • The tiles list is initialized with sublists, each representing a different tile type. Within each sublist, the algorithm calculates all possible shifts of the tile on an 8x8 grid.

  3. img Function:

    • This function takes a sequence of tile numbers as input and generates a visual representation of the tile arrangement as a string. It creates a 10x10 grid and marks the occupied cells based on the input sequence.

  4. tile Function:

    • This is the main recursive function that performs the backtracking search for solutions.
      • It takes three parameters:
        • board: A bitmask representing the occupied cells in the current solution.
        • seq: A tuple representing the sequence of tiles used so far.
        • tiles: A list of the remaining tile types yet to be placed.
      • The function iterates through all possible placements of the first tile type and recursively calls itself with the updated board, seq, and tiles for each placement. The recursion continues until a valid solution is found or all possibilities have been exhausted.

  5. Loop:

    • After the tile function has exhausted all possibilities, it yields a string representation of the solution. The main loop iterates through all yielded solutions and prints them out.

In summary, this code uses a recursive backtracking algorithm to solve a tiling puzzle. It generates all possible tile arrangements and prints visual representations of the valid solutions.

Source code in the python programming language

from itertools import product

minos = (((197123, 7, 6), (1797, 6, 7), (1287, 6, 7), (196867, 7, 6)),
        ((263937, 6, 6), (197126, 6, 6), (393731, 6, 6), (67332, 6, 6)),
        ((16843011, 7, 5), (2063, 5, 7), (3841, 5, 7), (271, 5, 7), (3848, 5, 7), (50463234, 7, 5), (50397441, 7, 5), (33686019, 7, 5)),
        ((131843, 7, 6), (1798, 6, 7), (775, 6, 7), (1795, 6, 7), (1543, 6, 7), (197377, 7, 6), (197378, 7, 6), (66307, 7, 6)),
        ((132865, 6, 6), (131846, 6, 6), (198146, 6, 6), (132611, 6, 6), (393986, 6, 6), (263938, 6, 6), (67330, 6, 6), (132868, 6, 6)),
        ((1039, 5, 7), (33751554, 7, 5), (16843521, 7, 5), (16974081, 7, 5), (33686274, 7, 5), (3842, 5, 7), (3844, 5, 7), (527, 5, 7)),
        ((1804, 5, 7), (33751297, 7, 5), (33686273, 7, 5), (16974338, 7, 5), (16843522, 7, 5), (782, 5, 7), (3079, 5, 7), (3587, 5, 7)),
        ((263683, 6, 6), (198148, 6, 6), (66310, 6, 6), (393985, 6, 6)),
        ((67329, 6, 6), (131591, 6, 6), (459266, 6, 6), (263940, 6, 6)),
        ((459780, 6, 6), (459009, 6, 6), (263175, 6, 6), (65799, 6, 6)),
        ((4311810305, 8, 4), (31, 4, 8)),
        ((132866, 6, 6),))

boxchar_double_width = ' ╶╺╵└┕╹┖┗╴─╼┘┴┶┚┸┺╸╾━┙┵┷┛┹┻╷┌┍│├┝╿┞┡┐┬┮┤┼┾┦╀╄┑┭┯┥┽┿┩╃╇╻┎┏╽┟┢┃┠┣┒┰┲┧╁╆┨╂╊┓┱┳┪╅╈┫╉╋'
boxchar_single_width = [c + ' ─━'[i%3] for i, c in enumerate(boxchar_double_width)]

# choose drawing alphabet based on terminal font
patterns = boxchar_single_width

tiles = []
for row in reversed(minos):
    tiles.append([])
    for n, x, y in row:
        for shift in (b*8 + a for a, b in product(range(x), range(y))):
            tiles[-1].append(n << shift)

def img(seq):
    b = [[0]*10 for _ in range(10)]

    for i, s in enumerate(seq):
        for j, k in product(range(8), range(8)):
            if s & (1<<(j*8 + k)):
                b[j + 1][k + 1] = i + 1

    idices = [[0]*9 for _ in range(9)]
    for i, j in product(range(9), range(9)):
        n = (b[i+1][j+1], b[i][j+1], b[i][j], b[i+1][j], b[i+1][j+1])
        idices[i][j] = sum((a != b)*(1 + (not a or not b))*3**i for i, (a,b) in enumerate(zip(n, n[1:])))

    return '\n'.join(''.join(patterns[i] for i in row) for row in idices)

def tile(board=0, seq=tuple(), tiles=tiles):
    if not tiles:
        yield img(seq)
        return

    for c in tiles[0]:
        b = board | c

        tnext = [] # not using list comprehension ...
        for t in tiles[1:]:
            tnext.append(tuple(n for n in t if not n&b))
            if not tnext[-1]: break # because early break is faster
        else:
            yield from tile(b, seq + (c,), tnext)

for x in tile():
    print(x)

You may also check:How to resolve the algorithm Literals/String step by step in the DWScript programming language
You may also check:How to resolve the algorithm Non-decimal radices/Convert step by step in the M4 programming language
You may also check:How to resolve the algorithm Department numbers step by step in the EasyLang programming language
You may also check:How to resolve the algorithm Doubly-linked list/Traversal step by step in the Action! programming language
You may also check:How to resolve the algorithm Execute HQ9+ step by step in the JavaScript programming language