The question

Recently, we will do a question. The meaning of the question is:

With as few steps as possible, as short as possible time, the number of squares on the board, according to the order from left to right, from top to bottom rearranged orderly

1. First determine whether it is reachable

2. Secondly, three algorithms are used to solve the problem

A. Depth-first search

B. Breadth-first search

C. Iteratively deepened depth-first search

[The figure above is the third order]

Train of thought

Think of the problem as 0 going in four directions, constantly swapping with neighboring numbers to form a new state diagram, but paying attention to the recurring states, and also paying attention to whether or not you hit the boundary when you move. There’s no unique way to go 0, so there’s BFS, DFS, and ID-dfs.

How do you tell if there is a solution?

  • If the number of columns is odd, the number of inversions must be even
  • If the number of cell columns is even and the number of inversions is even, the difference between the number of lines on which the current space is located and the number of lines on which the original space is located is even
  • If the number of cell columns is even and the number of inversions is odd, the difference between the number of lines on which the current space is located and the number of lines on which the original space is located is odd

How to find the number of inverse numbers?

a = np.array(self.arr).flatten()
b = list(a)
b.remove(0)
ans = 0
for i in range(len(b)):
    for j in range(i + 1.len(b)):
        if b[i] > b[j]:
            ans += 1
return ans 
Copy the code

How do I find zero?

index = np.argwhere(np.array(self.arr) == 0)
return index[0] [0], index[0] [1]
Copy the code

How do I move 0?

def move_0(self, direction) :
    """ Param direction: U D L R
    Copy the current matrix data
    new_arr = deepcopy(self.arr)
    Find the position of 0
    x, y = self.find_0()
    # Determine the direction of movement to move + determine the boundary
    if direction == 'U':
        if x == 0:
            return False.None
        else:
            new_arr[x][y] = new_arr[x - 1][y]
            new_arr[x - 1][y] = 0
            elif direction == 'D':
                if x == len(new_arr) - 1:  # if x is in the last row
                    return False.None
                else:
                    new_arr[x][y] = new_arr[x + 1][y]
                    new_arr[x + 1][y] = 0
                    elif direction == 'L':
                        if y == 0:
                            return False.None
                        else:
                            new_arr[x][y] = new_arr[x][y - 1]
                            new_arr[x][y - 1] = 0
                            elif direction == 'R':
                                if y == len(new_arr) - 1:
                                    return False.None
                                else:
                                    new_arr[x][y] = new_arr[x][y + 1]
                                    new_arr[x][y + 1] = 0
                                    return True, Node(arr=new_arr, parent=self, depth=self.depth + 1)
Copy the code

BFS

Breadth-first search algorithm is implemented by using a queue and a list.

def bfs(node, last_node) :
        Param node: initial node: param last_node: target node: return: """
        operate_queue = []
        finished_queue = []
        operate_queue.append(node)
        while True:
            print('operated number:{}'.format(len(operate_queue)))
            if not operate_queue:
                return False.None
            queue_first_node = operate_queue.pop(0)
            finished_queue.append(queue_first_node)
            for direction in directions:
                has_result, next_node = queue_first_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_queue.append(next_node)
                    if next_node == last_node:
                        return True, next_node
Copy the code

DFS

Depth-first search algorithm is implemented with a stack and a list.

 def dfs(node, last_node) :
        Param node: initial node: param last_node: target node: return: """
        operate_stack = []
        finished_queue = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                return False.None
            stack_top_node = operate_stack.pop()
            finished_queue.append(stack_top_node)
            for direction in directions:
                has_result, next_node = stack_top_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_stack.append(next_node)
                    if next_node == last_node:
                        return True, next_node
Copy the code

ID-DFS

The iteratively deepened depth-first search algorithm is implemented by means of a stack and two lists

def id_dfs(node, last_node, k=10) :
        """ Iterate depth-first algorithm :param node: initial node: param last_node: target node: param K: predefined depth of K layer :return: ""
        The node to be processed is placed on the stack
        operate_stack = []
        The traversed nodes are placed in the completion queue
        finished_queue = []
        # put temporary list for layer larger than k
        tmp = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                if tmp:
                    operate_stack = tmp
                    tmp = []
                    k = k + 1
                else:
                    return False.None
            stack_top_node = operate_stack.pop()
            print("First judge depth :{},k:{}".format(stack_top_node.depth, k))
            if stack_top_node.depth < k:
                finished_queue.append(stack_top_node)
                for direction in directions:
                    has_result, next_node = stack_top_node.move_0(direction)
                    if has_result and next_node not in finished_queue:
                        print("Second judge depth :{},k:{}".format(next_node.depth, k))
                        if next_node.depth <= k:
                            if next_node == last_node:
                                return True, next_node
                            operate_stack.append(next_node)
                        else:
                            tmp.append(next_node)
            else:
                tmp.append(stack_top_node)
