Pentomino solver in Python

Question

When I was a child, I used to play Ubongo board game, recently I discovered Pentomino puzzle and I wanted to create a custom solver in python for it. Here is what I got:

import datetime
def solve(height, width, pieces):
 sorted_pieces = sort_pieces_by_length(pieces) # this makes it faster as it sort also coords of piece
 board = [['' for _ in range(width)] for _ in range(height)]
 result = []
 counter = 0
 def is_valid_placement(piece, x, y):
 first_coord = piece[0]
 if not (0 <= x < width and 0 <= y < height) or board[y][x] != '':
 return False
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 if not (0 <= nx < width and 0 <= ny < height) or board[ny][nx] != '':
 return False
 return True
 def place_piece(piece, x, y, char):
 first_coord = piece[0]
 board[y][x] = char
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 board[ny][nx] = char
 def remove_piece(piece, x, y):
 first_coord = piece[0]
 board[y][x] = ''
 for px, py in piece[1:]:
 nx, ny = x + px - first_coord[0], y + py - first_coord[1]
 board[ny][nx] = ''
 def find_smallest_area():
 visited = set()
 smallest_area = height * width
 occupied_tiles = 0
 for y in range(height):
 for x in range(width):
 if board[y][x] != '':
 occupied_tiles += 1
 def bfs(start_x, start_y):
 nonlocal smallest_area
 queue = [(start_x, start_y)]
 area = 0
 while queue:
 curr_x, curr_y = queue.pop(0)
 if (curr_x, curr_y) in visited or not (0 <= curr_x < width and 0 <= curr_y < height) or board[curr_y][curr_x] != '':
 continue
 visited.add((curr_x, curr_y))
 area += 1
 for dir_x, dir_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
 new_x, new_y = curr_x + dir_x, curr_y + dir_y
 queue.append((new_x, new_y))
 smallest_area = min(smallest_area, area)
 for y in range(height):
 for x in range(width):
 if occupied_tiles + len(visited) == height * width:
 return smallest_area
 if (x, y) not in visited and board[y][x] == '':
 bfs(x, y)
 return smallest_area
 def rotateR(piece_coords):
 return sorted([[y, -x] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
 def rotateH(piece_coords):
 return sorted([[-x, y] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
 def backtrack(piece_index):
 nonlocal result,counter
 counter+=1
 if piece_index == len(sorted_pieces):
 result.append([row[:] for row in board])
 return True
 piece_name, piece_coords = list(sorted_pieces.items())[piece_index]
 reset_coords = piece_coords
 def try_place(x, y, piece_coords, placed_pieces, piece_index):
 if not piece_already_placed(piece_coords, placed_pieces):
 place_piece(piece_coords, x, y, piece_name)
 placed_pieces.append(piece_coords)
 if find_smallest_area() >= 5 and backtrack(piece_index + 1):
 return True
 remove_piece(piece_coords, x, y)
 return False
 for y in range(height):
 for x in range(width):
 if board[y][x] != '':
 continue
 placed_pieces = []
 piece_coords = reset_coords
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 for _ in range (3):
 piece_coords = rotateR(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 piece_coords = reset_coords
 piece_coords = rotateH(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 for _ in range (3):
 piece_coords = rotateR(piece_coords)
 if is_valid_placement(piece_coords, x, y):
 if try_place(x, y, piece_coords, placed_pieces, piece_index):
 return True
 return False
 start_time = datetime.datetime.now()
 backtrack(0)
 print("TOTAL BACKTRACKS",counter)
 print("Time to find: ",(datetime.datetime.now() - start_time).total_seconds(), "sec")
 return result[0]
def sort_pieces_by_length(piece_dict):
 sorted_pieces = dict(sorted(piece_dict.items(), key=lambda item: len(item[1]),reverse=True))
 for piece_name, piece_coords in sorted_pieces.items():
 sorted_pieces[piece_name] = sorted(piece_coords, key=lambda coord: (coord[0], coord[1]))
 return sorted_pieces
def piece_already_placed(new_piece, pieces):
 for piece in pieces:
 if are_pieces_same(new_piece, piece):
 return True
 return False
def are_pieces_same(piece1, piece2):
 # Calculate the biases on x and y axes
 piece1 = [coord.copy() for coord in piece1]
 piece2 = [coord.copy() for coord in piece2]
 for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
 coord1[0] += 10
 coord1[1] += 10
 coord2[0] += 10
 coord2[1] += 10
 piece1 = sorted(piece1, key=lambda coord: (coord[0], coord[1]))
 piece2 = sorted(piece2, key=lambda coord: (coord[0], coord[1]))
 bias_x = piece2[0][0] - piece1[0][0]
 bias_y = piece2[0][1] - piece1[0][1]
 # Check if all corresponding coordinates are the same with the calculated biases
 for coord1, coord2 in zip(piece1, piece2):
 if coord1[0] + bias_x != coord2[0] or coord1[1] + bias_y != coord2[1]:
 return False
 return True
print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]], 'W': [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2]], 'V': [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]], 'X': [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]], 'N': [[0, 0], [0, 1], [1, 1], [1, 2], [1, 3]], 'P': [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]], 'U': [[0, 0], [0, 1], [1, 0], [2, 0], [2, 1]], 'Z': [[0, 0], [1, 0], [1, -1], [1, -2], [2, -2]], 'I': [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 'Y': [[0, 0], [1, 0], [2, 0], [2, 1], [3, 0]], 'T': [[0, 0], [0, 1], [0, 2], [-1, 2], [1, 2]], 'L': [[0, 0], [0, 1], [1, 0], [0, 2], [0, 3]]}))

