# 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 = [ * 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 = [ * cols for _ in range(rows)]
board = '#'
board = '#'
board = '#'
board = '#'

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)
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 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 at 16:46
• @Abdur-RahmaanJanhangeer For example, do the insert_col or delete_col methods need comments? – MiniMax Dec 3 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 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 at 17:55