In the time before ‘Tetris’
Before ‘Tetris’, if you wanted to stack smaller pieces into bigger areas, you could play with the Tenyo puzzles called “Beat the Computer”.
These puzzles were pocket-sized containers with a bestiary of pre-cut pieces - you tipped them out and then tried to fit them back in.
They were really difficult!
Below are puzzle numbers 783 and 6 in this series.
Finding all 9356 solutions to Puzzle No 5
This puzzle challenges you to fit the complete set of 12 pentominos into a 6x10 space.
According to the instructions for Puzzle No. 5, there are 2339 unique solutions to this puzzle. If reflections along both axes are considered then there are 2339 * 4 = 9356 solutions.
The code which follows finds all solutions by:
- modelling each piece as a set of indices defining its shape
- using recursive backtracking to try and place each piece in turn
It takes about 15 minutes to find all solutions - about 10 solutions/second.
The following 50 minute video shows all the solutions (at a rate of 3 solutions per second)
suppressPackageStartupMessages({
library(dplyr)
library(purrr)
library(tidyr)
})
# Reference and naming scheme from:
# https://en.wikipedia.org/wiki/Pentomino
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
w <- 10 # width of space to place pentominos
h <- 6 # height of space to place pentominos
buf <- 5 - 1 # maximum safety buffer around placement area
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Create a board to contain the placement area.
# The buffer arund the outside is to ensure that any piece that starts within
# the placement area, will not be out of bounds of the board.
# Use '1' to indicate that the space is occupied.
# Use '0' to indicate an empty space into which a pentomino may be placed
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
board <- matrix(1L, nrow = h + 2 * buf, ncol = w + 2 * buf)
for (i in seq(h)) {
board[buf + i, buf + seq(w)] <- 0L
}
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Pentominoes as matrices
# Naming scheme follows wikipedia: https://en.wikipedia.org/wiki/Pentomino
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pent_mats <- list(
I = matrix(c(
1, 1, 1, 1, 1
), nrow = 1, ncol = 5, byrow = TRUE),
F = matrix(c(1, 0, 0,
1, 1, 1,
0, 1, 0), nrow=3, byrow = TRUE),
L = matrix(c(1, 1, 1, 1,
1, 0, 0, 0), nrow = 2, byrow = TRUE),
P = matrix(c(1, 1, 0,
1, 1, 1), nrow = 2, byrow = TRUE),
N = matrix(c(0, 1, 1, 1,
1, 1, 0, 0), nrow = 2, byrow = TRUE),
T = matrix(c(1, 1, 1,
0, 1, 0,
0, 1, 0), nrow = 3, byrow = TRUE),
U = matrix(c(1, 0, 1,
1, 1, 1), nrow = 2, byrow = TRUE),
V = matrix(c(0, 0, 1,
0, 0, 1,
1, 1, 1), nrow = 3, byrow = TRUE),
W = matrix(c(1, 0, 0,
1, 1, 0,
0, 1, 1), nrow = 3, byrow = TRUE),
X = matrix(c(0, 1, 0,
1, 1, 1,
0, 1, 0), nrow = 3, byrow = TRUE),
Y = matrix(c(0, 0, 1, 0,
1, 1, 1, 1), nrow = 2, byrow = TRUE),
Z = matrix(c(1, 0, 0,
1, 1, 1,
0, 0, 1), nrow = 3, byrow = TRUE)
)
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Check that they're all pentominoes
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
stopifnot(all(map_dbl(pent_mats, sum) == 5))
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Plot the board
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plot_board <- function(x) {
# trim the board
x <- x[buf + seq(h), buf + seq(w)]
image(t(x), asp=6/10, col = RColorBrewer::brewer.pal(12, 'Paired'), axes = F, ann = F)
}
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Convert a piece matrix to a vector of indices
#'
#' @param piece_mat integer matrix with values 0/1 to represent piece layout
#' @param rows how many rows are in the matrix this will be superimposed upon?
#' @return integer vetor of offsets of the locations in this piece
#'
#' @examples
#' piece_to_idx(pent_mats[[1]], rows = nrow(board))
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
piece_to_idx <- function(piece_mat, rows) {
# Find all the locations in the matrix as (row, col) coords
coords <- arrayInd(which(piece_mat > 0), dim(piece_mat))
# Offset set to first part of piece
offset <- which(piece_mat >= 1)[1]
coords[, 1] <- coords[,1] - offset
idx <- (coords[,2] - 1L) * rows + coords[,1]
idx
}
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Matrix manipulation functions. Nothing fancy - only called during setup.
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rot90 <- function(x) {
x <- t(x)
x <- x[rev(seq(nrow(x))),,drop=FALSE]
x
}
rot180 <- function(x) rot90(rot90(x))
rot270 <- function(x) rot90(rot90(rot90(x)))
mirror <- function(x) {
x[rev(seq(nrow(x))), , drop=FALSE]
}
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Convert the pentomino matrices into lists of indices
#
# Add all rotated versions of all pieces as well.
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
all_pents <- map(pent_mats, function(x) {
list(
piece_to_idx(x , rows = nrow(board)),
piece_to_idx(rot90(x) , rows = nrow(board)),
piece_to_idx(rot180(x), rows = nrow(board)),
piece_to_idx(rot270(x), rows = nrow(board))
)
})
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Pieces which need to also have mirrored counterparts
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mirror_pieces <- c('F', "L", 'P', 'N', 'Y', 'Z')
for (letter in mirror_pieces) {
x <- mirror(pent_mats[[letter]])
all_pents[[letter]][[5]] <- piece_to_idx( x , rows = nrow(board))
all_pents[[letter]][[6]] <- piece_to_idx( rot90(x) , rows = nrow(board))
all_pents[[letter]][[7]] <- piece_to_idx( rot180(x), rows = nrow(board))
all_pents[[letter]][[8]] <- piece_to_idx( rot270(x), rows = nrow(board))
}
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Remove duplicates.
# * 'I' piece only exists as horizontal and vertical. Rotated versions are dupes.
# * 'X' only needs a single piece as all rotations are identical
# * 'Z' some rotations are duplicates of existing
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
all_pents[['I']][[4]] <- NULL
all_pents[['I']][[3]] <- NULL
all_pents[['X']][[4]] <- NULL
all_pents[['X']][[3]] <- NULL
all_pents[['X']][[2]] <- NULL
all_pents[['Z']][[8]] <- NULL
all_pents[['Z']][[7]] <- NULL
all_pents[['Z']][[4]] <- NULL
all_pents[['Z']][[3]] <- NULL
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Assign a number ('val') to use for each piece. This is the number that will be
# written to the 'board' matrix for this piece.
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
all_pents <- map(1:12, function(x) {
list(
val = x,
piece_indices = all_pents[[x]]
)
})
#=============================================================================
#=============================================================================
#
# Everything above this comment is just prepping the data structures
#
# Everything below this comment is the recursive backtracking
#
#=============================================================================
#=============================================================================
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Place a piece on the board
#'
#' @param board integer matrix of an appropriate size
#' @param idx location on board to place piece
#' @param piece_indices integer vector of offsets which define the piece
#' @param val integer value to write into the board
#'
#' @return copy of 'board' with piece if placement is valid. Otherwise 'NULL'
#' @example
#' place_piece(board, 106, all_pents[[12]]$piece_indices[[1]], 99)
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
place_piece <- function(board, idx, piece_indices, val) {
current_vals <- board[idx + piece_indices]
if (any(current_vals > 0)) {
return(NULL)
}
board[idx + piece_indices] <- val
board
}
count <- 0L
zz <- NULL
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Fill a board with the given set of pentominos
#'
#' Recursive placement of pentominos with backtracking
#'
#' @param board integer matrix
#' @param pents list of pentoninos i.e. `all_pents`
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fill_board <- function(board, pents) {
# Ran out of pentominos => must be a solution!
if (length(pents) == 0L) {
count <<- count + 1L
# Save image
if (FALSE) {
filename <- sprintf("images/%04i.png", count)
png(filename, width = 480, height = 320)
par(mar=c(0, 0, 0, 0))
plot_board(board)
dev.off()
}
# be verbose about number of solutions found so far
if (count %% 100 == 0) cat(count, "")
return()
}
# Where's the next location in the board that we can place a pentomino?
idx <- which(board == 0)[1]
# Try and place each pentomino at the current position.
# If the placement is valid, recursively call 'fill_board' with the
# latest version of the board, and the updated list of pentominos
for (i in seq_along(pents)) {
val <- pents[[i]]$val
all_piece_indices <- pents[[i]]$piece_indices
for (piece_indices in all_piece_indices) {
new_board <- place_piece(board, idx, piece_indices, val = val)
if (!is.null(new_board)) {
fill_board(new_board, pents[-i])
}
}
}
}#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# It takes about 15 minutes to generate all 9356 solutions - about 10 solns/second
# Note: Mirrored and flipped solutions are included.
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fill_board(board, all_pents)