6 minutes
Katamino
Katamino is a puzzle game where the goal is to fit a set of pieces on a board.
I played a lot with this game as a kid, but I figured it would also be a good puzzle to write a program that can solve it. This is a typical problem of recursive algorithm where one can write a function that takes the current board as input as well as the remaining pieces to place on the board. This function places one piece on the board and then calls itself again with the new board and the pieces minus the one that was just placed on the board.
It gives us the following solver function, which is fairly simple:
def solve_katamino(board, pieces):
# Make sure the puzzle is solvable
assert np.sum(board.board == 0)//5 == len(pieces)
if len(pieces) == 0:
return True, board
# Pick first piece
piece = pieces[0]
# Finds the different possible orientations for this piece
oriented_pieces = piece.orientations()
for oriented_piece in oriented_pieces:
# Finds the possible ways to place that piece on the board
possible_boards = board.possibilities(oriented_piece)
# Loop through each possibility and recursively call main function
for possible_board in possible_boards:
sol, b = solve_katamino(possible_board, pieces[1:])
if sol:
return True, b
return False, NoneI decided to represent each piece as a list of 0 and 1. For example the orange piece is:
'orange':[[1,0,0,0],
[1,1,1,1]]And I built a Piece class to be able to flip and rotate each piece in order to give all the possible orientations of a piece via the orientations method. Note here that duplicates orientations are removed by overriding the built-in method __eq__. As a result, the piece [[1,1,1,1,1]] will have 2 orientations (one horizontal and one vertical) while more complex shapes like the orange piece above have 8.
Finally, we need to implement a Board class to keep track of where we placed the pieces during the search. This is where we implement the possibilities method which is a key part of our main function and enumerates the possible boards that can be made with the oriented piece.
First, we get the list of valid_locations where this piece can be placed on the board within its limits (regardless of what is on the board at this point), then loops through each location and place the piece on the board with place_piece and check whether the piece is sitting on another piece.
The last (and defintely not least) thing we need to check is whether the board we have is even a valid one and worth pursuing further. Let's take an example. Imagine you placed the orange piece on the board and it looks like this:
[[0,1,0,0],
[0,1,0,0],
[0,1,0,0],
[1,1,0,0],
[0,0,0,0]]Well this board is not worth continuing because no piece can ever fit in the hole left in the upper left corner. Because there is only 3 empty squares left and katamino pieces are all of size 5. So in order to do that, we run a Breadth-First-Search on the 0 on the board and check that the remaining holes are all multiples of 5 so that there is the possibility for a piece to fit.
import numpy as np
class Piece:
def __init__(self, p, name, i):
self.p = np.array(p)
self.h, self.w = self.p.shape
self.name = name
self.id = i
self.shape = self.p.shape
def mirror(self):
new_orientation = np.fliplr(self.p)
return Piece(new_orientation, self.name, self.id)
def rotate(self, r):
new_orientation = np.rot90(self.p, r)
return Piece(new_orientation, self.name, self.id)
def orientations(self):
orientations = []
for r in range(4):
rot = self.rotate(r)
if all(rot != p for p in orientations):
orientations.append(rot)
for r in range(4):
rot = self.mirror().rotate(r)
if all(rot != p for p in orientations):
orientations.append(rot)
return orientations
def __eq__(self, other):
return self.shape == other.shape and np.all(self.p == other.p)
class Board:
def __init__(self, size=4, b=None):
if b is None:
self.board = np.array([[0] * size,
[0] * size,
[0] * size,
[0] * size,
[0] * size])
else:
self.board = b
self.H, self.W = self.board.shape
self.sol = []
@classmethod
def from_solution(cls, sol):
b = Board(size=len(sol))
for piece, loc in sol:
b = b.place_piece(piece, loc, use_id=True)
return b
def valid_locations(self, piece):
valid_loc = []
for i in range(0, self.H - piece.h + 1):
for j in range(0, self.W - piece.w + 1):
valid_loc.append((i,j))
return valid_loc
def place_piece(self, piece, loc, use_id=False):
i,j = loc
b = self.board.copy()
if use_id:
b[i:i+piece.h,j:j+piece.w] = b[i:i+piece.h,j:j+piece.w] + piece.id*piece.p
else:
b[i:i+piece.h,j:j+piece.w] += piece.p
board = Board(b=b)
board.sol = self.sol + [(piece, loc)]
return board
def is_finished(self):
return np.all(self.board == 1)
def possibilities(self, piece):
possible_boards = []
valid_locations = self.valid_locations(piece)
for loc in valid_locations:
new_board = self.place_piece(piece, loc)
# Check if the piece is over another one
if np.any(new_board.board == 2):
continue
# Check if it's even worth continuing...
ccs = connected_components(new_board.board, 0)
if any(len(cc) % 5 != 0 for cc in ccs):
continue
else:
possible_boards.append(new_board)
return possible_boards
def bfs(M, i, j, value=0):
"""
Breadth First Search algorithm implementation on a binary matrix
start_loc = (i,j)
Returns an island = list of tuples
"""
if M[i, j] != value:
return []
visited = set([(i,j)])
queue = [(i,j)]
while len(queue) > 0:
x, y = queue.pop(0)
neighbors = neighboring_squares(M, x, y, value)
for neighbor in neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return list(visited)
def neighboring_squares(M, i, j, value):
"""
Returns the list of connected land from a location
"""
m, n = M.shape
neighboring_squares = []
if i > 0 and M[i-1,j] == value:
neighboring_squares.append((i-1,j))
if i < m - 1 and M[i+1,j] == value:
neighboring_squares.append((i+1,j))
if j > 0 and M[i,j-1] == value:
neighboring_squares.append((i,j-1))
if j < n - 1 and M[i,j+1] == value:
neighboring_squares.append((i,j+1))
return neighboring_squares
def connected_components(M, value):
"""Return the set of connected components (a list of sets) of the matrix"""
x, y = np.where(M == value)
remaining_squares = set([t for t in zip(x, y)])
connected_components = []
while len(remaining_squares) > 0:
random_square = remaining_squares.pop()
remaining_squares.add(random_square)
cc = bfs(M, random_square[0], random_square[1], value)
connected_components.append(cc)
for square in cc:
remaining_squares.remove(square)
return connected_componentsNow solving the puzzles takes between 1sec and ~5min on my 2017 Mac (1.8GHz Intel Core) depending on the number of pieces in the puzzle. The results look like below:
PIECES = {'lightbrown': [[1,1,1,1,1]],
'orange':[[1,0,0,0],
[1,1,1,1]],
'darkbrown': [[0,1,0,0],
[1,1,1,1]],
'purple': [[1,1,0,0],
[0,1,1,1]],
'darkblue': [[1,0,0],
[1,0,0],
[1,1,1]],
'pink': [[1,1,1],
[1,1,0]],
'yellow': [[1,0,1],
[1,1,1]],
'lightblue': [[1,1,0],
[0,1,0],
[0,1,1]],
'grey': [[0,1,1],
[1,1,0],
[0,1,0]],
'darkgreen': [[1,1,1],
[0,1,0],
[0,1,0]],
'lightgreen':[[1,1,0],
[0,1,1],
[0,0,1]],
'red': [[0,1,0],
[1,1,1],
[0,1,0]]
}
PROBLEMS = [[2,3,6,11,8,4,5,10,9,1,7],
[2,3,7,9,8,5,6,4,10,1,12]]
pieces = {i+1:Piece(p, name, i+1) for i, (name, p) in enumerate(PIECES.items())}
k = 0
n = 6
katamino_problem = PROBLEMS[k][:n]
board = Board(size=n)
found_solution, b = solve_katamino(board, [pieces[i] for i in katamino_problem])
if found_solution:
board_solved = Board.from_solution(b.sol)
print(board_solved.board)And the output is:
[[4, 3, 3, 3, 3,11],
[4, 8, 8, 3,11,11],
[4, 4, 8,11,11, 6],
[2, 4, 8, 8, 6, 6],
[2, 2, 2, 2, 6, 6]]1131 Words
2024-11-01 14:57