It finds the correct solution, but I wanted to get all the solutions (or at least few more in a reasonable time). I tried to do some optimization, but I think it 100% it is still falling into unnecessary recursive branches.
It finds one solution in ~22 seconds on my PC. I added print for counter of backtracks called and 23k seems too high.
The ×ばつ12 box has 1010 solutions (Wikipedia).
For sure there are some complex techniques to speed this up, but are there some trivial that could be added to my code?

Thanks for any help.

Answer 1

Kudos on tackling such an interesting problem!

design of Public API

print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]],
 'W': ... }))

On the one hand, I like the simplicity of representation, and the very helpful use of standard pentomino names. On the other hand, I think I'd prefer to see a level of indirection here. And [x, y] coord lists should definitely become (x, y) tuples. (Also, trivially, W ×ばつ H might become a size tuple, whatever.)

pentominos = {
 'F': [(0, 0), (1, 0), (1, -1), (1, 1), (2, 1)],
 'W': ...
}
print(solve((5, 12), 'FWVXNPUZIYTL', pentominos)

or perhaps

print(solve((5, 12), 'FILNPTUVWXYZ', pentominos)

---

tuple over list

A slightly odd thing about python culture is that choice of Sequence matters. Some concepts are a good semantic fit for a tuple, others for a list, as James Tauber explains.

Think of an (x, y) Point as a C struct or a python tuple.

Or consider an invoice spreadsheet showing the sale of half a dozen widgets, with columns part_number, quantity, extended_price. Each row is a 3-tuple. And then we have half a dozen list entries, each of them being a 3-tuple.

With tuples position matters, it changes the meaning of the item. In contrast, a list is a bunch of "same thing", so the initial item and the final one have similar semantics.

Recommend you prefer (x, y) tuples in this code base, rather than the [x, y] lists that are currently implemented.

---

unit tests

This submission tackles a challenging geometry problem.

Yet it includes no automated unit or integration tests. Which makes me sad. And complicates the life of maintainers, or benchmarkers.

---

nested functions

The following functions impress me as being "hard to test":

 def is_valid_placement(piece, x, y): ...
 def place_piece(piece, x, y, char): ...
 def remove_piece(piece, x, y): ...
 def find_smallest_area(): ...
 def bfs(start_x, start_y): ...
 def rotateR(piece_coords): ...
 def rotateH(piece_coords): ...
 def backtrack(piece_index): ... 
 def try_place(x, y, piece_coords, placed_pieces, piece_index): ...

Why? Because they are nested. Sometimes even doubly-nested!

Occasionally nesting can be helpful, when functions should share the same namespace, should have overlapping access to same variables. My standard advice on nesting is simple: Don't. Usually it's not helpful. (I confess this is the very first time I have ever seen someone use double nesting for purposes other than asking whether the interpreter supports arbitrary nesting.)

Here, we are using some very well thought out nesting to organize the code. But it thwarts the efforts of any maintainer who wants to write a simple unit test or wants to produce benchmark timings of two competing implementations, even something as simple as the use of @njit decorator.

Prefer to use modules or classes to organize the code. Alternatively, each of these functions might appear at top-level, just like solve. Use an _ underscore prefix to suggest that a _private helper is not part of the Public API that you're exporting.

I feel it would make sense to introduce class Solver: which knows about a collection of class Pentomino: shapes.

---

lint

 def rotateR( ... ): ...
 def rotateH( ... ): ...

Pep-8 asks that you name these rotate_r and rotate_h.

And then I ask that you spell these out more fully. At first I thought left / right, cw / ccw (or anti-clockwise for my British friends), links / rechts, gauche / droit, but wasn't finding a match. The OP context suggested your native tongue might possibly be Polish, but lewy / prawidłowy doesn't work, and clockwise had too many Z's and W's for a match.

The (y, -x) and (-x, y) transforms suggest that we are Flipping about a mirror axis, rather than Rotating a shape within the plane. Recommend that you choose more informative function names, or at least add a """docstring""" to each one.

The lambdas appear to be superfluous, as each sequence would work on its own.

---

tuple unpack

This code base makes extensive use of [0] subscript to denote x and [1] subscript to denote y.

Prefer to express this as x, y = coords.

Or, much better, define a class:

from collections import namedtuple
Point = namedtuple('Point', 'x y')

---

rotations

def sort_pieces_by_length(piece_dict):
 sorted_pieces = dict(sorted(piece_dict.items(),
 key=lambda item: len(item[1]), reverse=True))

I don't understand this function. In two ways.

It's unclear whether "length" should match "width" or "height". (The [1] subscript tells me "height", but the relationship isn't obvious to me.)

It's unclear why this is even helpful. We alternatively might define max_length as the maximum of a piece's width or height, and then "sort by max_length", in an effort to make "hard to fit" pieces bubble up toward the front.

Maybe "height" is special because of how we iterate over shapes, doing x and y in a certain order? Maybe it's special because pentominos are conventionally defined to be "tall", or "squat"? Maybe there's something else going on here?

Dealing with symmetry is fundamental to solving pentomino-style problems. This codebase should include ReadMe.md or docstrings that describe the approach taken. The L pentomino, for example, has four rotations and then the flipped form has four rotations. It might be worth hanging on to all eight copies, recording them as all part of the same equivalence class, and trying to fit them into the evolving puzzle.

---

use builtins

def piece_already_placed(new_piece, pieces):
 for piece in pieces:
 if are_pieces_same(new_piece, piece):
 return True
 return False

This is:

def piece_already_placed(new_piece, pieces):
 return any(are_pieces_same(new_piece, piece) for piece in pieces)

With judicial use of partial it would be amenable to a map invocation.

It's possible that @lru_cache could help speed this up in nearly its current form, if we're passing around immutable (hashable!) tuples instead of lists.

---

use array for speed

 board = [['' for _ in range(width)] for _ in range(height)]

Lists are nice, but they involve a lot of object pointers. Prefer a python array, or perhaps a numpy ndarray.

A byte array, without all those object pointers, will be smaller and more cache friendly.

If you go the numpy route you will be able to use fast vectorized operations for adding a piece shape to the board, for testing whether a proposed placement caused overlap, and other useful primitives.

---

define a class

Uggh! Put this within class Solver:, please.

 def backtrack( ... ):
 nonlocal result, counter
 counter += 1
 if ... :
 result.append( ... )

The declaration for result appears to be spurious. (While the one for counter is essential.) The lookup should succeed even without a declaration, and then we mutate that object, which is quite different from assigning a new value to counter.

This code appears to be trickier than necessary.

Prefer references to self.counter and self.result.

---

sameness

def are_pieces_same(piece1, piece2):
 # Calculate the biases on x and y axes
 piece1 = [coord.copy() for coord in piece1]
 piece2 = [coord.copy() for coord in piece2]
 for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
 coord1[0] += 10 ...

Thank you for that helpful comment about the magic number 10 -- we're just translating to the positive quadrant, and a pentomino's size will never exceed 5.

The # Calculate ... comment could have been a """docstring""". Except that it wouldn't be a very informative docstring. So I'm left with the (very nice!) function name to explain this function's responsibility.

It leaves me with some questions about what "same" means.

Same w.r.t. translation? rotation? mirror-flipping?

During placement we did some of those transforms. And now it seems we have to undo them to recover the identity of the piece. It makes me sad that we lost track of its identity during placement.

Consider pre-rotating and pre-flipping all pieces at the outset. The "I" pentomino, for example, is quite boring so it will expand to fewer entries than "L" will.

You can write five I's, or five L values, into five cells of board.

You may find it helpful to attach a summary bbox, a width ×ばつ height bounding box, to each piece variant, so e.g. a vertical "I" or a horizontal "I" can be quickly ruled out from certain proposed solutions.

---

This code appears to achieve a subset of its design goals. Speedup is the principle aim of future development. Changes to how we represent pieces, and the board, hold some promise for that.

There are no automated tests in this submission, and substantial changes would be needed in order to introduce them.

I would not be willing to delegate or accept maintenance tasks on this codebase.

• Riomare: Thanks for detailed review, I will update the code based on your recommendations.