Haiyang Yu's Blog
0%

n数码问题的A*算法(java实现)

发表于 更新于 分类于 Valine：
本文字数： 15k 阅读时长 ≈ 13 分钟

简介

本文用AStar算法实现了关于8数码问题(也可以是n数码问题, n = i^2 - 1, i = 2,3,…). 关于8数码问题和AStar算法的描述参见网络. 这里仅给出java 实现.

h函数的定义

当前 状态的 n*n 矩阵与 目标 状态的 n*n 矩阵中不同数字的个数即为h

1
2
3
4
5
6
7
8
9
10
11
public int distanceTo(Grid to) throws Exception {
        if(to.grid.length != this.grid.length)
            throw new Exception("ArraySize not Match!");
        int dist = 0;
        for(int i = 0; i < this.grid.length; ++i)
        {
            if(this.grid[i] != to.grid[i])
                ++dist;
        }
        return dist;
    }

基本类型Grid的定义

Grid类中储存了矩阵的元素信息, 并且实现了判断两个矩阵的曼哈顿距离的distanceTo()方法和向四周移动元素0的方法expands(), 重写了equals, hashCode, toString方法.

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
package AIHomework;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Description 定义储存二维数组的基本类型Grid
 * @author Haiyang Yu
 */
public class Grid
{
    public int[] grid;
    public int N;
    public Grid(int[][] grid)
    {
        if(grid == null)
        {
            throw new NullPointerException("grid is NULL!");
        }
        for (int[] ints : grid) {
            if (ints.length != grid.length)
                throw new ExceptionInInitializerError("grid must be a square array!");
        }
        N = grid.length;
        int size = grid.length * grid[0].length;
        this.grid = new int[size];
        int k = 0;
        for(int[] i : grid)
        {
            for(int j : i)
                this.grid[k++] = j;
        }
    }
    public Grid(int[] grid)
    {
        int len = grid.length;
        if((int) Math.sqrt(len) * (int) Math.sqrt(len) != len)
            throw new ExceptionInInitializerError("grid must be a square array!");
        N = (int) Math.sqrt(len);
        this.grid = Arrays.copyOf(grid,grid.length);
    }
    public Grid(Grid other)
    {
        this.grid = Arrays.copyOf(other.grid, other.grid.length);
        this.N = other.N;
    }
    public int distanceTo(Grid to) throws Exception {
        if(to.grid.length != this.grid.length)
            throw new Exception("ArraySize not Match!");
        int dist = 0;
        for(int i = 0; i < this.grid.length; ++i)
        {
            if(this.grid[i] != to.grid[i])
                ++dist;
        }
        return dist;
    }
    private int find0() throws Exception {
        for(int i = 0; i <grid.length; ++i)
        {
            if(grid[i] == 0)
                return i;
        }
        throw new Exception("0 not found!");
    }
    public List<Grid> expands() throws Exception {
        int loc0 = find0();
        List<Grid> ans = new ArrayList<>();
        if(loc0 >= N)  //move up
        {
            int[] tmparr = Arrays.copyOf(grid, grid.length);
            int tmp = tmparr[loc0];
            tmparr[loc0] = tmparr[loc0 - N];
            tmparr[loc0 - N] = tmp;
            ans.add(new Grid(tmparr));
        }
        if(loc0 < grid.length - N) // move down
        {
            int[] tmparr = Arrays.copyOf(grid, grid.length);
            int tmp = tmparr[loc0];
            tmparr[loc0] = tmparr[loc0 + N];
            tmparr[loc0 + N] = tmp;
            ans.add(new Grid(tmparr));
        }
        if(loc0 % N != 0) //move left
        {
            int[] tmparr = Arrays.copyOf(grid, grid.length);
            int tmp = tmparr[loc0];
            tmparr[loc0] = tmparr[loc0 - 1];
            tmparr[loc0 - 1] = tmp;
            ans.add(new Grid(tmparr));
        }
        if(loc0 % N != N-1) //move right
        {
            int[] tmparr = Arrays.copyOf(grid, grid.length);
            int tmp = tmparr[loc0];
            tmparr[loc0] = tmparr[loc0 + 1];
            tmparr[loc0 + 1] = tmp;
            ans.add(new Grid(tmparr));
        }
        return ans;
    }
    @Override
    public boolean equals(Object other) {
        if(other instanceof Grid)
        {
            Grid o = (Grid) other;
            if(o.grid.length != this.grid.length)
                return false;
            else {
                for(int i = 0; i < this.grid.length; ++i) {
                    if(o.grid[i] != this.grid[i])
                        return false;
                }
                return true;
            }
        }
        else
            return false;
    }
    @Override
    public int hashCode()
    {
        int a = 0;
        final int base = 31;
        for(int i : grid)
        {
            a += i;
            a *= base;
        }
        return a;
    }
    @Override
    public String toString()
    {
        StringBuilder s = new StringBuilder();
        int max = 0;
        for(int i : this.grid)
            if(i > max)
                max = i;
        int subsize = (int) Math.sqrt(grid.length);
        for(int i = 0; i < grid.length; ++i)
        {
            if(i % subsize == 0 && i != 0)
                s.append("\n");
            if(max > 9 && grid[i] < 10)
                s.append(' ');
            s.append(grid[i]);
            s.append(' ');
        }
        return s.toString();
    }

