seemingly simple number puzzle solutions with speed improvements

seemingly_simple_number_puzzle.py

# uses python3 features
from time import time

# Fast solution for problem from Tomasz Nurkiewicz blog:
# https://www.nurkiewicz.com/2018/09/brute-forcing-seemingly-simple-number.html?utm_source=programmingdigest&utm_medium=email&utm_campaign=featured

# heuristic to greatly speed up from discussion of knights tour problem at
# https://runestone.academy/runestone/static/pythonds/Graphs/KnightsTourAnalysis.html

# by Gerry Jenkins see my channel youtube.com/gjenkinslbcc

N = 14  # size of grid
N2 = N * N


def in_bounds(row, column):  # valid rows in range 1 to N
    return 1 <= row <= N and 1 <= column <= N


def moves_for(row, column):  # return list of tuples (r,c) pairs of moves
    _moves = []
    for delta_row, delta_column in ((-3, 0), (-2, -2), (0, -3), (2, -2), (3, 0), (2, 2), (0, 3), (-2, 2)):
        move_row, move_column = row + delta_row, column + delta_column
        if in_bounds(move_row, move_column):
            _moves.append((move_row, move_column))
    return _moves


# we pre compute all the moves from any grid cell, and using tuple for the cell row and column,
# we can use the cell as lookup key in dictionary

def all_moves():
    _moves = {}
    for row in range(1, N + 1):
        for column in range(1, N + 1):
            _moves[(row, column)] = moves_for(row, column)

    # so higher priority goes to moves with fewer choices (moves near edges first)
    # this tries moves that tend to hang around the edges before moving to center
    # see text in link above for discussion of why
    sorted_moves = list(_moves)
    sorted_moves.sort(key=lambda k: len(_moves[k]))
    sorted_lookup = {}
    for k in sorted_moves:
        _moves[k].sort(key=lambda v: sorted_moves.index(v))
        sorted_lookup[k] = _moves[k]
    return sorted_lookup

# print in grid
def print_solutions(moves):
    for row in range(1, N + 1):
        i_s = [1 + moves.index((row, column)) for column in range(1, N + 1)]
        line = ""
        for i in i_s:
            line += f'{i:4d}'
        print(line)


def solution():
    moves = []
    used_cells = set()
    move_lookup = all_moves()

    def do_move(): # recurse inner method
        possible_moves = [move for move in move_lookup[moves[-1]] if move not in used_cells]
        for next_move in possible_moves:
            moves.append(next_move)
            used_cells.add(next_move)
            if len(moves) == N2:  # solution
                return True
            if do_move():
                return True
            
            moves.pop() # remove new move before return
            used_cells.remove(next_move)
        return False

    for next_move in move_lookup.keys():
        moves.append(next_move)
        used_cells.add(next_move)
        if do_move():
            # solution
            print_solutions(moves)
            return
        moves.pop()
        used_cells.remove(next_move)


t1 = time()
solution()
print("\ntime", time() - t1, 'secs')

# by Gerry Jenkins see my channel youtube.com/gjenkinslbcc