p313_SlidingGame

p313_SlidingGame.py

class SlidingGame:
    
    def __init__(self, m, n):
        self.board = self.create_board(m, n)
        self.solution = self.find_best_path(self.board, m, n)
    
    def create_board(self, m, n):
        board = []
        for x in range(n):
            board.append([1]*m)
        board[0][0] = 2
        board[-1][-1] = 0
        return board
    
    def move_piece(self, board, x, y, d):
        v = board[x][y]
        if d == "n":
            new_x, new_y = x - 1, y
        if d == "s":
            new_x, new_y = x + 1, y
        if d == "e":
            new_x, new_y = x, y + 1
        if d == "w":
            new_x, new_y = x, y - 1
            
        board[new_x][new_y] = v
        board[x][y] = 0
        return board
    
    def find_movable_pieces(self, board, empty_x, empty_y, m, n):
        pieces = []
        if empty_x + 1 < n:
            pieces.append((empty_x + 1, empty_y, "n"))
        
        if empty_x - 1 >= 0:
            pieces.append((empty_x - 1, empty_y, "s"))
        
        if empty_y + 1 < m:
            pieces.append((empty_x, empty_y + 1, "w"))
        
        if empty_y - 1 >= 0:
            pieces.append((empty_x, empty_y - 1, "e"))
        
        return pieces
    
    def create_board_id(self, board, m, n):
        board_id = ""
        for x in range(n):
            for y in range(m):
                board_id += str(board[x][y])
        return board_id
    
    def print_board(self, board, n):
        for x in range(n):
            print(board[x])
    
    def copy_board(self, board, m, n):
        new_board = []
        for x in range(n):
            t = []
            for y in range(m):
                t.append(board[x][y])
            new_board.append(t)
        return new_board
    
    def print_path(self, path, n):
        for i, x in enumerate(path):
            print(i)
            self.print_board(x, n)
            
    def find_best_path(self, board, m, n):
        
        queue = [(board, n - 1, m - 1, 0, (board,))]
        seen = []
        while queue != []:
            b, empty_x, empty_y, move, path = queue.pop(0)
            board_id = self.create_board_id(b, m, n)
            
            if board_id not in seen:
                seen.append(board_id)
                for xx, yy, d in self.find_movable_pieces(b, empty_x, empty_y, m, n):
                    temp_board = self.copy_board(b, m, n)
                    new_board = self.move_piece(temp_board, xx, yy, d)
                    new_path = path + (new_board, )
                    if new_board[-1][-1] == 2:
                        return move + 1
                    queue.append((new_board, xx, yy, move + 1, new_path))
            
def S_brute_force(m, n):
    s = SlidingGame(m, n)
    return s.solution