    public static void main(String[] args) throws Exception
    {
        int[] a = {1,2,0,4,5,6,7,3,8};
        Grid ga = new Grid(a);
        int[][] b = {{2,8,3},
                {1,0,4},
                {7,6,5}};
        Grid gb = new Grid(b);
        for(Grid g : ga.expands())
            System.out.println(g);
    }
}

状态节点类型State的定义

State是节点类, 描述某个节点含有的grid, 最终状态的目标grid, 以及节点是从哪个父节点移动得来的.

同时, 计算了H, G, F的值. 并且可以通过调用aStar方法来执行A*算法

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
package AIHomework;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 节点类, 描述某个节点含有的grid, 最终的目标grid, 以及节点是从哪个父节点移动得来的.
 * 同时, 计算了H, G, F的值. 并且可以通过调用aStar方法来执行A*算法
 * @author Haiyang Yu
 * @see Grid
 */
public class State {
    public Grid curr;
    public Grid finalState;
    public State prev = null;
    public int H;
    public int G;
    public int F;
    private int maxIteration;
    public State(Grid currState, Grid finalState, State prev, int maxIteration) throws Exception {
        this.maxIteration = maxIteration;
        this.curr = currState;
        this.prev = prev;
        this.finalState = finalState;
        H = currState.distanceTo(finalState);
        if(prev == null)
            G = 0;
        else
            G = prev.G + 1;
        F = G + H;
    }
    public State(Grid currState, Grid finalState, State prev) throws Exception {
        this(currState, finalState, prev, 1 << 16);
    }
    public State(Grid currState, Grid finalState) throws Exception {
        this(currState,finalState, null);
    }
    public List<State> expands() throws Exception {
        List<State> states = new ArrayList<>();
        for(Grid grid : curr.expands())
        {
            states.add(new State(grid, finalState, this));
        }
        return states;
    }
    @Override
    public boolean equals(Object other)
    {
        if(other instanceof State)
        {
            State o = (State) other;
            return o.curr.equals(this.curr);
        }
        else
            return false;
    }
    @Override
    public int hashCode()
    {
        return curr.hashCode();
    }
    @Override
    public String toString()
    {
        return curr.toString() + "\n" + "F: " + F + " H: " + H + " G: " + G;
    }

