SE250:lab-X:tlou006
Q1
Number of states is 9 factorial
9! = 362880
The edges represent the number of states which branch off a certain state.
If the empty space is at a corner, for each of those 4 states there are 2 possible "next" states.
If the empty space is at one of the sides, for each of those 4 states there are 3 possible "next" states.
If the empty space is in the middle, for that single state there are 4 possible "next" states.
The average number of "next" states for any state is
4/9 * 2 + 4/9 * 3 + 1/9 * 4 = 2.67
Taking 2.67 * 9! and dividing by 2 because each edge is being counted from both sides(states)
number of edges = 483840
Q2
- Start and finish states are initialised
- Initialise a StateList containing the solution??
- Run the search function, if successful then print out the StateList solution, otherwise print out "Cannot solve"
- Print out the number of "moves made"
- Free the memory used by StateList
Q3
Wasn't sure if states could go back to a previous state. ie. have two edges leading to the same state
Asked Mark, he said I was dumb and the edges would override eachother.
The first state will have 2 edges, as the empty space is in the corner.
I tried the graph.c but it gave an error. Then I used rwan064's fix from lab 8
The graph drawn was a huge tree
I changed the code
graph_state( &s, 7, "x.jpg" ); init_State( &s, "12345678." );
to
init_State( &s, "123456.78" ); graph_state( &s, 2, "x.jpg" );
<html> <img src="http://studwww.cs.auckland.ac.nz/~tlou006/x.jpg" width="500" height="500" alt="Tom's Task 3 Image" /> </html>
Q4
Q5
Q6
What i understood from the question, we want to search through the entire length(height) of a branch before starting on the next branch beside it??
in the search function
int i, n_children;
State* cs = get_children( &s, &n_children );
for( i = 0; i < n_children; i++ )
if( add_to_StateSet( &visited, &cs[ i ] ) ) {
/* we have not yet seen this state */
put_StateMap( &path_map, &cs[ i ], &s );
add_to_OrderedStateList( &open, &cs[ i ] );
}
Take the last state off the list and read it.
Set that state as the current state, for each of the current state's children, if we have not visited this children state then add it to the StateList.
For each of the "current state"'s children we want to add each of the children's children to the list BEFORE adding the next children to the list and reading the next "current state"
That made no sense.
int i, n_children;
State* cs = get_children( &s, &n_children );
for( i = 0; i < n_children; i++ )
if( add_to_StateSet( &visited, &cs[ i ] ) ) {
/* we have not yet seen this state */
put_StateMap( &path_map, &cs[ i ], &s );
add_to_OrderedStateList( &open, &cs[ i ] );
}
I think we need to repeat the for loop but setting State* cs = to &cs[ i ]
ie. the ith child of the "current state" we are looking at
We want to do this before i increments??