ROTH IN
FINAL PROJECT REPORT
Project Description
This project will use Greedy Approach algorithm to find a solution for Eight Puzzle. Greedy Approach is an
algorithm that always choosing the next step that offers the most obvious and immediate benefit. `Carpe Diem` is
the best example to explain Greedy Approach algorithm. The word `Carpe Diem` is Latin for “seize the day!”. The
Oxford Languages defined as “used to urge someone to make the most of the present time and give little thought
to the future.” Just like the definition of `Carpe Diem`, Greedy Approach will find the maximum optimal current
move to solve the puzzle and give little thought to the future.
Eight Puzzle
8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The
object is to move to squares around into different positions and having the numbers displayed in the “goal state”.
The image below show an unsolved initial state and a goal state of the "3 x 3" 8 puzzle.
8-Puzzle
Greedy A. EIght
2 of 5
ROTH IN
Algorithm
1. Hard-coded the goal state
2. Moving the blank square
1. Using calculation to determine where can the square be move to
2. Avoid recurring states
3. Calculate the gain from the move
3. Save the state
The goal state can easily be auto generated, but the goal state for this project was hard-coded since the puzzle is
always 3 by 3. The puzzle is all about moving the blank square. So, most of the algorithm are happening in the
portion of moving the blank square. To move the blank square, some mathematic calculation are needed. Whether
the blank square is located in the far right, far left, top row, or bottom row, these information are crucial for
calculating and choosing the movement of the blank square. After the square is moved, the state of the puzzle is
saved. Each of the states correspond with each step of the puzzle. If a move generated a state that is identical to
one of the previous states, then that move is marked invalid. If a move is invalid, the algorithm will not choose that
move.
After the algorithm found all the valid moves, the gain score calculation will calculate each move. The move with
the highest gain score will be chosen to be the next step of the puzzle.
• Calculating the Gain
• Each matched square will get 1.0 points.
• Each adjacent square will get 0.5 points.
If the square is in the correct spot, that spot will return 1.0 points. The algorithm will chose the next step base on
the move that generated the highest total points. Using this `one point or nothing calculation` will find a solution to
solve the random mixed puzzle at approximately 30% of the time.
This result is not quite pleasing. The calculation need to be improved. The method of adjacent score looking at
each spot and determine if the correct square for that spot is within its surrounding. For example, if the algorithm
looking at the number 1 spot. If 1 is not at that spot then the algorithm will look up, down, left, and right (if
possible) to see if 1 is in one of the those square. If so, this spot will return 0.5 points.
The algorithm will sum up all the points from each of the spots. The total points will be used as the score gain for
making that particular move. Consider all the possible moves, the algorithm will choose the move with the most
gain scores. With this new point system, the algorithm can find a solution at approximately 86% of the time.
Greedy A. EIght
3 of 5
ROTH IN
Code Snippet
There are six files in the directory, but there are only two main programming files. The programming language is
Python 3.7 and up. Each function is documented and codes are self-documented. One main Python script is to
run the algorithm and find solution. The other script is to display the states in graphical interface.
The file names and descriptions are below:
• acmlogo.jpg | square JPEG image file for graphical visualization | used by ran.py
• data.txt | generated by main.py, store states from initial state to final/goal state | used by ran.py
• gen_data.txt | generated by main.py, store states from solved state to mixed state | used by ran.py
• main.py
• contains all the algorithms and calculations for this project.
• can be run with `-h` to display help menu.
• ran.py
• contain pygame code to visually run 1 step by step mixing and solving the puzzle.
• requirements.txt | contain necessary Python packages to run the program successfully
Statistics
Statistics Table - showing mixing moves, average solve %, and average moves.
Greedy A. EIght
4 of 5
ROTH IN
Summary
Greedy A. EIght is using Greedy Approach algorithm to find a solution to an eight puzzle. Greedy Approach is an
algorithm that will find the current state local max and disregard the future states. Eight puzzle is a 3 by 3 squares
with one blank square. The objective of this puzzle is to keep moving the blank square to reach the goal state. This
approach may seem naive. But as the statistics table showed above, the result is tremendously appealing. Based
on the statistic generated from executing the code, as mixing moves increase the average solved percent
approach 84% and the average moves approach 240 moves.
References
Artificial Intelligence, A Modern Approach 3rd Edition - a textbook for this course
Greedy A. EIght
5 of 5
