package search;

import java.util.List;

/**

* An implementation of a Searcher that performs an iterative search,

* storing the list of next states in a Queue. This results in a

* breadth-first search.

*

* @author liberato

*

* @param the type for each vertex in the search graph

*/

public class Searcher {

private final SearchProblem searchProblem;

/**

* Instantiates a searcher.

*

* @param searchProblem

* the search problem for which this searcher will find and

* validate solutions

*/

public Searcher(SearchProblem searchProblem) {

this.searchProblem = searchProblem;

}

/**

* Finds and return a solution to the problem, consisting of a list of

* states.

*

* The list should start with the initial state of the underlying problem.

* Then, it should have one or more additional states. Each state should be

* a successor of its predecessor. The last state should be a goal state of

* the underlying problem.

*

* If there is no solution, then this method should return an empty list.

*

* @return a solution to the problem (or an empty list)

*/

public List findSolution() {

// TODO

return null;

}

/**

* Checks that a solution is valid.

*

* A valid solution consists of a list of states. The list should start with

* the initial state of the underlying problem. Then, it should have one or

* more additional states. Each state should be a successor of its

* predecessor. The last state should be a goal state of the underlying

* problem.

*

* @param solution

* @return true iff this solution is a valid solution

* @throws NullPointerException

* if solution is null

*/

public final boolean isValidSolution(List solution) {

// TODO

return false;

}

}

-----------------------------------------------------------------------------------------------

package puzzle;

import java.util.Arrays;

import java.util.List;

import search.SearchProblem;

import search.Searcher;

/**

* A class to represent an instance of the eight-puzzle.

*

* The spaces in an 8-puzzle are indexed as follows:

*

* 0 | 1 | 2

* --+---+---

* 3 | 4 | 5

* --+---+---

* 6 | 7 | 8

*

* The puzzle contains the eight numbers 1-8, and an empty space.

* If we represent the empty space as 0, then the puzzle is solved

* when the values in the puzzle are as follows:

*

* 1 | 2 | 3

* --+---+---

* 4 | 5 | 6

* --+---+---

* 7 | 8 | 0

*

* That is, when the space at index 0 contains value 1, the space

* at index 1 contains value 2, and so on.

*

* From any given state, you can swap the empty space with a space

* adjacent to it (that is, above, below, left, or right of it,

* without wrapping around).

*

* For example, if the empty space is at index 2, you may swap

* it with the value at index 1 or 5, but not any other index.

*

* Only half of all possible puzzle states are solvable! See:

* https://en.wikipedia.org/wiki/15_puzzle

* for details.

*

* @author liberato

*

*/

public class EightPuzzle implements SearchProblem> {

/**

* Creates a new instance of the 8 puzzle with the given starting values.

*

* The values are indexed as described above, and should contain exactly the

* nine integers from 0 to 8.

*

* @param startingValues

* the starting values, 0 -- 8

* @throws IllegalArgumentException

* if startingValues is invalid

*/

public EightPuzzle(List startingValues) {

}

@Override

public List getInitialState() {

// TODO

return null;

}

@Override

public List> getSuccessors(List currentState) {

// TODO

return null;

}

@Override

public boolean isGoal(List state) {

// TODO

return false;

}

public static void main(String[] args) {

EightPuzzle eightPuzzle = new EightPuzzle(Arrays.asList(new Integer[] {1, 2, 3, 4, 0, 6, 7, 5, 8 }));

List> solution = new Searcher>(eightPuzzle).findSolution();

for (List state : solution) {

System.out.println(state);

}

System.out.println(solution.size() + " states in solution");

}

}

What to do There are a few small tests already, which you will likely want to add to. You may also want to write an interactive driver the main methods in MazeDriver, FindIntegersDriver, and EightPuzzle should give you an idea of how to use the various classes together. There are two tasks to accomplish; they are mostly independent of one another. You must implement the missing methods in searcher, and you must implement the EightPuzzle search problem. Implementing Searcher A Searcher should be able to validate that the solution it found was valid. Start by implementing the isValidsolution method. Then move on to the findsolution method, which will strongly resemble the code we wrote in class (no need to reinvent the wheel here!) Once you have that working, the main method of the MazeDriver will run to completion, and show you the results of a search on a random maze. You can vary the maze by changing the width, height, or seed. You can also test against the other drivers, as noted above, but again: I strongly recommend you write some tests rather than caveman debugging your way to victory here. Implementing EightPuzzle Once you have your searcher working, it's time to implement a new search problem. Turn your attention to EightPuzzle. You should fill out each of the stub methods here. getInitialstate and isGoal should be trivial, depending upon how you choose to represent a game state within EightPuzzle. getSuccessors will require that you understand the rules of the game, and return the complete set of successors of a given state, as a List What to do There are a few small tests already, which you will likely want to add to. You may also want to write an interactive driver the main methods in MazeDriver, FindIntegersDriver, and EightPuzzle should give you an idea of how to use the various classes together. There are two tasks to accomplish; they are mostly independent of one another. You must implement the missing methods in searcher, and you must implement the EightPuzzle search problem. Implementing Searcher A Searcher should be able to validate that the solution it found was valid. Start by implementing the isValidsolution method. Then move on to the findsolution method, which will strongly resemble the code we wrote in class (no need to reinvent the wheel here!) Once you have that working, the main method of the MazeDriver will run to completion, and show you the results of a search on a random maze. You can vary the maze by changing the width, height, or seed. You can also test against the other drivers, as noted above, but again: I strongly recommend you write some tests rather than caveman debugging your way to victory here. Implementing EightPuzzle Once you have your searcher working, it's time to implement a new search problem. Turn your attention to EightPuzzle. You should fill out each of the stub methods here. getInitialstate and isGoal should be trivial, depending upon how you choose to represent a game state within EightPuzzle. getSuccessors will require that you understand the rules of the game, and return the complete set of successors of a given state, as a List