8-puzzle Programming Project

Today, I am going to start some work on a project for my school. It deals with programming an 8-puzzle. This is a game where there are 8 numbers, and you have to line it up to make the correct order. It's doesn't seem that difficult because I have all the notes I need to help me accomplish this task. I'm going to try to summarize and review my notes for this post. I feel that I can do a lot better, if I can write it out first and in a way, this is my way of communicating to the world in a small way.

It applies to me that the best way to be able to solve any riddle is to be able to look at all the possible solutions. The computer is designed to do this very efficiently, if it's done right. There are two types of searches that the teacher wants us to use. The first is breadth-first search and the other is depth-first search. These types of searches are best explained with an animation, as I have mentioned on my club forum. The forum is on http://www.csupomona.edu/~css. The animations are found by searching with 'DFS' and 'BFS' queries on google. You'll find a school site that outlines these searches very well. The third thing I have had to review is the manhattan distance. The manhattan distance is basically defined with two points (x1,y1) and (x2,y2) as x1-x2+y1-y2. That's pretty much it, and what it does is measure two points in right angles. It can be found in math world, by searching for it on google as well. The manhattan distance and the number of wrong places are going to be used as separate heuristic functions.

Thirdly, the AI class with Dr. P has emphasized graph search algorithm. There are two sets in this algorithm. The first is OPEN and the other is CLOSED. Initally O (open) has a starting node s and CLOSED is empty. The objective of this algorithm is to find the finish node f. For example, think of a graph G as a one-directional tree with the definition G=(V,E). V is its nodes and E is its edges. I'll try to make a stupid diagram of it here:
S--------

a -- b

c d F

For this diagram, S is the starting point. In a BFS algorithm, it travels by going to all the levels of its children, recursively. So the answer is Sabcde. The DFS occurs by reaching the farthest node as possible that's to the left in our assumption. So the answer is Sacdeb.

Now it's back to the GSA (graph search). Let's refresh with remember O for open set and C for closed set. O = {S} and C={} (empty). The steps are defined here:

1. If O is empty return FAIL otherwise choose a node n from O.
2. Remove n from O, create the set S of all its children and add n to closed.
4. For each m is an element of S, if m is not on O or C, then add n to set O.

Okay, this seems a little complicated. I'm going to apply an example of the stupid graph I outlined. S is the starting node on it. Following step 2, we remove S from O and create a set = {a,b} and place S on set C (closed). We know that a,b has still not been searched so we put both on O, according to step 3. O = {a,b}.

We remove a and create the set = {c,d,e} and place a on C. C={a,S}. Following step 3, O={c,d,F,b}. We can't forget about b. Each of these nodes now get examined until we get to finishing node F, which means we're done.

To do a BFS algorithm using graph search, simply make the new nodes from step 2 in back of O (open). So with O={a,b}. We make O={b,c,d,F} and C={a}. This gets us to the children of each node with earlier priority. That's an easy proof to understand. To do a DFS we do just the opposite by making the new nodes in front of O. Using O={a,b} again, O={c,d,F,b}. This gets us to the furthest node starting with the left of each child as early as possible. Again this is easy to see.

--------------------------The meat -----------------------------------
This is a funny section that I decided to create to talk about the project implementation.

An 8-puzzle looks like this, I'll a-i represent any number of the range, 1-8 but each number cannot be used twice. There is also one empty space so the numbers can shift.

a b c
----------
h i d
----------
g f e


As you can see, this reminds you of Tic-Tac-Toe. The exhaustive method is to now write out all the possible combinations, this means 9! = 362,880. I don't know about you but I got a life to take care of and serving the Lord Christ to actually to do this meaningless thing. Fortunately, someone from class has made it possible by proposing that we use the empty space to duke this problem out. This means that we don't get to see the result right away before the answer comes out. This is how a lot of programming problems are like!

The empty space allows to create children for a BFS (breath) or DFS( depth) algorithm by interchanging numbers back and forth. I am going to symbolize the directions with the letters UDLR which represent each of the four directions using the first letter respectively. Using the diagram I have used that represents 8-puzzle, I'm going to define how the numbers should be interchanged for each letter. Let me draw this out again.

a b c
h i d
g f e

a= DR
b= LDR
c= LD
d=ULD
e=LU
f=LUR
g=UR
h=URD
i=LUDR

Fair enough, 8 possible things to keep looking beats 9! ! Digressing player 2 will never win at tic-tac-toe if the first player plays right by placing that X in the center. There are more combinations as i represents. It's one of those games where an extra letter on a limited space can help, giving the aggressor the edge. The chicken that never loses at Tic-Tac-Toe probably always goes first! Don't be a chicken brain and lose to it.

I have laid out the foundation for myself, and good luck to me to get this project finished. The theories seem pretty easy to grasp, and it's now the programming part that kills like 80% of the population.