package search;

import java.util.Set;

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;

}

/**

* Determines what states are reachable from the start state in a

* certain number of moves

*

* @param m the number of moves from the start state

* @return a set of nodes

*/

public Set findReachableSet(int m) {

// 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 printState(List state) {

String rowOne = state.get(0).toString() + state.get(1).toString() + state.get(2).toString();

String rowTwo = state.get(3).toString() + state.get(4).toString() + state.get(5).toString();

String rowThree = state.get(6).toString() + state.get(7).toString() + state.get(8).toString();

System.out.println(rowOne);

System.out.println(rowTwo);

System.out.println(rowThree);

System.out.println();

}

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);

printState(state);

}

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

}

}