Copy the code

The complete code

import numpy as np
from copy import deepcopy
from enum import Enum

# stands for up, down, left, and right
directions = ['U'.'D'.'L'.'R']


# Define enumeration classes, three algorithms
class Algorithm(Enum) :
    BFS = 1
    DFS = 2
    ID_DFS = 3


# define node
class Node:

    def __init__(self, arr, parent, depth=1) :
        """ Initialize :param arr: two-dimensional array :param parent: parent node :param depth: ""
        self.arr = arr
        self.parent = parent
        self.depth = depth

    def find_0(self) :
        "" find the position of 0 :return: coordinate index """
        index = np.argwhere(np.array(self.arr) == 0)
        return index[0] [0], index[0] [1]

    def move_0(self, direction) :
        """ Param direction: U D L R
        Copy the current matrix data
        new_arr = deepcopy(self.arr)
        Find the position of 0
        x, y = self.find_0()
        # Determine the direction of movement to move + determine the boundary
        if direction == 'U':
            if x == 0:
                return False.None
            else:
                new_arr[x][y] = new_arr[x - 1][y]
                new_arr[x - 1][y] = 0
        elif direction == 'D':
            if x == len(new_arr) - 1:  # if x is in the last row
                return False.None
            else:
                new_arr[x][y] = new_arr[x + 1][y]
                new_arr[x + 1][y] = 0
        elif direction == 'L':
            if y == 0:
                return False.None
            else:
                new_arr[x][y] = new_arr[x][y - 1]
                new_arr[x][y - 1] = 0
        elif direction == 'R':
            if y == len(new_arr) - 1:
                return False.None
            else:
                new_arr[x][y] = new_arr[x][y + 1]
                new_arr[x][y + 1] = 0
        return True, Node(arr=new_arr, parent=self, depth=self.depth + 1)

    def get_way(self) :
        """ Traceback to retrieve path :return: node list """
        way = []
        cur = self
        while cur is not None:
            way.insert(0, cur)
            cur = cur.parent
        return way

    def print_array(self) :
        Output matrix :return: """
        print(np.array(self.arr))

    def __eq__(self, other) :
        Param other: :return: """
        return self.arr == other.arr if other else False

    def has_answer(self, last_node) :
        "" count inversions (except 0) to determine if there is a solution :return: True if there is a solution """
        a = np.array(self.arr).flatten()
        b = list(a)
        b.remove(0)
        ans = 0
        for i in range(len(b)):
            for j in range(i + 1.len(b)):
                if b[i] > b[j]:
                    ans += 1

        # If the number of columns is odd, the number of inversions must be even;
        # if the number of columns is even and the number of inversions is even, then the difference between the number of rows on which the current space is located and the number of rows on which the original space is located is even;
        # If the number of columns is even and the number of inversions is odd, then the difference between the number of rows on which the current space is located and the number of rows on which the original space is located is odd.

        if len(a) % 2= =0:
            x0, y0 = self.find_0()
            x1, y1 = last_node.find_0()
            return (ans % 2= =0 and abs(y1 - y0) % 2= =0) or (ans % 2! =0 and abs(y1 - y0) % 2! =0)
        else:
            return ans % 2= =0


