15 головоломок, создающих мою собственную доску и сольвин
Я пытаюсь создать доску. Не слишком уверен, где его добавить. Мне нужно создать конкретную плату, а затем решить с использованием BFS, DFS, BLS и IDS. Я ТАК растерялся даже от того, как создать саму плату. Нам дали исходный код для платы из восьми частей. Как мне заставить это работать на 15?
Это мое главное
public class puzzleSolver {
private static class node{
int level = 0;
int [][] state = new int [4][4];
int blankRow;
int blankCol;
String move = "";
node parent = null;
node up = null;
node down = null;
node left = null;
node right = null;
}
private static class solutionData {
int expandedNodes = 0;
node solutionNode = null;
long memoryUsed;
long totalTime;
String path = "";
String startingBoard = "";
}
public static void main(String [] args){
if(args.length <= 0){
System.out.println("No puzzle was provided");
return;
}
else if(args.length != 16){
System.out.println("Puzzle does not contain correct number of numbers");
return;
}
System.gc();
System.out.println("\nBFS:");
try{
// populate the root node with puzzle
String board = "";
node root = new node();
root.move = "Start";
for (int i =0; i < 4; i++) {
for (int q = 0; q < 4; q++) {
root.state[i][q] = Integer.parseInt(args[4*i + q]);
board = board + root.state[i][q] +" ";
if(root.state[i][q] == 0){
root.blankRow = i;
root.blankCol = q;
}
}
}
solutionData breadthSolution = breadthFind(root, board);
if(breadthSolution != null)
printSolutionData(breadthSolution);
else
System.out.println("Can't find solution- A*h1 ran out of memory :(");
}catch(OutOfMemoryError e){
System.out.println("Can't find solution- BFS ran out of memory :(");
}
System.gc();
System.out.println("\nIDDFS:");
try{
// populate the root node with puzzle
String board = "";
node root = new node();
root.move = "Start";
for (int i =0; i < 4; i++) {
for (int q = 0; q < 4; q++) {
root.state[i][q] = Integer.parseInt(args[4*i + q]);
board = board + root.state[i][q] +" ";
if(root.state[i][q] == 0){
root.blankRow = i;
root.blankCol = q;
}
}
}
solutionData solution = iterDepthFind(root, board);
if(solution != null)
printSolutionData(solution);
else
System.out.println("Can't find solution- A*h1 ran out of memory :(");
}catch(OutOfMemoryError e){
System.out.println("Can't find solution- IDDFS ran out of memory :(");
}
System.gc();
System.out.println("\nA*h1:");
try{
// populate the root node with puzzle
String board = "";
node root = new node();
root.move = "Start";
for (int i =0; i < 4; i++) {
for (int q = 0; q < 4; q++) {
root.state[i][q] = Integer.parseInt(args[4*i + q]);
board = board + root.state[i][q] +" ";
if(root.state[i][q] == 0){
root.blankRow = i;
root.blankCol = q;
}
}
}
solutionData solution = aStarH1(root, board);
if(solution != null)
printSolutionData(solution);
else
System.out.println("Can't find solution- A*h1 ran out of memory :(");
}catch(OutOfMemoryError e){
System.out.println("Can't find solution- A*h1 ran out of memory :(");
}
System.gc();
System.out.println("\nA*h2:");
try{
// populate the root node with puzzle
String board = "";
node root = new node();
root.move = "Start";
for (int i =0; i < 4; i++) {
for (int q = 0; q < 4; q++) {
root.state[i][q] = Integer.parseInt(args[4*i + q]);
board = board + root.state[i][q] +" ";
if(root.state[i][q] == 0){
root.blankRow = i;
root.blankCol = q;
}
}
}
solutionData solution = aStarH2(root, board);
if(solution != null)
printSolutionData(solution);
else
System.out.println("Can't find solution- A*h2 ran out of memory :(");
}catch(OutOfMemoryError e){
System.out.println("Can't find solution- A*h2 ran out of memory :(");
}
}
// solution using the second heuristic. This method calls getDistanceSum()
public static solutionData aStarH2(node root, String board){
ArrayList<node> unexpandedNodes = new ArrayList<node>();
unexpandedNodes.add(root);
solutionData breadthSolution = new solutionData();
int expandedNodes = 0;
long startTime = System.currentTimeMillis();
node cur = null;
while(expandedNodes < Integer.MAX_VALUE){
// get node with lowest f(n) = g(n) + h(n) result
int minVal = Integer.MAX_VALUE;
for (int i = 0; i < unexpandedNodes.size() ; i++) {
node tmp = unexpandedNodes.get(i);
if(getDistanceSum(tmp) + tmp.level < minVal){
minVal = getDistanceSum(tmp) + tmp.level;
cur = tmp;
}
}
unexpandedNodes.remove(cur);
if (getDistanceSum(cur) == 0){
breadthSolution.expandedNodes = expandedNodes;
breadthSolution.solutionNode = cur;
breadthSolution.startingBoard = board;
breadthSolution.path = getPath(cur);
Runtime runtime = Runtime.getRuntime();
breadthSolution.memoryUsed = (runtime.totalMemory() - runtime.freeMemory())/(1024);
breadthSolution.totalTime = System.currentTimeMillis() - startTime;
return breadthSolution;
}
else{
evaluateChildren(cur);
expandedNodes++;
if(cur.left != null)
unexpandedNodes.add(cur.left);
if(cur.right != null)
unexpandedNodes.add(cur.right);
if(cur.up != null)
unexpandedNodes.add(cur.up);
if(cur.down != null)
unexpandedNodes.add(cur.down);
}
}
return null;
}
// method that usis the first heuristic to get the solution. it calls getMissplacedTiles()
public static solutionData aStarH1(node root, String board){
ArrayList<node> unexpandedNodes = new ArrayList<node>();
unexpandedNodes.add(root);
solutionData breadthSolution = new solutionData();
int expandedNodes = 0;
long startTime = System.currentTimeMillis();
node cur = null;
while(expandedNodes < Integer.MAX_VALUE){
// get node with lowest f(n) = g(n) + h(n) result
int minVal = Integer.MAX_VALUE;
for (int i = 0; i < unexpandedNodes.size() ; i++) {
node tmp = unexpandedNodes.get(i);
if(getMissplacedTiles(tmp) + tmp.level < minVal){
minVal = getMissplacedTiles(tmp) + tmp.level;
cur = tmp;
}
}
unexpandedNodes.remove(cur);
if (getMissplacedTiles(cur) == 0){
breadthSolution.expandedNodes = expandedNodes;
breadthSolution.solutionNode = cur;
breadthSolution.startingBoard = board;
breadthSolution.path = getPath(cur);
Runtime runtime = Runtime.getRuntime();
breadthSolution.memoryUsed = (runtime.totalMemory() - runtime.freeMemory())/(1024);
breadthSolution.totalTime = System.currentTimeMillis() - startTime;
return breadthSolution;
}
else{
evaluateChildren(cur);
expandedNodes++;
if(cur.left != null)
unexpandedNodes.add(cur.left);
if(cur.right != null)
unexpandedNodes.add(cur.right);
if(cur.up != null)
unexpandedNodes.add(cur.up);
if(cur.down != null)
unexpandedNodes.add(cur.down);
}
}
return null;
}
// A method that uses breadth first search to find a solution
public static solutionData breadthFind(node root, String board){
LinkedList<node> queue = new LinkedList<node>();
queue.add(root);
solutionData breadthSolution = new solutionData();
int expandedNodes = 0;
long startTime = System.currentTimeMillis();
while(!queue.isEmpty() && expandedNodes <= Integer.MAX_VALUE){
node cur = queue.removeFirst();
String curState = makeStateID(cur);
if(goalTest(cur)){
breadthSolution.expandedNodes = expandedNodes;
breadthSolution.solutionNode = cur;
breadthSolution.startingBoard = board;
breadthSolution.path = getPath(cur);
Runtime runtime = Runtime.getRuntime();
breadthSolution.memoryUsed = (runtime.totalMemory() - runtime.freeMemory())/(1024);
breadthSolution.totalTime = System.currentTimeMillis() - startTime;
return breadthSolution;
}
else {
// expands node
evaluateChildren(cur);
expandedNodes++;
if(cur.left != null)
queue.add(cur.left);
if(cur.right != null)
queue.add(cur.right);
if(cur.up != null)
queue.add(cur.up);
if(cur.down != null)
queue.add(cur.down);
}
}
// should never happen unless puzzle is not valid or ran out of memory
return null;
}
// A method that uses iterative deepening depth first search
public static solutionData iterDepthFind(node root, String board){
int depthLevel = 0;
solutionData breadthSolution = new solutionData();
int expandedNodes = 0;
long startTime = System.currentTimeMillis();
while(depthLevel < Integer.MAX_VALUE){
// ArrayList<String> savedStates = new ArrayList<String>();
LinkedList<node> stack = new LinkedList<node>();
stack.add(root);
while(!stack.isEmpty()){
node cur = stack.removeLast();
String curState = makeStateID(cur);
if(goalTest(cur)){
breadthSolution.expandedNodes = expandedNodes;
breadthSolution.solutionNode = cur;
breadthSolution.startingBoard = board;
breadthSolution.path = getPath(cur);
Runtime runtime = Runtime.getRuntime();
breadthSolution.memoryUsed = (runtime.totalMemory() - runtime.freeMemory())/(1024);
breadthSolution.totalTime = System.currentTimeMillis() - startTime;
return breadthSolution;
}
else if(cur.level < depthLevel){
// savedStates.add(curState);
evaluateChildren(cur);
expandedNodes++;
if(cur.left != null)
stack.add(cur.left);
if(cur.right != null)
stack.add(cur.right);
if(cur.up != null)
stack.add(cur.up);
if(cur.down != null)
stack.add(cur.down);
}
}
depthLevel++;
}
// should never happen unless puzzle is not valid or ran out of memory
return null;
}
// helper function that creates a unique id for each state to be later stored
public static String makeStateID(node curNode){
String id = "";
for(int i = 0; i < 4; i++){
for (int q = 0; q < 4; q++)
id = id + ((char) (65 + curNode.state[i][q]));
}
return id;
}
// check to see if the children are possible legal moves
public static void evaluateChildren(node curNode){
if(curNode.blankCol > 0){
curNode.left = new node();
curNode.left.move = "L";
curNode.left.level = curNode.level + 1;
curNode.left.blankCol = curNode.blankCol - 1;
curNode.left.blankRow = curNode.blankRow;
curNode.left.parent = curNode;
curNode.left.state = makeState(curNode.state, curNode.blankRow, curNode.blankCol, 'L');
}
if(curNode.blankCol < 3){
curNode.right = new node();
curNode.right.move = "R";
curNode.right.level = curNode.level + 1;
curNode.right.blankCol = curNode.blankCol + 1;
curNode.right.blankRow = curNode.blankRow;
curNode.right.parent = curNode;
curNode.right.state = makeState(curNode.state, curNode.blankRow, curNode.blankCol, 'R');
}
if(curNode.blankRow > 0){
curNode.up = new node();
curNode.up.move = "U";
curNode.up.level = curNode.level + 1;
curNode.up.blankCol = curNode.blankCol;
curNode.up.blankRow = curNode.blankRow - 1;
curNode.up.parent = curNode;
curNode.up.state = makeState(curNode.state, curNode.blankRow, curNode.blankCol, 'U');
}
if(curNode.blankRow < 3){
curNode.down = new node();
curNode.down.move = "D";
curNode.down.level = curNode.level + 1;
curNode.down.blankCol = curNode.blankCol;
curNode.down.blankRow = curNode.blankRow + 1;
curNode.down.parent = curNode;
curNode.down.state = makeState(curNode.state, curNode.blankRow, curNode.blankCol, 'D');
}
}
// returns a new state(matrix) from the current state given the location of the blank and given
// the direction up = U, down = D, left = L, right = R
// does not have error checking, must be done BEFORE calling the function
public static int[][] makeState(int[][] curState, int blankY, int blankX, char move){
int [][] newState = new int [4][];
for(int i = 0; i < 4; i++)
newState[i] = curState[i].clone();
if(move == 'U'){
newState[blankY][blankX] = newState[blankY - 1][blankX];
newState[blankY - 1][blankX] = 0;
}
else if(move == 'D'){
newState[blankY][blankX] = newState[blankY + 1][blankX];
newState[blankY + 1][blankX] = 0;
}
else if(move == 'L'){
newState[blankY][blankX] = newState[blankY][blankX - 1];
newState[blankY][blankX - 1] = 0;
}
else{
newState[blankY][blankX] = newState[blankY][blankX + 1];
newState[blankY][blankX + 1] = 0;
}
return newState;
}
// compare the goal state and cur state and return the manhattan sum of a the misplace tiles
public static int getDistanceSum(node curNode){
int manhatSum = 0;
for (int row = 0; row < 4 ; row++) {
for (int col = 0; col < 4 ; col++ ) {
int x;
int y;
int val = curNode.state[row][col];
if(val >= 1 && val <= 4){
y = 0;
x = val - 1;
}
else if(val >= 5 && val <= 8){
y = 1;
x = val - 5;
}
else if(val >= 9 && val <= 12){
y = 2;
x = val - 9;
}
else if(val >= 13 && val <= 15){
y = 3;
x = val - 13;
}
else{
y = 3;
x = 3;
}
manhatSum = manhatSum + Math.abs(row - y) + Math.abs(col - x);
}
}
return manhatSum;
}
// compares the goal state and cur state and returns the number of missplace tiles
public static int getMissplacedTiles(node curNode){
int [][] goalState = {{1,2,3,4},{5,6,7,8},{9, 10,11,12},{13,14,15,0}};
int tileCounter = 0;
for (int row = 0; row<4; row++){
for (int col = 0; col < 4; col++){
if(goalState[row][col] != curNode.state[row][col])
tileCounter++;
}
}
return tileCounter;
}
// checks to see if the node has the correct state(goal)
public static boolean goalTest(node curNode){
int [][] goalState = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
return Arrays.deepEquals(curNode.state, goalState);
}
// returns a string that shows the path that needs to be taken to solve the puzzle
public static String getPath(node solution){
LinkedList<node> solutionPath = new LinkedList<node>();
node cur = solution;
String path = "";
while(cur != null){
solutionPath.addFirst(cur);
cur = cur.parent;
}
while(!solutionPath.isEmpty()){
node tmp = solutionPath.removeFirst();
if(tmp.move != "Start")
path = path + tmp.move;
}
return path;
}
// helper method that simply prints the solution and information regarding the solution
public static void printSolutionData(solutionData solution){
System.out.println(solution.startingBoard + " Moves:" + solution.path.length() + " Steps:" + solution.path);
System.out.println("Memory: " + solution.memoryUsed +"kb Time:
"+ solution.totalTime + "ms Expanded Nodes:" +
solution.expandedNodes);
}
}
И это моя доска:
public class FifteenPuzzleBoard {
public static String LEFT = "Left";
public static String RIGHT = "Right";
public static String UP = "Up";
public static String DOWN = "Down";
public int[] getBoard() {
return board;
}
int[] board;
public FifteenPuzzleBoard() {
board = new int[] { 1, 0, 2, 4, 5, 7, 3, 8, 9, 6, 11, 12, 13, 14, 15 };
}
public FifteenPuzzleBoard(int[] aBoard) {
board = aBoard;
}
private int[] xycoordinatesFromAbsoluteCoordinate(int x) {
int[] retVal = null;
switch (x) {
case 0:
retVal = new int[] { 0, 0 };
break;
case 1:
retVal = new int[] { 0, 1 };
break;
case 2:
retVal = new int[] { 0, 2 };
break;
case 3:
retVal = new int[] { 0, 3 };
break;
case 4:
retVal = new int[] { 1, 0 };
break;
case 5:
retVal = new int[] { 1, 1 };
break;
case 6:
retVal = new int[] { 1, 2 };
break;
case 7:
retVal = new int[] { 1, 3 };
break;
case 8:
retVal = new int[] { 2, 0 };
break;
case 9:
retVal = new int[] { 2, 1 };
break;
case 10:
retVal = new int[] { 2, 2 };
break;
case 11:
retVal = new int[] { 2, 3 };
break;
case 12:
retVal = new int[] { 3, 0 };
break;
case 13:
retVal = new int[] { 3, 1 };
break;
case 14:
retVal = new int[] { 3, 2 };
break;
case 15:
retVal = new int[] { 3, 3 };
break;
}
return retVal;
}
private int absoluteCoordinatesFromXYCoordinates(int x, int y) {
return x * 3 + y;
}
private int getValueAt(int x, int y) {
// refactor this use either case or a div/mod soln
return board[absoluteCoordinatesFromXYCoordinates(x, y)];
}
private int getGapPosition() {
return getPositionOf(0);
}
private int getPositionOf(int val) {
int retVal = -1;
for (int i = 0; i < 16; i++) {
if (board[i] == val) {
retVal = i;
}
}
return retVal;
}
public XYLocation getLocationOf(int val) {
int abspos = getPositionOf(val);
int xpos = xycoordinatesFromAbsoluteCoordinate(abspos)[0];
int ypos = xycoordinatesFromAbsoluteCoordinate(abspos)[1];
return new XYLocation(xpos, ypos);
}
private void setValue(int xPos, int yPos, int val) {
int abscoord = absoluteCoordinatesFromXYCoordinates(xPos, yPos);
board[abscoord] = val;
}
public int getValueAt(XYLocation loc) {
return getValueAt(loc.getXCoOrdinate(), loc.getYCoOrdinate());
}
public void moveGapRight() {
int gapPosition = getGapPosition();
int xpos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[0];
int ypos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[1];
if (!(ypos == 2)) {
int valueOnRight = getValueAt(xpos, ypos + 1);
setValue(xpos, ypos, valueOnRight);
setValue(xpos, ypos + 1, 0);
}
}
public void moveGapLeft() {
int gapPosition = getGapPosition();
int xpos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[0];
int ypos = xycoordinatesFromAbsoluteCoordinate(getGapPosition())[1];
if (!(ypos == 0)) {
int valueOnLeft = getValueAt(xpos, ypos - 1);
setValue(xpos, ypos, valueOnLeft);
setValue(xpos, ypos - 1, 0);
}
}
public void moveGapDown() {
int gapPosition = getGapPosition();
int xpos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[0];
int ypos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[1];
if (!(xpos == 2)) {
int valueOnBottom = getValueAt(xpos + 1, ypos);
setValue(xpos, ypos, valueOnBottom);
setValue(xpos + 1, ypos, 0);
}
}
public void moveGapUp() {
int gapPosition = getGapPosition();
int xpos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[0];
int ypos = xycoordinatesFromAbsoluteCoordinate(gapPosition)[1];
if (!(xpos == 0)) {
int valueOnTop = getValueAt(xpos - 1, ypos);
setValue(xpos, ypos, valueOnTop);
setValue(xpos - 1, ypos, 0);
}
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if ((o == null) || (this.getClass() != o.getClass())) {
return false;
}
FifteenPuzzleBoard aBoard = (FifteenPuzzleBoard) o;
for (int i = 0; i < 15; i++) {
if (this.getPositionOf(i) != aBoard.getPositionOf(i)) {
return false;
}
}
return true;
}
@Override
public int hashCode() {
int result = 17;
for (int i = 0; i < 15; i++) {
int position = this.getPositionOf(i);
result = 37 * result + position;
}
return result;
}
public List<XYLocation> getPositions() {
ArrayList<XYLocation> retVal = new ArrayList<XYLocation>();
for (int i = 0; i < 16; i++) {
int[] res = xycoordinatesFromAbsoluteCoordinate(getPositionOf(i));
XYLocation loc = new XYLocation(res[0], res[1]);
retVal.add(loc);
}
return retVal;
}
public void setBoard(List<XYLocation> locs) {
int count = 0;
for (int i = 0; i < locs.size(); i++) {
XYLocation loc = locs.get(i);
this.setValue(loc.getXCoOrdinate(), loc.getYCoOrdinate(), count);
count = count + 1;
}
}
public boolean canMoveGap(String where) {
boolean retVal = true;
int absPos = getPositionOf(0);
if (where.equals(LEFT)) {
if ((absPos == 0) || (absPos == 3) || (absPos == 6)) {
retVal = false;
}
}
if (where.equals(RIGHT)) {
if ((absPos == 2) || (absPos == 5) || (absPos == 8)) {
retVal = false;
}
}
if (where.equals(UP)) {
if ((absPos == 0) || (absPos == 1) || (absPos == 2)) {
retVal = false;
}
}
if (where.equals(DOWN)) {
if ((absPos == 6) || (absPos == 7) || (absPos == 8)) {
retVal = false;
}
}
return retVal;
}
@Override
public String toString() {
String retVal = board[0] + " " + board[1] + " " + board[2] + " " + board[3] + "\n"
+ board[4] + " " + board[5] + " " + board[6] + " " + board[7] + "\n"
+ board[8] + " " + board[9] + " " + board[10] + " " + board[11] + "\n"
+ board[12] + " " + board[13] + " " + board[14] + " " + board[15] + "\n";
return retVal;
}
}
Как добавить этот код в основную, чтобы я мог тестировать на этой конкретной плате? Я просто получаю вывод без головоломки, когда я запускаю основной.
заранее спасибо