Knight Tour

knight_tour.py

"""
  There is a disagreement regarding the original reference handling the
lambda key.
  And there is no need to find a closed patrol path here. Modify the extend
function

Refs.
original https://linuxgazette.net/110/kapil.html#denouement
wiki https://en.wikipedia.org/wiki/Knight%27s_tour
WolframMathWord https://mathworld.wolfram.com/KnightGraph.html
"""
KNIGHT_MOVES = [
    (-1, -2), (-2, -1),
    (1, -2), (-2, 1),
    (-1, 2), (2, -1),
    (1, 2), (2, 1)]


def add(pos, move):
    """
    position to next position
    :param pos:
    :param move:
    :return:
    """
    return pos[0] + move[0], pos[1] + move[1]


def is_on_board(pos):
    """
    move to next position P, P is on board m * n.
    :param pos:
    :return:
    """
    return (pos[0] >= 0) and \
           (pos[0] <= 7) and \
           (pos[1] >= 0) and \
           (pos[1] <= 7)


def moves(pos):
    """
    Possible next positions of a knight
    :param pos:
    :return:
    """
    return list(filter(
        is_on_board,
        [add(pos, move) for move in KNIGHT_MOVES]
    ))


def allow_moves(pos, solution):
    """
    Possible next positions of a knight, which Not yet passed.
    :param pos:
    :param solution:
    :return:
    """

    def predicate(p):
        return not (p in solution)

    return list(filter(
        predicate,
        [new_pos for new_pos in moves(pos)]
    ))


def comp_key(pos, solution):
    """
    Number of allow_moves
    :param pos:
    :param solution:
    :return:
    """
    return len(allow_moves(pos, solution))


def sorted_moves(solution):
    """
    solution ==[passed] == [lasted_passed,recent_passed]
    lasted_passed = solution[0]
    recent_passed = solution[1:]

      find next move, which p-move->new_p, new_p has smallest allow_moves.

      This is a greedy algorithm,
    and the number of branches generated in the next step is the least.

    :param solution:
    :return:
    """

    array = allow_moves(solution[0], solution[1:])
    array.sort(key=lambda x: comp_key(x, solution))
    return array


def extend(solution):
    if len(solution) == 64:
        return solution
    else:
        for new_pos in sorted_moves(solution):
            sol = extend([new_pos] + solution)
            if sol is False:
                continue
            else:
                return sol
        return False


def print_sol(solution):
    line = "-"
    for i in range(8):
        for j in range(8):
            line = line + "-----"
        print(line)
        line = "|"
        for j in range(8):
            line = line + " %2i |" % (64 - solution.index((i, j)))
        print(line)
        line = "-"
    for j in range(8):
        line = line + "-----"
    print(line)


if __name__ == '__main__':
    print_sol(extend([(0, 0)]))