    /**
     * @Description 算法参考于https://www.cnblogs.com/roadwide/p/12890295.html
     */
    public void aStar() throws Exception {
        List<State> open = new LinkedList<>();
        List<State> closed = new LinkedList<>();
        open.add(this);
        int iteration = 0;
        while(!open.isEmpty())
        {
            ++iteration;
            if(iteration == maxIteration)
                throw new Exception("Iteration times reached " + maxIteration + ". This state maybe doesn't have a solution!");
            if(iteration % 1000 == 0)
                System.out.println("Iteration times: " + iteration);
            open.sort((State a, State b) -> {return a.F - b.F;});
            State minFState = open.get(0);
            if(minFState.H == 0)
            {
                minFState.tracePrint();
                System.out.println("Process finished with " + iteration + " times iteration.");
                return;
            }
            open.remove(0);
            closed.add(minFState);

            List<State> expandStates = minFState.expands();
            for(State state : expandStates)
            {
                boolean doesClosedContainState = false;
                for(State closedState : closed)
                {
                    if(closedState.equals(state)) {
                        doesClosedContainState = true;
                        if(state.G < closedState.G) {
                            closedState = state;
                            open.add(state);
                        }
                    }
                }
                boolean doesOpenContainState = false;
                for(State openState : open) {
                    if(openState.equals(state)){
                        doesOpenContainState = true;
                        if(state.G < openState.G)
                        {
                            openState = state;
                        }
                    }
                }
                if(!doesOpenContainState && !doesClosedContainState)
                    open.add(state);
            }
        }
    }
    private void tracePrint()
    {
        List<State> ans = new ArrayList<>();
        State state = this;
        while(state != null)
        {
            ans.add(state);
            state = state.prev;
        }
        Collections.reverse(ans);
        for(State i : ans)
        {
            System.out.println("-------------");
            System.out.println(i);
        }
    }
    public static void main(String[] args) throws Exception
    {
        int[] a = {1,2,3,4,5,6,7,8,0};
        Grid ga = new Grid(a);
        int[][] b = {{1,2,3},
                    {4,0,8},
                    {7,6,5}};
        Grid gb = new Grid(b);
        State state = new State(gb,ga);
        state.aStar();
    }
}

构造测试样例的辅助类

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
package AIHomework;

import java.util.List;
import java.util.Random;

/**
 * @Description 由于n数码问题不是一定有解的. 当二维数组的size升高时, 随机生成一个 0 - 15的矩阵或者随机生成一个 0 - 24的矩阵很可能导致问题无解,
 * 这里的无解定义为A*算法迭代次数多于65536次. 参考State类中的aStar()方法.
 * 所以特意编写此类, 通过最终矩阵随机转移n次元素0, 保证生成的矩阵到最终矩阵是可以通过有限次转移得到, 即n数码问题问题有解
 * @author Haiyang Yu
 */
public class GridGenerationFromFinalGrid {
    public static Grid getNewGrid(Grid finalGrid, int moveTimes, long seed) throws Exception {
        Grid ans = new Grid(finalGrid);
        Random r = new Random(seed);
        while(moveTimes > 0)
        {
            List<Grid> grids = ans.expands();
            int i = r.nextInt(grids.size());
            ans = grids.get(i);
            --moveTimes;
        }
        return ans;
    }
    public static Grid getNewGrid(Grid finalGrid, int moveTimes) throws Exception {
        return getNewGrid(finalGrid, moveTimes, 2020103732L);
    }
    public static Grid getNewGrid(Grid finalGrid) throws Exception {
        return getNewGrid(finalGrid, 47, 2020103732L);
    }

    public static void main(String[] args) throws Exception {
        int[] finalArray3 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0};
        Grid finalGrid = new Grid(finalArray3);
        int[] a = GridGenerationFromFinalGrid.getNewGrid(finalGrid).grid;
        for(int i : a)
            System.out.print(i + ",");
    }


}

调用A*算法的主函数类

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
package AIHomework;

public class AStarMain {
    private static final int[][] array1 =  {{5,3,6},
                                            {1,8,4},
                                            {7,2,0}};
    private static final int[][] array2 =  {{0,6,2,3},
                                            {1,7,12,11},
                                            {5,9,10,4},
                                            {13,14,8,15}};
    private static final int[][] array3 =  {{1,2,3,5,9},
                                            {6,7,8,4,10},
                                            {11,12,13,19,14},
                                            {0,17,21,18,15},
                                            {16,22,23,24,20}};
    private static final int[] finalArray1 = {1,2,3,4,5,6,7,8,0};
    private static final int[] finalArray2 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
    private static final int[] finalArray3 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0};
    public static void main(String[] args) throws Exception {
        State state1 = new State(new Grid(array1), new Grid(finalArray1));
        state1.aStar();
        State state2 = new State(new Grid(array2), new Grid(finalArray2));
        state2.aStar();
        State state3 = new State(new Grid(array3), new Grid(finalArray3));
        state3.aStar();
    }
}

示例1 (3*3)

1
2
3
{{5,3,6},                       1 2 3
{1,8,4},          =>            4 5 6
{7,2,0}};                       7 8 0
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
-------------
5 3 6 
1 8 4 
7 2 0 
F: 7 H: 7 G: 0
-------------
5 3 6 
1 8 4 
7 0 2 
F: 9 H: 8 G: 1
-------------
5 3 6 
1 0 4 
7 8 2 
F: 9 H: 7 G: 2
-------------
5 3 6 
1 4 0 
7 8 2 
F: 10 H: 7 G: 3
-------------
5 3 0 
1 4 6 
7 8 2 
F: 10 H: 6 G: 4
-------------
5 0 3 
1 4 6 
7 8 2 
F: 10 H: 5 G: 5
-------------
0 5 3 
1 4 6 
7 8 2 
F: 11 H: 5 G: 6
-------------
1 5 3 
0 4 6 
7 8 2 
F: 11 H: 4 G: 7
-------------
1 5 3 
4 0 6 
7 8 2 
F: 11 H: 3 G: 8
-------------
1 0 3 
4 5 6 
7 8 2 
F: 11 H: 2 G: 9
-------------
1 3 0 
4 5 6 
7 8 2 
F: 13 H: 3 G: 10
-------------
1 3 6 
4 5 0 
7 8 2 
F: 15 H: 4 G: 11
-------------
1 3 6 
4 5 2 
7 8 0 
F: 15 H: 3 G: 12
-------------
1 3 6 
4 5 2 
7 0 8 
F: 18 H: 5 G: 13
-------------
1 3 6 
4 0 2 
7 5 8 
F: 20 H: 6 G: 14
-------------
1 3 6 
4 2 0 
7 5 8 
F: 21 H: 6 G: 15
-------------
1 3 0 
4 2 6 
7 5 8 
F: 21 H: 5 G: 16
-------------
1 0 3 
4 2 6 
7 5 8 
F: 21 H: 4 G: 17
-------------
1 2 3 
4 0 6 
7 5 8 
F: 21 H: 3 G: 18
-------------
1 2 3 
4 5 6 
7 0 8 
F: 21 H: 2 G: 19
-------------
1 2 3 
4 5 6 
7 8 0 
F: 20 H: 0 G: 20
Process finished with 3721 times iteration.

示例2 (4*4)

1
2
3
4
{{0,6,2,3},                                      1  2  3  4
{1,7,12,11},                          =>         5  6  7  8
{5,9,10,4},                                      9 10 11 12
{13,14,8,15}};                                  13 14 15  0
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
-------------
 0  6  2  3 
 1  7 12 11 
 5  9 10  4 
13 14  8 15 
F: 14 H: 14 G: 0
-------------
 1  6  2  3 
 0  7 12 11 
 5  9 10  4 
13 14  8 15 
F: 14 H: 13 G: 1
-------------
 1  6  2  3 
 5  7 12 11 
 0  9 10  4 
13 14  8 15 
F: 14 H: 12 G: 2
-------------
 1  6  2  3 
 5  7 12 11 
 9  0 10  4 
13 14  8 15 
F: 14 H: 11 G: 3
-------------
 1  6  2  3 
 5  7 12 11 
 9 10  0  4 
13 14  8 15 
F: 14 H: 10 G: 4
-------------
 1  6  2  3 
 5  7  0 11 
 9 10 12  4 
13 14  8 15 
F: 15 H: 10 G: 5
-------------
 1  6  2  3 
 5  7 11  0 
 9 10 12  4 
13 14  8 15 
F: 16 H: 10 G: 6
-------------
 1  6  2  3 
 5  7 11  4 
 9 10 12  0 
13 14  8 15 
F: 17 H: 10 G: 7
-------------
 1  6  2  3 
 5  7 11  4 
 9 10  0 12 
13 14  8 15 
F: 17 H: 9 G: 8
-------------
 1  6  2  3 
 5  7 11  4 
 9 10  8 12 
13 14  0 15 
F: 18 H: 9 G: 9
-------------
 1  6  2  3 
 5  7 11  4 
 9 10  8 12 
13 14 15  0 
F: 17 H: 7 G: 10
-------------
 1  6  2  3 
 5  7 11  4 
 9 10  8  0 
13 14 15 12 
F: 20 H: 9 G: 11
-------------
 1  6  2  3 
 5  7 11  4 
 9 10  0  8 
13 14 15 12 
F: 21 H: 9 G: 12
-------------
 1  6  2  3 
 5  7  0  4 
 9 10 11  8 
13 14 15 12 
F: 21 H: 8 G: 13
-------------
 1  6  2  3 
 5  0  7  4 
 9 10 11  8 
