8 Puzzle Solver

You have been given the following code: HW4.java

import java.util.*;

public class HW4 {

// Returns true if it is possible to reach the goal configuration from the initial configuration.
static boolean isSolvable(Configuration initialConfiguration) {
// Fill in.
return false;
}

public static void main(String[] args) {
Configuration puzzle1 = new Configuration(Arrays.asList(null, 1, 3, 4, 2, 5, 7, 8, 6));
System.out.println(isSolvable(puzzle1)); // true

Configuration puzzle2 = new Configuration(Arrays.asList(3, null, 7, 2, 8, 1, 6, 4, 5));
System.out.println(isSolvable(puzzle2)); // true

Configuration puzzle3 = new Configuration(Arrays.asList(2, 1, 3, 4, 5, 6, 7, 8, null));
System.out.println(isSolvable(puzzle3)); // false
}

static class Configuration {

List config;
Configuration(List list) {
config = list;
}

// Returns a List of configurations adjacent to this configuration
List getAdjacentConfigurations() {
List newConfigurations = new ArrayList<>();
for (int i = 0; i < 9; ++i) {
if (config.get(i) == null) {
if (i > 2) { // Swap empty square with square above
List newConfig = new ArrayList<>(config);
Collections.swap(newConfig, i, i-3);
newConfigurations.add(new Configuration(newConfig));
}
if (i < 6) { // Swap empty square with square below
List newConfig = new ArrayList<>(config);
Collections.swap(newConfig, i, i+3);
newConfigurations.add(new Configuration(newConfig));
}
if (i % 3 != 0) { // Swap empty square with square to left
List newConfig = new ArrayList<>(config);
Collections.swap(newConfig, i, i-1);
newConfigurations.add(new Configuration(newConfig));
}
if (i % 3 != 2) { // Swap empty square with square to right
List newConfig = new ArrayList<>(config);
Collections.swap(newConfig, i, i+1);
newConfigurations.add(new Configuration(newConfig));
}
}
}
return newConfigurations;
}

static final List goalConfig = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, null);
// Returns true if this configuration is the goal configuration
boolean isGoalConfiguration() {
return config.equals(goalConfig);
}

// Note: The equals and hashCode methods below make it possible to use Configurations as keys in a hash table.
public boolean equals(Object o) {
return config.equals(((Configuration)o).config);
}
public int hashCode() {
return config.hashCode();
}

// Returns a string representation of this configuration's 3x3 grid.
public String toString() {
String grid = "";
for (int i = 0; i < 9; ++i)
grid += (config.get(i) == null ? "_" : config.get(i)) + (i % 3 == 2 ? "n" : "");
return grid;
}
}
}

8-puzzle rules

The puzzle consists of a 3x3 grid, with 8 tiles, labeled 1 to 8, and one empty slot. You can move a tile horizontally or vertically into the empty slot, to move from one configuration to another. The initial configuration is "solvable" if it is possible to reach the goal configuration.

This initial configuration is solvable because it is possible to reach the goal configuration. Source: cs.princeton.edu: see image.

Graph representation

Each configuration will be represented by a Configuration object (the Configuration class has been given to you).

The Configuration class has the following instance methods:

List< Configuration> getAdjacentConfigurations()

returns a List of all adjacent configurations adjacent to this configuration (the List will always have 2, 3, or 4 elements).

For example, if c is a Configuration object, c.getAdjacentConfigurations() returns a List of Configurations adjacent to c.

boolean isGoalConfiguration()

returns true if if this configuration is the goal configuration.

For example, if c is a Configuration object, c.isGoalConfiguration() returns true if c is the goal configuration.

Solving the puzzle

Write a method

boolean isSolvable(Configuration initialConfiguration)

which takes an initial configuration as a parameter and returns true if it is possible to reach the goal configuration. Otherwise return false.

You must use breadth-first search. If the search takes more than 1 second, there's probably a bug in your code.

Below is pseudocode for breadth-first search. see image.

Notes:

• I suggest using a HashSet to keep track of which configurations have been visited (Configuration objects may be used as hash table keys because the class has both an equals method and a hashCode method).
• You can find a list of Queue methods in the Queue interface.
• The Configuration class has a ToString method, in case you want to print the 3x3 grids, which might be useful for debugging purposes.