Как рекурсивно добавить узлы (в режиме поиска в глубину) к n-дереву, чтобы решить головоломку 4x4?

Question

Я в своем уме ... это мой первый пост, надеюсь, вы, ребята, можете мне помочь.

У меня есть сетка головоломки 4x4 (начальное состояние), которая выглядит следующим образом: X - единственный, кто может двигаться, и делает это, меняя значения

Конец игры - когда плитки ABC выглядят так: X не имеет значения, где он заканчивается

Мне нужно решить эту проблему, добавив узлы (с настольной игрой в нем) в n-дерево (корень - начальное состояние), но я должен сделать это, напоминая поиск в глубину, здесь я приведу пример:

Максимальная глубина составляет 2

моя проблема в том, что когда я пытаюсь добавить больше узлов, но я достигаю максимальной глубины, я должен иметь возможность добавить их в доступный узел с максимальной глубиной -1 (например, процедура поиска в глубину)

Я читал и смотрю учебные пособия в течение 2 дней, и все они показывают мне, как пройти по уже построенному дереву, но не как его создать. Я добавлю мои 2 класса (настольная игра и дерево), надеюсь, кто-нибудь может указать мне правильное направление.

N = 4

класс BoardGame:

board = []

def start_game(self):
    self.board = ["0"] * N
    for c in range(N):
        self.board[c] = ["0"] * N
    self.board[N - 1][0] = "A"
    self.board[N - 1][1] = "B"
    self.board[N - 1][2] = "C"
    self.board[N - 1][3] = "X"

def end_game(self):
    if self.board[1][1] == "A" and self.board[2][1] == "B" and self.board[3][1] == "C":
        return True
    else:
        return False

def draw_board(self):
    print("Board:")
    for j in range(N):
        print()
        for k in range(N):
            print(self.board[j][k], end='')
    print()

def find_x(self):
    found_x = False
    for j in range(N):
        for k in range(N):
            if self.board[j][k] == "X":
                found_x = True
                break
        if found_x:
            break
    return j, k

def possible_moves(self):
    x = self.find_x()
    # corner 1
    if x == (0, 0):
        return ["Right", "Down"]
    # corner 2
    if x == (0, 3):
        return ["Left", "Down"]
    # corner 3
    if x == (3, 0):
        return ["Up", "Right"]
    # corner 4
    if x == (3, 3):
        return ["Up", "Left"]
    # top sides
    if x == (0, 1) or x == (0, 2):
        return ["Left", "Right", "Down"]
    # left sides
    if x == (1, 0) or x == (2, 0):
        return ["Up", "Right", "Down"]
    # right sides
    if x == (1, 3) or x == (2, 3):
        return ["Up", "Left", "Down"]
    # bottom sides
    if x == (3, 1) or x == (3, 2):
        return ["Up", "Left", "Right"]
    # center
    else:
        return["Up", "Left", "Right", "Down"]

def move(self, movement):
    x = self.find_x()
    j = x[0]
    k = x[1]
    if movement == "Up":
        # print("Moving X Up")
        aux = self.board[j-1][k]
        self.board[j][k] = aux
        self.board[j-1][k] = "X"
    elif movement == "Left":
        # print("Moving X Left")
        aux = self.board[j][k-1]
        self.board[j][k] = aux
        self.board[j][k-1] = "X"
    elif movement == "Right":
        # print("Moving X Right")
        aux = self.board[j][k + 1]
        self.board[j][k] = aux
        self.board[j][k + 1] = "X"
    elif movement == "Down":
        # print("Moving X Down")
        aux = self.board[j + 1][k]
        self.board[j][k] = aux
        self.board[j + 1][k] = "X"
    else:
        print("Something went wrong")

а это моё классное дерево:

class Node(object):
from Puzzle import BoardGame
from random import shuffle
import sys
import copy

sys.setrecursionlimit(10000)                                # 10000 is an example, try with different values
max_depth = 3

    def __init__(self):

        self.value = ""                 # Value of the node "Up", "Left", "Right", "Down"
        self.depth = 0                  # Depth of the node
        self.bg = BoardGame()           # New board game
        self.bg.start_game()            # Initial state board game
        self.children = []              # Empty list of children nodes
        self.parent = None

    '''
    When treating children as string returns the 
    value of the node not the memory location
    '''
    def __str__(self):
        return self.value

    '''
    When using iterators (for, next etc) it does not create a list only shows the value
    and destroys it
    '''
    def __iter__(self):

        yield self
        for c in self.children:
            for node in c:
                yield node

    # check if board in current node is goal
    def is_node_goal(self):
        return self.bg.end_game()

    def show_node(self):
        print("value:", self.value, "Depth:", self.depth)
        if self.children:
            print("Children: ", end='[ ')
            for c in self.children:
                print(c, end=' ')
            print("]")
        else:
            print("Children: ")
        #self.bg.draw_board()
        print("------------")
        print()


def show_tree(node):
    if node.value == "":
        node.show_node()
    if node.children:
        for ch in node.children:
            ch.show_node()
        for ch in node.children:
            show_tree(ch)


def insert_children(node):
    if not node.children:                                   # if node doesnt have children
        pm = node.bg.possible_moves()                       # shuffle randomly possible moves
        #shuffle(pm)
        node.visited = True
        for v in pm:
            new_node = Node()                               # Creates a Node
            new_node.value = v                              # Assign value of new node
            new_node.depth = node.depth + 1                 # Add one level of depth to the three
            new_node.parent = node                          # address of the parent
            new_node.bg = copy.deepcopy(node.bg)            # Create a copy of parents board game
            new_node.bg.move(new_node.value)                # Moves node board game to the value
            node.children.append(new_node)                  # Add this new node to the list of parent children
        return True
    else:
        return False


def dfs(node):
    if node.depth + 1 <= max_depth:
        if not node.children:
            insert_children(node)
        else:
            dfs(node.children[0])


n = Node()
for r in range(3):
    dfs(n)

show_tree(n)