# define resolver
class Solver:
    def __init__(self, first_node, last_node) :
        """ First_node: last_node: param last_node: last_node: param last_node: last_node ""
        self.first_node = first_node
        self.last_node = last_node

    def solve(self, alg) :
        """ Solving 15 puzzle problems: Param Alg: Select algorithm :return: """
        if self.first_node.has_answer(self.last_node):
            if alg == Algorithm.BFS:
                result, node = self.bfs(self.first_node, self.last_node)
            elif alg == Algorithm.DFS:
                result, node = self.dfs(self.first_node, self.last_node)
            elif alg == Algorithm.ID_DFS:
                result, node = self.id_dfs(self.first_node, self.last_node, k=10)
            else:
                print("error~wrong algorithm")
                return
            Output path
            if result:
                print("get answer as follow:")
                way = node.get_way()
                for w in way:
                    if w:
                        w.print_array()
                return
        print("no answer~")

    @staticmethod
    def id_dfs(node, last_node, k=10) :
        """ Iterate depth-first algorithm :param node: initial node: param last_node: target node: param K: predefined depth of K layer :return: ""
        The node to be processed is placed on the stack
        operate_stack = []
        The traversed nodes are placed in the completion queue
        finished_queue = []
        # put temporary list for layer larger than k
        tmp = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                if tmp:
                    operate_stack = tmp
                    tmp = []
                    k = k + 1
                else:
                    return False.None
            stack_top_node = operate_stack.pop()
            print("First judge depth :{},k:{}".format(stack_top_node.depth, k))
            if stack_top_node.depth < k:
                finished_queue.append(stack_top_node)
                for direction in directions:
                    has_result, next_node = stack_top_node.move_0(direction)
                    if has_result and next_node not in finished_queue:
                        print("Second judge depth :{},k:{}".format(next_node.depth, k))
                        if next_node.depth <= k:
                            if next_node == last_node:
                                return True, next_node
                            operate_stack.append(next_node)
                        else:
                            tmp.append(next_node)
            else:
                tmp.append(stack_top_node)

    @staticmethod
    def dfs(node, last_node) :
        Param node: initial node: param last_node: target node: return: """
        operate_stack = []
        finished_queue = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                return False.None
            stack_top_node = operate_stack.pop()
            finished_queue.append(stack_top_node)
            for direction in directions:
                has_result, next_node = stack_top_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_stack.append(next_node)
                    if next_node == last_node:
                        return True, next_node

    @staticmethod
    def bfs(node, last_node) :
        Param node: initial node: param last_node: target node: return: """
        operate_queue = []
        finished_queue = []
        operate_queue.append(node)
        while True:
            print('operated number:{}'.format(len(operate_queue)))
            if not operate_queue:
                return False.None
            queue_first_node = operate_queue.pop(0)
            finished_queue.append(queue_first_node)
            for direction in directions:
                has_result, next_node = queue_first_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_queue.append(next_node)
                    if next_node == last_node:
                        return True, next_node


if __name__ == '__main__':
    last_arr = [[1.2.3.4],
                [5.6.7.8],
                [9.10.11.12],
                [13.14.15.0]]

    first_arr = [[3.2.1.4],
                 [7.6.5.8],
                 [11.10.9.12],
                 [13.15.14.0]]
    #
    # last_arr = [[1, 2, 3, 4],
    # [5, 6, 7, 8],
    # [9, 10, 11, 12],
    # [13, 14, 15, 0]
    #
    # first_arr =[[1, 2, 3, 4],
    # [5, 6, 7, 8],
    # [10, 12, 0, 14],
    # [9, 11, 13, 15]
    # last_arr = [[1, 2, 3],
    # [4, 5, 6].
    # [7, 8, 0]]
    #
    # first_arr = [[1, 3, 4],
    # [8, 6, 5),
    # [2, 7, 0]]

    # last_arr = [[1, 2],
    # [3, 0]]
    #
    # first_arr = [[0, 1],
    # (3, 2]]

    solver = Solver(Node(arr=first_arr, parent=None), Node(arr=last_arr, parent=None))
    solver.solve(Algorithm.ID_DFS)
Copy the code