Created
July 31, 2017 03:51
-
-
Save unmultimedio/accf12c24c3685759231f759cfd3addd to your computer and use it in GitHub Desktop.
Shortest amount of steps for a knight path in chess board from point A to point B.
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
// This algorithm allows to find the shortest amount of steps | |
// For a knight in a chess board to go from a point A to point B | |
import java.util.*; | |
class Solution { | |
// A Node is any position within the chess board | |
static class Node { | |
public int x; | |
public int y; | |
public int step; | |
public boolean open_options; | |
public Node(int new_x, int new_y, int new_step){ | |
this.x = new_x; | |
this.y = new_y; | |
this.step = new_step; | |
this.open_options = true; | |
} | |
public boolean isEqual(Node a){ | |
return (this.x == a.x && this.y == a.y); | |
} | |
public boolean valid(){ | |
return (this.x >= 0 && this.y >= 0 && this.x < 8 && this.y < 8); | |
} | |
public String toString(){ | |
return "("+this.x+","+this.y+")("+this.step+")"; | |
} | |
} | |
static ArrayList<Node> pastMovements; | |
public static void main(String[] args){ | |
// Checking the algorithm for all positions in the board | |
for(int i=0; i<8; i++) { | |
for(int j=0; j<8; j++) { | |
System.out.println(solution(i,j)); | |
} | |
} | |
} | |
public static int solution(int A, int B) { | |
Node start = new Node(0,0,0); | |
Node end = new Node(A,B,0); | |
prepareList(start); | |
return calculateMoves(getNextNode(), end); | |
} | |
public static void prepareList(Node start){ | |
pastMovements = new ArrayList<>(); | |
pastMovements.add(start); | |
} | |
public static Node getNextNode(){ | |
int min = 999; | |
int index_min = 0; | |
for(int i=0; i<pastMovements.size(); i++) { | |
if(pastMovements.get(i).open_options && pastMovements.get(i).step < min) { | |
min = pastMovements.get(i).step; | |
index_min = i; | |
} | |
} | |
return pastMovements.get(index_min); | |
} | |
public static boolean isInList(Node a){ | |
for(int i=0; i<pastMovements.size(); i++) { | |
if(a.isEqual(pastMovements.get(i))) { | |
return true; | |
} | |
} | |
return false; | |
} | |
public static int calculateMoves(Node now, Node objective){ | |
System.out.println(now.toString()+" - "+objective.toString()); | |
if(now.step > 100000000) { | |
return -1; | |
} | |
if(now.isEqual(objective)) { | |
return now.step; | |
} | |
for(int mov=0; mov<8; mov++) { | |
Node next = new Node(now.x, now.y, now.step+1); | |
switch(mov) { | |
case 0: | |
next.x += 2; | |
next.y += 1; | |
break; | |
case 1: | |
next.x += 2; | |
next.y += -1; | |
break; | |
case 2: | |
next.x += 1; | |
next.y += 2; | |
break; | |
case 3: | |
next.x += -1; | |
next.y += 2; | |
break; | |
case 4: | |
next.x += -2; | |
next.y += 1; | |
break; | |
case 5: | |
next.x += -2; | |
next.y += -1; | |
break; | |
case 6: | |
next.x += -1; | |
next.y += -2; | |
break; | |
case 7: | |
next.x += 1; | |
next.y += -2; | |
now.open_options = false; | |
break; | |
} | |
if(!next.valid()) { | |
continue; | |
} else if(!isInList(next)) { | |
pastMovements.add(next); | |
} | |
} | |
return calculateMoves(getNextNode(), objective); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment