Artificial Intelligence

Sliding Brick Puzzle Part II: Searching for Solutions $(12$ points$)$

In the previous part, we implemented key components of a solver for the puzzle game Sliding Brick Puzzle. In this part, we continue with this implementation and significantly extend it to find puzzle solutions using various methods.

Please start with your code from part $1$ and extend it as directed below. As before, the code for this part should be written in Python to run on tux.cs$.$drexel.edu, and we will use the same run.sh shell script for testing. Again, you may only use built$-$in standard libraries $($e$.$g$.,$ math, random, etc.$)$; you may NOT use any external libraries or packages $($if you have any questions at all about what is allowable, please email the instructor$).$

Important notes: Notice that the search space is a graph, so you will have to keep track of all the states visited so far, and make sure your algorithm does not get stuck in loops.

For all the search functions that you will implement in this assignment, the output should print the following:

$$ the list of moves required to solve the state,

$$ the final state of the puzzle,

$$ the number of nodes that were explored,

$$ the time that the function took to find the solution in seconds with two decimal

digits,

$$ and the length of the solution found.

Breadth$-$First Search $($BFS$)(3$pts$)$

Write a method that does a breadth$-$first search from the given state from a file, returning the sequence of moves found that reaches the solution state. Add a $$bfs$$ command$-$line command that allows a user to perform the BFS on a given file representing the state like before.

Here is an example $($pay attention to spaces and newlines$)$: $>$ sh run.sh bfs $"$SBP$-$level$0.$txt$"$

$(2,$left$)$

$(4,$down$)$

$(3,$right$)$

$(2,$up$)$

$(2,$up$)$

$5,4,$

$1,2,2,1,1,$

$1,0,0,3,1,$

$1,0,0,4,1,$

$1,1,1,1,1,$

$160\mathrm{.}005$

Depth$-$Frist Search $($DFS$)(3$pts$)$

Similar to BFS$,$ write a method that does a depth$-$limited search from a given cube, returning the first sequence of moves found that reaches the solution state. Like the previous part, add a $"$dfs$"$ command$-$line command that allows a user to perform the DFS on a given file representing the state:

$>$ sh run.sh dfs $"$SBP$-$level$0.$txt$"$

$(2,$left$)$

$(3,$left$)$

$(2,$right$)$

$(3,$down$)$

$(4,$left$)$

$(4,$left$)$

$(2,$up$)$

$(3,$right$)$

$(3,$right$)$

$(4,$down$)$

$(2,$left$)$

$(2,$up$)$

$5,4,$

$1,2,2,1,1,$

$1,0,0,3,1,$

$1,0,0,4,1,$

$1,1,1,1,1,$

$150\mathrm{.}0012$

Iterative Deepening Search $($IDS$)(3$pts$)$

Write a method that does an iterative deepening search from a given state, returning the first sequence of moves found that reaches the solution state. Add an "ids" command$-$line command that allows a user to perform this search:

$>$ sh run.sh ids $"$SBP$-$level$0.$txt$"$

$(3,$left$)$

$(2,$left$)$

$(4,$down$)$

$(3,$right$)$

$(3,$right$)$

$(2,$up$)$

$(2,$up$)$

$5,4,$

$1,2,2,1,1,$

$1,0,0,3,1,$

$1,0,0,4,1,$

$1,1,1,1,1,$

$190\mathrm{.}027$

A$*$ Search $(3$pts$)$

Lastly, write a method that does an A$*$ search from a given state, returning the first sequence of moves found that reaches the solution state. Add an "astar" command$-$line command that allows a user to perform this task. Note that as part of this process, you will need to choose and implement an admissible heuristic function h$(),$ such that A$*$ can reasonably estimate the minimum cost from a given state to the goal state. As a heuristic, use the Manhattan distance between the master brick and the goal. Also, note that the A$*$ and BFS should have a similar length which is the length of an optimal solution for a state.

Here is an example:

$>$ sh run.sh bfs $"$SBP$-$level$0.$txt$"$

$(2,$left$)$

$(4,$down$)$

$(3,$right$)$

$(2,$up$)$

$(2,$up$)$

$5,4,$

$1,2,2,1,1,$

$1,0,0,3,1,$

$1,0,0,4,1,$

$1,1,1,1,1,$

$120\mathrm{.}005$