SE250:lab-X:rwan064
Task 1
- The number of different states that exist for the 8 piece puzzle is 9! = 362,880
- This is because there are 9 different things to be put in the puzzle (i.e. numbers 1-8 and a blank space). And the number of ways of arranging 9 different things is 9! because for the first spot we have 9 choices, second spot we have 8 choices, 7 for the third and so on. Which is 9*8*7*6*5*4*3*2*1 = 9!
- The number of edges in the complete state space graph is (9! * 24/9)/2 = 483,840
- The total number of nodes is 9!
- If the blank spot is at the corners, we have 2 legal moves. If the blank spot is in the middle, we have 4 legal moves. And we have 3 legal moves for any other spot.
- So the number of "average" moves from any spot is = (total number of moves)/(number of spots) = ((4*2)+(1*4)+(4*3))/9 = 24/9.
- And therefore for every node in the 9! number of nodes, we can have 24/9 (= 2.66666...) moves. So the total number of moves = 9! * 24/9.
- But the moves also include going from one state to another and back! This means that every edge is repeated once. So we have to divide the number we got before by 2.
- Hence the total number of edges = (9! * 24/9)/2
Task 2
bool search( State* start, State* goal, StateList* solution, int* n_states_visited );
Summary:
- Start from the initial state.
- If the current state is the goal state, STOP.
- Otherwise, get the children of this state.
- Get one of the children and go back to step 2.
Task 3
I changed the main function of graph.c to fit the question on this task as shown:
int main( ) {
State s;
init_State( &s, "123456.78" );
graph_state( &s, 2, "x.png" );
return 0;
}
I ran the program using:
./graph.exe
And got the output shown below:
<html> <img src="http://studwww.cs.auckland.ac.nz/~rwan064/lab10/task3.png" width="371" height="395" alt="Task 3 Graph Image" /> </html>
I edited the graph image using Paint to highlight the initial and goal states. The path from the initial to goal state is also highlighted in blue. The output from graph.exe was the same as what i hand drew myself.
Task 4
Initiate the start and goal states using the code below (in search.c):
init_State( &start, "123456.78" ); init_State( &goal, "12345678." );
Run using:
./search.exe
I got the following output:
123 456 .78 -> 123 456 7.8 -> 123 456 78. -> Visited 5 states
The output says that the program visted 5 states. This means that the search strategy first goes through the height of the three , and then goes to the next child of the initial state and goes down the height of the tree from that node and so on until the goal state is found.
Conclusions
I had to stop at task 4 because I was running out of time. The lab wasn't as hard (or as long) as lab 9. But it was still quite challenging because I had to understand most of the source files to understand how the search function works. Because the search function uses some of the structures and functions declared in these files.
For task 1 I needed help from some class mates to understand how to calculate the number of edges. We discussed our answers and came with the answer shown in the report.
Task 2 took a fair amount of time because I had to read through the source files to find what the structures are and what some of the functions do. But I managed to get a fairly basic idea of how this function works and wrote a simple summary of it.
Task 3 was probably the easiest of the tasks I have got up to. It was fairly straight forward. Same with task 4.