# Solving Pentomino puzzles by using Knuth's Algorithm X

I wrote a program which solves Pentomino puzzles by using Knuth's Algorithm X. My priorities were: readability, straightforwardness and brevity of the solution, so I didn't try to squeeze as much performance as possible by eliminating function calls in some places or similar tricks.

I am interested in:

1. The code review. How this code can be better?

2. Performance improvement. Do you see a way to increase performance? May be numpy can help here? At this moment the fastest version takes 1 hour 57 minutes on Intel i5-2500 to find all solutions of 5 x 12 board. The second version is slower by three times, but it is having less of code duplicity, so it is more beautiful in my opinion - what do you think?

3. Reducing a code duplicity of the faster version but without of large performance drop, as I have in my second version.

### Usage:

5 x 12 board

rows = 5
cols = 12
board = [[0] * cols for _ in range(rows)]
solver = Solver(board, figures, rows, cols, 1)
solver.find_solutions()


Output (partial - the first solution only)

The solution № 1
12 12  5  5  5  5  8  8  7  7  7  7
9 12 12 12  5  6  6  8  7 11  3  3
9  9  9  2  6  6 10  8  8 11  3  3
1  9  1  2  6 10 10 10 11 11 11  3
1  1  1  2  2  2 10  4  4  4  4  4

####################################################################


8 x 8 board with 4 prefilled cells in the middle.

rows = 8
cols = 8
board = [[0] * cols for _ in range(rows)]
board[3][3] = '#'
board[3][4] = '#'
board[4][3] = '#'
board[4][4] = '#'

solver = Solver(board, figures, rows, cols, 1)
solver.find_solutions()


Output (partial)

1614 variants have tried
Time has elapsed: 0:00:05.104412
The solution № 1
12 12  4  4  4  4  4 11
6 12 12 12  5 11 11 11
6  6  5  5  5  5 10 11
8  6  6  #  # 10 10 10
8  8  8  #  #  9 10  7
2  1  8  1  9  9  9  7
2  1  1  1  3  3  9  7
2  2  2  3  3  3  7  7

#################################################################


### The program

The slower version's methods are commented out, remove comments to test it (and comment out corresponding methods of the first version).

#!/usr/bin/python3

from time import time
from datetime import timedelta

figures = {
(
(1,1,1,1,1),
),
(
(1,1,1,1),
(1,0,0,0),
),
(
(1,1,1,1),
(0,1,0,0),
),
(
(1,1,1,0),
(0,0,1,1),
),
(
(1,1,1),
(1,0,1),
),
(
(1,1,1),
(0,1,1),
),
(
(1,1,1),
(1,0,0),
(1,0,0)
),
(
(1,1,0),
(0,1,1),
(0,0,1)
),
(
(1,0,0),
(1,1,1),
(0,0,1)
),
(
(0,1,0),
(1,1,1),
(1,0,0)
),
(
(0,1,0),
(1,1,1),
(0,1,0)
),
(
(1,1,1),
(0,1,0),
(0,1,0)
)
}

class Node():
def __init__(self, value):
self.value = value
self.up = None
self.down = None
self.left = None
self.right = None

def __init__(self, width):
self.width = width
self.size = 0

def append(self, value):
new_node = Node(value)

self.head = left_neigh = right_neigh = up_neigh = down_neigh = new_node
elif self.size % self.width == 0:
left_neigh = right_neigh = new_node
else:
right_neigh = left_neigh.right
if left_neigh is left_neigh.up:
up_neigh = down_neigh = new_node
else:
up_neigh = left_neigh.up.right
down_neigh = up_neigh.down

new_node.up = up_neigh
new_node.down = down_neigh
new_node.left = left_neigh
new_node.right = right_neigh
# Every node has links to the first node of row and column
# These nodes are used as the starting point to deletion and insertion

up_neigh.down = new_node
down_neigh.up = new_node
right_neigh.left = new_node
left_neigh.right = new_node

self.size += 1

def print_list(self, separator=' '):
for col in self.traverse_node_line(row, "right"):
print(col.value, end=separator)
print()

def traverse_node_line(self, start_node, direction):
cur_node = start_node
while cur_node:
yield cur_node
cur_node = getattr(cur_node, direction)
if cur_node is start_node:
break

### First approach - a lot of code duplicity
def col_nonzero_nodes(self, node):
cur_node = node
while cur_node:
yield cur_node
cur_node = cur_node.down
if cur_node is node:
break

def row_nonzero_nodes(self, node):
cur_node = node
while cur_node:
yield cur_node
cur_node = cur_node.right
if cur_node is node:
break

def delete_row(self, node):
cur_node = node
while cur_node:
up_neigh = cur_node.up
down_neigh = cur_node.down

if cur_node is down_neigh:

up_neigh.down = down_neigh
down_neigh.up = up_neigh

cur_node = cur_node.right
if cur_node is node:
break

def insert_row(self, node):
cur_node = node
while cur_node:
up_neigh = cur_node.up
down_neigh = cur_node.down

up_neigh.down = cur_node
down_neigh.up = cur_node

cur_node = cur_node.right
if cur_node is node:
break

def insert_col(self, node):
cur_node = node
while cur_node:
left_neigh = cur_node.left
right_neigh = cur_node.right

left_neigh.right = cur_node
right_neigh.left = cur_node

cur_node = cur_node.down
if cur_node is node:
break

def delete_col(self, node):
cur_node = node
while cur_node:
left_neigh = cur_node.left
right_neigh = cur_node.right

if cur_node is right_neigh:

left_neigh.right = right_neigh
right_neigh.left = left_neigh

cur_node = cur_node.down
if cur_node is node:
break

### Second approach - moving the common parts of code to separate functions.
### Then these functions are used in needed places, instead of duplicating the same code
### every time. But the perfomance was dropped by three times, so I decided to not use this
### methods in the program.
###
#   def delete_node(self, cur_node, a_node, a_neigh, b_node, b_neigh):
#           if cur_node is b_node:
#       setattr(a_node, a_neigh, b_node)
#       setattr(b_node, b_neigh, a_node)
#       self.size -= 1
#
#   def insert_node(self, cur_node, a_node, a_neigh, b_node, b_neigh):
#       setattr(a_node, a_neigh, cur_node)
#       setattr(b_node, b_neigh, cur_node)
#       self.size += 1
#
#   def col_nonzero_nodes(self, node):
#       for cur_node in self.traverse_node_line(node.col_head, "down"):
#               yield cur_node
#
#   def row_nonzero_nodes(self, node):
#       for cur_node in self.traverse_node_line(node.row_head, "right"):
#               yield cur_node
#
#   def delete_row(self, node):
#       for cur_node in self.traverse_node_line(node, "right"):
#           self.delete_node(cur_node, cur_node.up, "down", cur_node.down, "up")
#
#   def delete_col(self, node):
#       for cur_node in self.traverse_node_line(node, "down"):
#           self.delete_node(cur_node, cur_node.left, "right", cur_node.right, "left")
#
#   def insert_row(self, node):
#       for cur_node in self.traverse_node_line(node, "right"):
#           self.insert_node(cur_node, cur_node.up, "down", cur_node.down, "up")
#
#   def insert_col(self, node):
#       for cur_node in self.traverse_node_line(node, "down"):
#           self.insert_node(cur_node, cur_node.left, "right", cur_node.right, "left")

class Solver():
def __init__(self, board, figures, rows, cols, figures_naming_start):
self.rows = rows
self.cols = cols
self.fig_name_start = figures_naming_start
self.figures = figures
self.solutions = set()
self.llist = None
self.start_board = board
self.tried_variants_num = 0

def find_solutions(self):
named_figures = set(enumerate(self.figures, self.fig_name_start))
all_figure_postures = self.unique_figure_postures(named_figures)

self.llist = Linked_list_2D(self.rows * self.cols + 1)
pos_gen = self.generate_positions(all_figure_postures, self.rows, self.cols)

for line in pos_gen:
for val in line:
self.llist.append(val)
self.delete_filled_on_start_cells(self.llist)

self.starttime = time()
self.prevtime = self.starttime
self.dlx_alg(self.llist, self.start_board)

