/*

* Copyright 2017 Marc Liberatore.

* Modified 2018 David Wemhoener

*/

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

}

}