1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
15-puzzle path search by bidirectional A* algorithim using open&close list
"""
from heapq import heappush, heappop
from random import shuffle
import time
time.clock = time.time

OPEN = 0
CLOSE = 1
toGOAL = 0
toINIT = 1


class sBoard():

    def __init__(self, board_list, distance, parent, dir, node = OPEN):
        self._array = board_list
        self.distance = distance
        if dir == toGOAL:
            self.heuristic = calc_heuristic(board_list, goal_board)
        else:
            self.heuristic = calc_heuristic(board_list, init_board)
        self.cost = self.distance + self.heuristic
        self.parent = parent
        self.dir = dir
        self.node = node
        self.hashvalue = hash(tuple(self._array))

    def _getsBoard(self):
        return self._array

    def __hash__(self):
        return self.hashvalue

    def __eq__(self,other):
        return self._array == other._array

    def __lt__(self, other):
        return self._array < other._array

def astar():
    queue = []              # 待ち行列
    visited = {}            # 訪問済みnode；過去の盤面
    # インスタンス化
    start = sBoard(init_board, 0, None, toGOAL)
    end = sBoard(goal_board, 0, None, toINIT)
    # 訪問リストに登録
    visited[tuple(init_board)] = start
    visited[tuple(goal_board)] = end
    # 待ち行列にコストとインスタンスを登録
    heappush(queue, (start.cost, start))
    heappush(queue, (end.cost, end))

    No = 0                                              # debug
    # ゴールに到達するまで新しい盤面を探索する
    while len(queue) > 0:
        # 待ち行列からコスト最小の探索済みnode（盤面）を取り出す
        now_tuple = heappop(queue)
        now_board = now_tuple[1]                    # インスタンス
        # close-nodeならばループ先頭へ戻る
        if now_board.node == CLOSE: continue
        No += 1                                     # debug
        # ピースのない位置へ入ることのできる隣接座標
        index = now_board._array.index(0)
        x, y = XY_coord(index)
        coord_next_OK = coord_next(x, y)
        # 次のnode（盤面）を探索；ピースのない位置へスライドを試行
        for coord in coord_next_OK:
            # 次の盤面をつくる
            next_board = now_board._array[:]
            next_index = coord[0] * No_XY + coord[1]
            next_board[index], next_board[next_index] = \
                    next_board[next_index], next_board[index]
            key = tuple(next_board)
            # 同一盤面があるか（訪問済みか）確認する
            if key in visited:
                # 同一盤面がある
                visited_board = visited[key]
                # 両者の探索方向を確認する
                if now_board.dir != visited_board.dir:
                    # ゴールを発見
                    if now_board.dir == toGOAL:
                        # print 'toGOAL'                  # debug
                        sol1 =  get_sol(now_board)
                        sol2 = get_sol(visited_board)
                        sol1.reverse()
                    else:
                        # print 'toINIT'                  # debug
                        sol1 = get_sol(visited_board)
                        sol1.reverse()
                        sol2 = get_sol(now_board)
                    sol = sol1 + sol2
                    return sol, No

                # 同一盤面がある（訪問済み）がゴールではない
                if visited_board.cost > now_board.cost + 1:
                    # 訪問済みで今回のコストのほうが小さいならば更新する
                    # 以前のnodeをcloseにして新しいnodeをつくる
                    visited_board.node = CLOSE
                else:
                    continue
            # 未訪問ならばor訪問済みで今回のコストのほうが小さいならば
            # インスタンス化
            new_board = sBoard(next_board, now_board.distance+1, \
                                    now_board, now_board.dir)
            # 訪問済みリストに登録
            visited[key] = new_board
            # 待ち行列に登録
            heappush(queue, (new_board.cost, new_board))
        # 子ノードは展開済みなので親ノードをcloseする
        now_board.node = CLOSE
        #"""debug
        if No > 1000000:
            end = now_board
            break
        #"""

def get_sol(var):
    sol = []
    while var is not None:
        sol = sol + [var._array]
        var = var.parent
    return sol

def calc_heuristic(list, list2):
    """現局面からゴールまでのコスト予測値
    """
    now_board = list
    std_board = list2
    same = 0
    manhattan = 0
    for var in now_board:
        """ゴール盤面と一致しないピースの数"""
        x, y = XY_coord(var)
        if std_board.index(var) != now_board.index(var):
            same += 1
        """ゴール盤面へ移動するときのマンハッタン距離"""
        pos = std_board.index(var)
        std_board_x, std_board_y = XY_coord(pos)
        x, y = XY_coord(now_board.index(var))
        manhattan += abs(x-std_board_x) + abs(y-std_board_y)
    # print same, manhattan                   # debug
    # heuristic = same + manhattan            # debug
    heuristic = manhattan                   # debug
    # heuristic = same                        # debug
    return 0.79 * heuristic

def coord_next(x, y):
    """ピースのない位置へスライドできる隣接マスのXY座標のリストを返す
    """
    coord_next_OK = [[x, y]]
    # right
    if(x+1 < No_XY):
        coord_next_OK.append([x+1, y])
    # left
    if(x-1 >= 0):
        coord_next_OK.append([x-1, y])
    # down
    if(y-1 >= 0):
        coord_next_OK.append([x, y-1])
    # up
    if(y+1 < No_XY):
        coord_next_OK.append([x, y+1])

    return coord_next_OK

def XY_coord(index):
    """盤面配列のインデックスからXY座標を返す
    """
    x = index // No_XY
    y = index % No_XY
    return x, y

def main():
    global init_board, goal_board, goal_board2, No_XY

    No_XY = 4                                                               # 15
    goal_board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]     # 15
    goal_board2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 0]    # 15
    init_board = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12]     # 15
    # shuffle(init_board)     # init_boardをシャッフルする
    sol, No = astar()
    return sol, No

if __name__ == '__main__':
    s = time.clock()
    sol, No = main()
    e = time.clock()
    print(sol)
    print(len(sol), No, "%.3f" % (e - s))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
8 queens animation
"""
import tkinter as Tk
import fifteen_puzzle as NP

Timer = 500 # ミリ秒；アニメ更新間隔（1以上を設定）

class PuzzleBoard(Tk.Canvas):
    """set initial value"""
    cell_size = 80
    margin = 5
    p_images = []
    p_figure = []

    def __init__(self, master):
        """set initial value"""
        cwidth = 4 * self.cell_size
        Tk.Canvas.__init__(self, master, relief=Tk.RAISED, bd=4, bg='white',
                            width=cwidth, height=cwidth)
        """read solution"""
        p_sol, No_sol = NP.main()
        self.p_sol = p_sol
        self.len_sol = len(p_sol)
        print(self.p_sol)                    # debug
        print(self.len_sol)                  # debug
        # 図を登録
        self.p_images.append(Tk.PhotoImage(file="piece0.gif"))
        self.p_images.append(Tk.PhotoImage(file="piece15.gif"))
        # 初期盤面を描く
        sol = self.p_sol[0]
        self.numbering(sol)

    def numbering(self, sol):
        """ピース番号を付す
        """
        for row in range(4):
            for col in range(4):
                rr = self.cell_size*(row+0.5) + self.margin
                cc = self.cell_size*(col+0.5) + self.margin
                self.p_figure.append(self.create_image
                             (cc, rr, image=self.p_images[1], tags="piece15"))
                nn = row * 4 + col
                chr = str(sol[nn])
                self.create_text(
                        cc, rr, text = chr, justify=Tk.CENTER, fill="#ff00ff",
                        font = ("Times","36","bold"), tag = chr)
        pos0 = sol.index(0)
        row, col = self.XY_coord(pos0)
        rr = self.cell_size*(row+0.5) + self.margin
        cc = self.cell_size*(col+0.5) + self.margin
        self.p_figure.append(self.create_image
                (cc, rr, image=self.p_images[0], tags="piece0"))

    def XY_coord(self, index):
        """盤面配列のインデックスから座標を返す
        """
        r = index // 4
        c = index % 4
        return r, c

    def refresh(self, num_sol):
        """ピース空位置を動かす
        """
        sol = self.p_sol[num_sol]
        self.numbering(sol)
        if num_sol == self.len_sol - 1:
            return True
        else:
            return False

class PuzzleFrame(Tk.Frame):

    def __init__(self, master=None):
        Tk.Frame.__init__(self, master)
        self.master.title("15-Puzzle")
        # title
        l_title = Tk.Label(self, text='15 Puzzle',
                           font=('Times', '24', ('italic', 'bold')),
                           fg='#191970', bg='#E8B77D', width=12)
        l_title.pack(padx=10, pady=10)
        # board
        self.f_board = PuzzleBoard(self)
        self.f_board.pack(padx=10, pady=10)
        # buttons and a counter
        self.f_footer = Tk.Frame(self)
        self.f_footer.pack()
        self.a_button = Tk.Button(self.f_footer, text="start",
                        font=("Times", 14), command = self.show_next)
        self.a_button.pack(side=Tk.LEFT, padx=5,pady=5)
        """set initial value"""
        self.No_step = 0

    def show_next(self):
        """アニメーションのコマ送り
        """
        sol = self.f_board.refresh(self.No_step)
        if sol:
            """解発見"""
            return
        self.No_step += 1
        self.after(Timer, self.show_next)


if __name__ == "__main__":
    app = PuzzleFrame()
    app.pack()
    app.mainloop()