[Python] How to solve partial Knight's Tour with special constraints

Knight's tour problem described in the image here, with diagram.



A knight was initially located in a square labeled 1. It then proceeded to make a
series of moves, never re-visiting a square, and labeled the visited squares in
order. When the knight was finished, the labeled squares in each region of connected
squares had the same sum.

A short while later, many of the labels were erased. The remaining labels can be seen
above.

Complete the grid by re-entering the missing labels. The answer to this puzzle is
the sum of the squares of the largest label in each row of the completed grid, as in
the example.

[1]: E.g. the 14 and 33 are in different regions.


The picture explains it a lot more clearly, but in summary a Knight has gone around a 10 x 10 grid. The picture shows a 10 x 10 board that shows some positions in has been in, and at what point of its journey. You do not know which position the Knight started in, or how many movements it made.

The coloured groups on the board need to all sum to the same amount.

I’ve built a python solver, but it runs for ages - uses recursion. I’ve noted that the maximum sum of a group is 197, based on there being 100 squares and the smallest group is 2 adjacent squares.

My code at this link: https://pastebin.com/UMQn1HZa

import sys, numpy as np

fixedLocationsArray = [[ 12, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 5, 0, 23, 0],
[ 0, 0, 0, 0, 0, 0, 8, 0, 0, 0],
[ 0, 0, 0, 14, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 2, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 20, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 33, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 28]]

groupsArray = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0,10, 0],
[0, 0, 0, 1, 0, 0, 0, 0,10, 0],
[0, 0, 1, 1, 1, 1, 9,10,10,10],
[2, 0, 1, 0, 0,11, 9, 9, 9, 9],
[2, 0, 0, 0,11,11,11,15,15, 9],
[2, 4, 4,14,11,12,12,15,15, 8],
[2, 3, 4,14,14,13,13,13,15, 8],
[2, 3, 5,14,16,16,16, 7, 7, 8],
[3, 3, 5, 6, 6, 6, 6, 6, 7, 8]]

'''
Solver
- Noted that the maximum sum of a group is 197 since the group of only 2 can have the 100 filled and then 97 on return
'''

class KnightsTour:
def __init__(self, width, height, fixedLocations, groupsArray):
self.w = width
self.h = height
self.fixedLocationsArray = fixedLocations
self.groupsArray = groupsArray
self.npfixedLocationsArray = np.array(fixedLocations)
self.npgroupsArray = np.array(groupsArray)

self.board = [] # Contains the solution
self.generate_board()

def generate_board(self):
"""
Creates a nested list to represent the game board
"""
for i in range(self.h):
self.board.append([0]*self.w)

def print_board(self): # Prints out the final board solution
print(" ")
print("------")
for elem in self.board:
print(elem)
print("------")
print(" ")

def generate_legal_moves(self, cur_pos, n):
"""
Generates a list of legal moves for the knight to take next
"""
possible_pos = []
move_offsets = [(1, 2), (1, -2), (-1, 2), (-1, -2),
(2, 1), (2, -1), (-2, 1), (-2, -1)]

locationOfNumberInFixed = [(ix,iy) for ix, row in enumerate(self.fixedLocationsArray) for iy, i in enumerate(row) if i == n+1]
groupsizeIsNotExcessive = self.groupsNotExcessiveSize(self.board, self.groupsArray)

for move in move_offsets:
new_x = cur_pos[0] + move[0]
new_y = cur_pos[1] + move[1]
new_pos = (new_x, new_y)

if groupsizeIsNotExcessive:
if locationOfNumberInFixed:
print(f"This number {n+1} exists in the fixed grid at {locationOfNumberInFixed[0]}")
if locationOfNumberInFixed[0] == new_pos:
print(f"Next position is {new_pos} and matches location in fixed")
possible_pos.append((new_x, new_y))
else:
continue
elif not locationOfNumberInFixed: # if the current index of move is not in table, then evaluate if it is a legal move
if (new_x >= self.h): # if it is out of height of the board, continue, don't app onto the list of possible moves
continue
elif (new_x < 0):
continue
elif (new_y >= self.w):
continue
elif (new_y < 0):
continue
else:
possible_pos.append((new_x, new_y))
else:
continue

print(f"The legal moves for index {n} are {possible_pos}")
print(f"The current board looks like:")
self.print_board()

return possible_pos

def sort_lonely_neighbors(self, to_visit, n):
"""
It is more efficient to visit the lonely neighbors first,
since these are at the edges of the chessboard and cannot
be reached easily if done later in the traversal
"""
neighbor_list = self.generate_legal_moves(to_visit, n)
empty_neighbours = []

for neighbor in neighbor_list:
np_value = self.board[neighbor[0]][neighbor[1]]
if np_value == 0:
empty_neighbours.append(neighbor)

