Mark: 14 revision(s)

2008-11-03T05:20:49Z

14 revision(s)

New page

== LAB X ==

=== Task 1 ===

Different states: 9! = 362880, because there is 9 blocks, e.g. the space can be at 9 different positions, then "1" can be at 8 different positions and so forth<br />
Estimated Edges: Um.. this one is pretty hard, I think:<br />
*4 different ways when space is in middle
*3 different ways when space is on the side
*2 different ways when space is in a corner

Space in the middle, numbers can be different in 8! times, same with others.
8! * 4 + 8! * 3 + *1 * 2?

There are some overlapping here obviously...
cbf thinking about it right now :D

=== Task 2 ===
Some comments would have helped greatly, but I guess that is the point of this task :(
This is what I think the algorithm is:

<pre>

Initialise a start state and a goal state, a list of possible states and the number of states already visited.
Call the search function and pass in the start state, goal state, the list of states possible and the number of states already visited.

While the ordered state list is not empty:

-Pop off the current state from the ordered list of states.
-If the current state is the goal state, break loop and record "success"
-Otherwise, get the children of the current state.

For each children retrieved:
-Add to stateset if the child state is not present in the visitedmap
-Add to ordered state list

Clear the children
</pre>

=== Task 3 ===

<pre>
0 Start: 1 3 Goal:
123456.78 - > 1234567.8 -> 12345678.

1 2 3 1 2 3 1 2 3
4 5 6 - > 4 5 6 -> 4 5 6
. 7 8 7 . 8 7 8 .

|

2
123.56478

1 2 3
. 5 6 -> ...
4 7 8

</pre>

Graph from graph.exe
<html>
<img src="http://img209.imageshack.us/img209/9073/68740268th0.png"></img>
</html>

== Task 4 ==

Now I don't know why malloc.h was there and was an Apple implementation, removing that allowed compilation using the unix command make.

The output was:

<pre>
123
456
.78
->
123
456
7.8
->
123
456
78.
->
Visited 5 states
</pre>

The 3 states are shown here (shortest route), the other 2 states would be swapping the 4 and . and then possibly 1 and . or 5 and .

SE250:lab-X:sshi080 - Revision history

Mark: 14 revision(s)