13 14 15 12 
F: 21 H: 7 G: 14
-------------
 1  0  2  3 
 5  6  7  4 
 9 10 11  8 
13 14 15 12 
F: 21 H: 6 G: 15
-------------
 1  2  0  3 
 5  6  7  4 
 9 10 11  8 
13 14 15 12 
F: 21 H: 5 G: 16
-------------
 1  2  3  0 
 5  6  7  4 
 9 10 11  8 
13 14 15 12 
F: 21 H: 4 G: 17
-------------
 1  2  3  4 
 5  6  7  0 
 9 10 11  8 
13 14 15 12 
F: 21 H: 3 G: 18
-------------
 1  2  3  4 
 5  6  7  8 
 9 10 11  0 
13 14 15 12 
F: 21 H: 2 G: 19
-------------
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15  0 
F: 20 H: 0 G: 20
Process finished with 2217 times iteration.

示例3 (5*5)

1
2
3
4
5
{{1,2,3,5,9},                                 1  2  3  4  5
{6,7,8,4,10},                                 6  7  8  9 10
{11,12,13,19,14},                   =>       11 12 13 14 15
{0,17,21,18,15},                             16 17 18 19 20
{16,22,23,24,20}};                           21 22 23 24  0
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
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
 0 17 21 18 15 
16 22 23 24 20 
F: 11 H: 11 G: 0
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
17  0 21 18 15 
16 22 23 24 20 
F: 13 H: 12 G: 1
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
17 21  0 18 15 
16 22 23 24 20 
F: 14 H: 12 G: 2
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
17 21 23 18 15 
16 22  0 24 20 
F: 16 H: 13 G: 3
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
17 21 23 18 15 
16  0 22 24 20 
F: 18 H: 14 G: 4
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
17  0 23 18 15 
16 21 22 24 20 
F: 19 H: 14 G: 5
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
 0 17 23 18 15 
16 21 22 24 20 
F: 19 H: 13 G: 6
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
16 17 23 18 15 
 0 21 22 24 20 
F: 19 H: 12 G: 7
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
16 17 23 18 15 
21  0 22 24 20 
F: 19 H: 11 G: 8
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
16 17 23 18 15 
21 22  0 24 20 
F: 19 H: 10 G: 9
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
16 17  0 18 15 
21 22 23 24 20 
F: 19 H: 9 G: 10
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 19 14 
16 17 18  0 15 
21 22 23 24 20 
F: 19 H: 8 G: 11
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13  0 14 
16 17 18 19 15 
21 22 23 24 20 
F: 19 H: 7 G: 12
-------------
 1  2  3  5  9 
 6  7  8  4 10 
11 12 13 14  0 
16 17 18 19 15 
21 22 23 24 20 
F: 19 H: 6 G: 13
-------------
 1  2  3  5  9 
 6  7  8  4  0 
11 12 13 14 10 
16 17 18 19 15 
21 22 23 24 20 
F: 21 H: 7 G: 14
-------------
 1  2  3  5  0 
 6  7  8  4  9 
11 12 13 14 10 
16 17 18 19 15 
21 22 23 24 20 
F: 22 H: 7 G: 15
-------------
 1  2  3  0  5 
 6  7  8  4  9 
11 12 13 14 10 
16 17 18 19 15 
21 22 23 24 20 
F: 22 H: 6 G: 16
-------------
 1  2  3  4  5 
 6  7  8  0  9 
11 12 13 14 10 
16 17 18 19 15 
21 22 23 24 20 
F: 22 H: 5 G: 17
-------------
 1  2  3  4  5 
 6  7  8  9  0 
11 12 13 14 10 
16 17 18 19 15 
21 22 23 24 20 
F: 22 H: 4 G: 18
-------------
 1  2  3  4  5 
 6  7  8  9 10 
11 12 13 14  0 
16 17 18 19 15 
21 22 23 24 20 
F: 22 H: 3 G: 19
-------------
 1  2  3  4  5 
 6  7  8  9 10 
11 12 13 14 15 
16 17 18 19  0 
21 22 23 24 20 
F: 22 H: 2 G: 20
-------------
 1  2  3  4  5 
 6  7  8  9 10 
11 12 13 14 15 
16 17 18 19 20 
21 22 23 24  0 
F: 21 H: 0 G: 21
Process finished with 2567 times iteration.