scores = []
for empty in empty_neighbours:
score = [empty, 0]
moves = self.generate_legal_moves(empty, n)
for m in moves:
if self.board[m[0]][m[1]] == 0:
score[1] += 1
scores.append(score)

scores_sort = sorted(scores, key = lambda s: s[1])
sorted_neighbours = [s[0] for s in scores_sort]
return sorted_neighbours

def groupby_perID_and_sum(self, board, groups):

# Convert into numpy arrays
npboard = np.array(board)
npgroups = np.array(groups)

# Get argsort indices, to be used to sort a and b in the next steps
board_flattened = npboard.ravel()
groups_flattened = npgroups.ravel()

sidx = groups_flattened.argsort(kind='mergesort')
board_sorted = board_flattened[sidx]
groups_sorted = groups_flattened[sidx]

# Get the group limit indices (start, stop of groups)
cut_idx = np.flatnonzero(np.r_[True,groups_sorted[1:] != groups_sorted[:-1],True])

# Create cut indices for all unique IDs in b
n = groups_sorted[-1]+2
cut_idxe = np.full(n, cut_idx[-1], dtype=int)

insert_idx = groups_sorted[cut_idx[:-1]]
cut_idxe[insert_idx] = cut_idx[:-1]
cut_idxe = np.minimum.accumulate(cut_idxe[::-1])[::-1]

# Split input array with those start, stop ones
arrayGroups = [board_sorted[i:j] for i,j in zip(cut_idxe[:-1],cut_idxe[1:])]
arraySum = [np.sum(a) for a in arrayGroups]

sumsInListSame = arraySum.count(arraySum[0]) == len(arraySum)

return sumsInListSame

def groupsNotExcessiveSize(self, board, groups):
# Convert into numpy arrays
npboard = np.array(board)
npgroups = np.array(groups)

# Get argsort indices, to be used to sort a and b in the next steps
board_flattened = npboard.ravel()
groups_flattened = npgroups.ravel()

sidx = groups_flattened.argsort(kind='mergesort')
board_sorted = board_flattened[sidx]
groups_sorted = groups_flattened[sidx]

# Get the group limit indices (start, stop of groups)
cut_idx = np.flatnonzero(np.r_[True,groups_sorted[1:] != groups_sorted[:-1],True])

# Create cut indices for all unique IDs in b
n = groups_sorted[-1]+2
cut_idxe = np.full(n, cut_idx[-1], dtype=int)

insert_idx = groups_sorted[cut_idx[:-1]]
cut_idxe[insert_idx] = cut_idx[:-1]
cut_idxe = np.minimum.accumulate(cut_idxe[::-1])[::-1]

# Split input array with those start, stop ones
arrayGroups = [board_sorted[i:j] for i,j in zip(cut_idxe[:-1],cut_idxe[1:])]
arraySum = [np.sum(a) for a in arrayGroups]
print(arraySum)

# Check if either groups aren't too large
groupSizeNotExcessive = all(sum <= 197 for sum in arraySum)

return groupSizeNotExcessive

def tour(self, n, path, to_visit):
"""
Recursive definition of knights tour. Inputs are as follows:
n = current depth of search tree
path = current path taken
to_visit = node to visit, i.e. the coordinate
"""
self.board[to_visit[0]][to_visit[1]] = n # This writes the number on the grid
path.append(to_visit) #append the newest vertex to the current point
print(f"Added {n}")
print(f"For {n+1} visiting: ", to_visit)


if self.groupby_perID_and_sum(self.board, self.npgroupsArray): #if all areas sum
self.print_board()
print(path)
print("Done! All areas sum equal")
sys.exit(1)

else:
sorted_neighbours = self.sort_lonely_neighbors(to_visit, n)
for neighbor in sorted_neighbours:
self.tour(n+1, path, neighbor)

#If we exit this loop, all neighbours failed so we reset
self.board[to_visit[0]][to_visit[1]] = 0
try:
path.pop()
print("Going back to: ", path[-1])
except IndexError:
print("No path found")
sys.exit(1)


if __name__ == '__main__':
#Define the size of grid. We are currently solving for an 8x8 grid

kt0 = KnightsTour(10, 10, fixedLocationsArray, groupsArray)

kt0.tour(1, [], (3, 0))
# kt0.tour(1, [], (7, 0))
# kt0.tour(1, [], (7,2))
# kt0.tour(1, [], (6,3))
# kt0.tour(1, [], (4,3))
# kt0.tour(1, [], (3,2))

# startingPositions = [(3, 0), (7, 0), (7,2), (6,3), (4,3), (3,2)]

kt0.print_board()

Continue reading...