# Converts a one dimensional's element index to two dimensional's coordinates
def num_to_coords(self, num):
row = num // self.cols
col = num - row * self.cols
return row, col

def delete_filled_on_start_cells(self, llist):
row, col = self.num_to_coords(col_head_node.value - 1)
if self.start_board[row][col]:

def print_progress(self, message, interval):
new_time = time()
if (new_time - self.prevtime) >= interval:
print(message)
print(f"Time has elapsed: {timedelta(seconds=new_time - self.starttime)}")
self.prevtime = new_time

def check_solution_uniqueness(self, solution):
reflected_solution = self.reflect(solution)
for sol in [solution, reflected_solution]:
if sol in self.solutions:
return
for _ in range(3):
sol = self.rotate(sol)
if sol in self.solutions:
return
return 1

def dlx_alg(self, llist, board):
# If no rows left - all figures are used
self.print_progress(f"{self.tried_variants_num} variants have tried", 5.0)
self.tried_variants_num += 1
# If no columns left - all cells are filled, the solution is found.
solution = tuple(tuple(row) for row in board)
if self.check_solution_uniqueness(solution):
print(f"The solution № {len(self.solutions) + 1}")
self.print_board(solution)
return
# Search a column with a minimum of intersected rows
# The perfomance optimization - stops branch analyzing if empty columns appears
if min_col_sum == 0:
self.tried_variants_num += 1
return

intersected_rows = []
for node in llist.col_nonzero_nodes(min_col):
# Pick one row (the variant of figure) and try to solve puzzle with it
for selected_row in intersected_rows:
rows_to_restore = []
# If some figure is used, any other variants (postures) of this figure
# could be discarded in this branch
if posture_num_node.value == selected_row.value:
rows_to_restore.append(posture_num_node)
llist.delete_row(posture_num_node)

cols_to_restore = []
for col_node in llist.row_nonzero_nodes(selected_row):
# Delete all rows which are using the same cell as the picked one,
# because only one figure can fill the specific cell
# Delete the columns the picked figure fill, they are not
# needed in this branch anymore
# Pass the shrinked llist and the board with the picked figure added
# to the next processing
self.dlx_alg(llist, new_board)

for row in rows_to_restore:
llist.insert_row(row)

for col in cols_to_restore:
llist.insert_col(col)

def find_min_col(self, llist, min_col):
min_col_sum = float("inf")
tmp = sum(1 for item in llist.col_nonzero_nodes(col))
if tmp < min_col_sum:
min_col = col
min_col_sum = tmp
return min_col, min_col_sum

new_board = prev_steps_result.copy()
for node in self.llist.row_nonzero_nodes(posture_row):
row, col = self.num_to_coords(node.col_head.value - 1)
return new_board

def print_board(self, board):
for row in board:
for cell in row:
print(f"{cell: >3}", end='')
print()
print()
print("#" * 80)

def unique_figure_postures(self, named_figures):
postures = set(named_figures)
for name, fig in named_figures:

all_postures = set(postures)
for name, posture in postures:
for _ in range(3):
posture = self.rotate(posture)

return all_postures
# Generates entries for all possible positions of every figure's posture.
# Then the items of these entires will be linked into the 2 dimensional circular linked list
# The entry looks like:
# figure's name  {board cells filled by figure}  empty board's cells
#            |       | | | | |                       | | |
#            5 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ................
def generate_positions(self, postures, rows, cols):
def apply_posture(name, posture, y, x, wdth, hght):
# Flattening of 2d list
line = [cell for row in self.start_board for cell in row]
# Puts the figure onto the flattened start board
for r in range(hght):
for c in range(wdth):
if posture[r][c]:
num = (r + y) * cols + x + c
if line[num]:
return
line[num] = posture[r][c]
# And adds name into the beginning
line.insert(0, name)
return line
# makes columns header in a llist
yield [i for i in range(rows * cols + 1)]

for name, posture in postures:
posture_height = len(posture)
posture_width = len(posture[0])
for row in range(rows):
if row + posture_height > rows:
break
for col in range(cols):
if col + posture_width > cols:
break
new_line = apply_posture(name, posture, row, col, posture_width, posture_height)
if new_line:
yield new_line

def rotate(self, fig):
return tuple(zip(*fig[::-1]))

