Created
October 24, 2015 21:40
-
-
Save anonymous/290995af38fa23570880 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class EightPuzzle { | |
public static void main(String[] args) { | |
int eCount = 0, tempNum, ans = 0, num = 0; // Reply the user enters and the num is the counter for the frontier | |
int[][] temp = new int[3][3], goal = { {0,1,2}, {3,4,5}, {6,7,8} }; | |
boolean play = true, h_1 = true, finished = false; | |
Scanner kb = new Scanner(System.in); | |
Node[] frontier = new Node[200], path; | |
Node[][] explored = new Node[55][80]; // Holds all previous states that are not in the frontier by their cost | |
Node root = new Node(), copy, min; // Copy save the root for the second heuristic | |
for(int h = 0; h < 55; h++) { | |
for(int g = 0; g < 80; g++) { | |
explored[h][g] = new Node(); | |
} | |
} | |
public static int checkFrontier(Node[] f, Node[][] e, int num) { | |
// The purpose of this method is to see if any of the states that are in the frontier | |
// have already been expanded. This method sifts through the expanded hash table using the | |
// cost of the state as the index. If a state has already been visited it will be deleted | |
// from the frontier and num will be reduced by one. | |
int temp = num; // If num needs to be reduced temp will keep track of it | |
int count = 0; // Indexes through the 2nd dimension of the hash table | |
boolean repeat = true, runWhile = true; | |
//System.out.println("The number of states in the frontier is: " + num); | |
for(int i = 0; i < num; i++) { // Runs through all states in the frontier | |
int pra = f[i].getCost(); | |
Node[] tlo = e[pra]; | |
System.out.println("First index = " + pra); | |
System.out.println("i = " + i); | |
System.out.println("num = " + num); | |
checkIfEmpty(e[f[i].getCost()][count].puzzle); | |
while(!checkIfEmpty(e[f[i].getCost()][count].puzzle) && runWhile) { // While the explored list is not null for the specified index | |
System.out.println("Count = " + count); | |
for(int j = 0; j < 3; j++) { // Runs through the state's puzzle in frontier and explored | |
for(int k = 0; k < 3; k++) { // and compares the two | |
if(f[i].puzzle[j][k] != e[f[i].getCost()][count].puzzle[j][k]) // If one term from the puzzles does not match | |
repeat = false; // the states are not equal to one another | |
} | |
} | |
if(count + 1 < 80) | |
count++; | |
else | |
runWhile = false; | |
if(repeat) { // If the states are equal | |
temp--; | |
f[i] = null; // Remove the state from the frontier | |
runWhile = false; // Stop looking at the explored list with this state | |
} | |
try { | |
checkIfEmpty(e[f[i].getCost()][count].puzzle); | |
} catch(NullPointerException ex) { | |
runWhile = false; | |
} | |
} | |
repeat = true; | |
count = 0; | |
} | |
if(num != temp) { // If a state was deleted then shift over the frontier | |
for(int l = 0; l < num; l++) { | |
if(f[l] == null) { | |
f[l] = f[l + 1]; | |
f[l + 1] = null; | |
} | |
} | |
num = temp; // Adjust num | |
} | |
return num; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment