/* * Copyright 2017 Marc Liberatore. * Modified 2018 David Wemhoener */ package
ID: 3714218 • Letter: #
Question
/*
* 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<List<Integer>> {
/**
* 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<Integer> startingValues) {
}
@Override
public List<Integer> getInitialState() {
// TODO
return null;
}
@Override
public List<List<Integer>> getSuccessors(List<Integer> currentState) {
// TODO
return null;
}
@Override
public boolean isGoal(List<Integer> state) {
// TODO
return false;
}
public static void printState(List<Integer> 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<List<Integer>> solution = new Searcher<List<Integer>>(eightPuzzle).findSolution();
for (List<Integer> state : solution) {
//System.out.println(state);
printState(state);
}
System.out.println(solution.size() + " states in solution");
}
}
Explanation / Answer
Hi...
Instead of using above code I have rewritten two class.
1 node class
2 puzzle.class
which I merged in single java class.
package puzzle;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class Puzzle {
public int dimension = 3;
// Bottom, left, top, right
int[] row = { 1, 0, -1, 0 };
int[] col = { 0, -1, 0, 1 };
public int calculateCost(int[][] initial, int[][] goal) {
int count = 0;
int n = initial.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (initial[i][j] != 0 && initial[i][j] != goal[i][j]) {
count++;
}
}
}
return count;
}
public void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public boolean isSafe(int x, int y) {
return (x >= 0 && x < dimension && y >= 0 && y < dimension);
}
public void printPath(Node root) {
if (root == null) {
return;
}
printPath(root.parent);
printMatrix(root.matrix);
System.out.println();
}
public boolean isSolvable(int[][] matrix) {
int count = 0;
List<Integer> array = new ArrayList<Integer>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
array.add(matrix[i][j]);
}
}
Integer[] anotherArray = new Integer[array.size()];
array.toArray(anotherArray);
for (int i = 0; i < anotherArray.length - 1; i++) {
for (int j = i + 1; j < anotherArray.length; j++) {
if (anotherArray[i] != 0 && anotherArray[j] != 0 && anotherArray[i] > anotherArray[j]) {
count++;
}
}
}
return count % 2 == 0;
}
public void solve(int[][] initial, int[][] goal, int x, int y) {
PriorityQueue<Node> pq = new PriorityQueue<Node>(1000, (a, b) -> (a.cost + a.level) - (b.cost + b.level));
Node root = new Node(initial, x, y, x, y, 0, null);
root.cost = calculateCost(initial, goal);
pq.add(root);
while (!pq.isEmpty()) {
Node min = pq.poll();
if (min.cost == 0) {
printPath(min);
return;
}
for (int i = 0; i < 4; i++) {
if (isSafe(min.x + row[i], min.y + col[i])) {
Node child = new Node(min.matrix, min.x, min.y, min.x + row[i], min.y + col[i], min.level + 1, min);
child.cost = calculateCost(child.matrix, goal);
pq.add(child);
}
}
}
}
public static void main(String[] args) {
int[][] initial = { {1, 8, 2}, {0, 4, 3}, {7, 6, 5} };
int[][] goal = { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} };
// White tile coordinate
int x = 1, y = 0;
Puzzle puzzle = new Puzzle();
if (puzzle.isSolvable(initial)) {
puzzle.solve(initial, goal, x, y);
}
else {
System.out.println("The given initial is impossible to solve");
}
}
}
class Node {
public Node parent;
public int[][] matrix;
// Blank tile cordinates
public int x, y;
// Number of misplaced tiles
public int cost;
// The number of moves so far
public int level;
public Node(int[][] matrix, int x, int y, int newX, int newY, int level, Node parent) {
this.parent = parent;
this.matrix = new int[matrix.length][];
for (int i = 0; i < matrix.length; i++) {
this.matrix[i] = matrix[i].clone();
}
// Swap value
this.matrix[x][y] = this.matrix[x][y] + this.matrix[newX][newY];
this.matrix[newX][newY] = this.matrix[x][y] - this.matrix[newX][newY];
this.matrix[x][y] = this.matrix[x][y] - this.matrix[newX][newY];
this.cost = Integer.MAX_VALUE;
this.level = level;
this.x = newX;
this.y = newY;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.