def reflect(self, fig):
return tuple(fig[::-1])

• Comments mate, comments. This seems a nice piece of code to dive in and comments might've helped. – Abdur-Rahmaan Janhangeer Dec 3 '19 at 15:41
• @Abdur-RahmaanJanhangeer I heard the opinion that comments overloading isn't good as well as a scarce of them. The idea was something like: "Allow code to speak". So, I didn't make a lot of comments, but have tried to write a "speaking code" instead. The hardest part of the program is algorithm, it has comments in key places. And the algorithm has good explanation in the Wikipedia. Also, I read many source codes of big programs, like CPython - they are not having a lot of comments to explain everything, only for key things, so I did the same. – MiniMax Dec 3 '19 at 16:46
• @Abdur-RahmaanJanhangeer For example, do the insert_col or delete_col methods need comments? – MiniMax Dec 3 '19 at 16:51
• One of the reasons it's hard to get answers to your question is that it's long. Removing those commented out codes shorten it for one thing. One of the non-breaking code reading ways is to write comments after codes code # comment so that the code is read and when not understood, you just glance sideways. What i feel lack is the big picture like a docstring to def dlx_alg(self, llist, board): . Your linkedlist for example is too long. Compare with this – Abdur-Rahmaan Janhangeer Dec 3 '19 at 17:18
• @Abdur-RahmaanJanhangeer I looked at the article about Linked List you gave. There is a simple linked list, not my case. In my case it is a interlinked 2-d matrix, where every node has 4 neighbors: up, down, left, right. And it is customized specially for this program, because the program needs methods to manipulate rows and columns. I didn't find an explanation article about this to give you. May be this will be useful: Dancing Links – MiniMax Dec 3 '19 at 17:55

# Low Hanging Fruit

I obtained a 27% speed-up with one tiny change.

For this speed-up, I didn't want to wait 2 hours for tests to run, so I used a 3x20 board. Elapsed times:

• 0:01:44 - before the change
• 0:01:16 - after the change

I'm sure you'd like to know what the change was. I can't drag it out much more, so here it is. I added this line to the Nodes class:

    __slots__ = ('value', 'up', 'down', 'left', 'right', 'row_head', 'col_head')


This eliminates the __dict__ member of the Nodes objects. So instead of self.down being interpreted as self.__dict__['down'], the value referenced is in a predefined "slot" in the Nodes object. Not only do the references become faster, but the object uses less space, which reduces the memory footprint, which increases locality of reference which again helps performance.

(Adding the __slots__ to Linked_list_2D and Solver didn't change my performance numbers at all.)

# Interface

class Solver():
def __init__(self, board, figures, rows, cols, figures_naming_start):
...


This is an "unfriendly" interface. You have to pass all 5 values to the Solver(). But some of these parameters are redundant.

You've got board and you have rows and cols. Given a board, the Solver could determine rows = len(board) and cols = len(board[0]). Or given rows and cols, the Solver() could construct an empty board.

figures_naming_start is likely always going to be 1. Why not use a default value of 1 for that parameter? Or pass a dictionary to figures with the key names the "name" for the figures. And since figures is a predefined set, why not default it to a class constant?

class Solver():
STANDARD_FIGURES = { 'I' : ((1, 1, 1, 1, 1)),
'Q' : ((1, 1, 1, 1),
(1, 0, 0, 0)),
...
}
def __init__(self, board=None, rows=None, cols=None, figures=STANDARD_FIGURES):
if board is None:
board = [[0] * cols for _ in range(len(rows))]
if rows is None and cols is None:
rows = len(board)
cols = len(board[0])
...


Usage:

solver = Solver(rows=3, cols=20)
solver.find_solutions()


# Finding Solutions

When a solution is found, it is printed. What if you wanted to display it in a GUI of some kind, with coloured tiles?

It would be better for find_solutions() to yield solution, and then the caller could print the solutions, or display them in some fashion, or simply count them:

solver = Solver(rows=3, cols=20)
for solution in solver.find_solutions():
solver.print_board(solution)


# Progress

The progress / timing messages should be presented via the logging module, where they could be printed, or written to a file, or turned off all together.