Greedy A. EIght
Roth In
CS5433
Dr. Qualls
Fall 2020
1
2
Initial State
4
5
3
Solving 8-Puzzle
7
8
6
Using Greedy Approach to find
a solution for 8 Puzzle
1
2
3
Goal State
4
5
6
7
8
Algorithm
• Hard-coded the goal state
• Moving the blank square
• Using calculation to determine if it is movable
• Avoiding recurring states
• Calculating the max gain
• Save the states
Calculating the Gain
• Goal State: [1,2,3,4,5,6,7,8,0]
• Each move has its own gain(score). Each
1
3
6
matched square will get 1 point.
• Movable: 2, 5, & 8
• Calculation:
7
4
5
• moving(2) = 3 points
• moving(5) = 2 points
• moving(8) = 5 points
• Greedy approach will move 8
2
8
• Using this `1 point or nothing` method will
solved approximately 30%
Improved Calculation
• Goal State: [1,2,3,4,5,6,7,8,0]
• New point system:
7
8
• matched = 1 point
• adjacent = 0.5 point
• Movable: 3, 7, & 8
• Calculation:
4
3
5
• moving(3) = 2.5 points
• moving(7) = 2.0 points
• moving(8) = 2.0 points
• Greedy approach will move 3
1
2
6
• By adding this 1/2 points adjacent, the
agent can now solved approximately 87%
Statistics
Mixing
moves
4
10
20
30
40
75
100
200
Avg.
Solved
100
92.2
86.5
85.4
84.9
84.7
84.6
84.5
%
Avg.
5.3
112.7
188.8
212.5
231.3
239.3
239.5
239.8
Moves
