SE250:lab-X:npit006

Preliminary Code Fixing

I was only able to compile and run search.exe and graph.exe 40 minutes into the lab. These are the changes required.

static char* DOT_CMD = "\"C:/Program Files/ATT/Graphviz/bin/dot.exe\"";

//static char* DOT_CMD = "dot";

// init_State( &start, ".123456789abcdef" );

// init_State( &goal, "123456789abcdef." );

   init_State( &start, ".12345678" );

   init_State( &goal,  "12345678." );

Task 1

In the 8 piece puzzle, there are 9 possible different values for each position. Therefore, the total number of states is 9! = 362880.

Calculating the number of edges in the total state space is a bit more difficult. Each state has a certain number of edges depending on whereabouts the blank space is... there are 9 possible positions for the blank space... summary:

4/9 positions are corners which have 2 edges 4/9 positions are edges which have 3 edges 1 position is a middle one which has 4 edges.

With 362880 possible states categorised by where the blank space is, I think:

• 161280 of these states are corners and yield 322560 edges
• 161280 of these states are edges and yield 483840 edges
• 40320 of these states are middles and yield 161280 edges

Total number of edges = 967680

Have to divide by 2 since an edge is bidirectional... edges = 483840

Task 2

Judging from the sparsely commented wall of code that is search.c, I think I'll skip this task for now. Other tasks are probably more important/useful.

Task 3

I drew the state space enclosed within 2 moves of the initial state and it was correct. There were 7 states included.

Tasks 4 & 5

Task 4 involved inserting a print_state call at some point in the program - I tried including it in various positions in search.c. In order to insert it in a sensible position, I attempted to understand search.c (this is Task 2 all over again!). Shown below is the output from a regular search followed by the output from a search with a print_state call. I've also included the print_state call which I added in after pop command in search.c

E:\lab10>search
123
456
.78
->
123
456
7.8
->
123
456
78.
->
Visited 5 states 
 
 
 
 
***
123
456
.78


***
123
456
7.8


***
123
456
78.

123
456
.78
->
123
456
7.8
->
123
456
78.
->
Visited 5 states

E:\lab10>

CODE:
printf("\n***\n");
print_state( &s); 
printf("\n");

Given the initial state, there were 2 possible routes from there (2 children). Judging from the output (5 nodes visited), the depth-first search chose the correct path for the first movement, but then the wrong one for the second and had to backtrack... this makes sense.

I think my code is in the wrong place though.

Task 6 - Change from Depth First to Breadth First

I have no idea which line to change in order to alter the search strategy - it might help if I had been to lectures recently. From what I understand, using a queue is natural for a breadth-first search and using a stack is natural for a depth-first search. Though I'm pretty sure that has nothing to do with the one line change required here.

Perhaps if in looking for children, we only add one child at a time per search, that might alter how it works. I don't really have any real idea of what to do here.

Conclusion

Again, it is annoying that the prepared code has problems because that only wastes time. The lab itself was fairly difficult mainly because I've missed a critical lecture or two. I could have been better prepared by reading over last year's HTTB section on state-space searching, but this week has been far too busy. Still, all things considered, I think I accomplished a reasonable amount.