Problem Statement :
Given on a chessboard a Black Knight position (x, y) and the opponent white King position is at the the coordinate of (m, n), assuming the King is not moving to any place, then find the minimum moves of Black Knight requires to get a checkmate and to win the game. [Coordinates are shown in the above picture]
Solution :
The Knight moves with respect to its current position (x,y) in the 8 possible coordinates :
(x+2 , y+1 ) , (x+2 , y-1 ) , (x-2 , y+1 ) , (x-2 , y-1 ) , (x+1 , y+2 ) , (x-1 , y+2 ) , (x+1 , y-2 ) ,
(x-1 , y-2 )
So it can be noted that position (x,y ) can be treated as the head vertex of the Graph and reaming 8 possible coordinates are adjacent vertex of the graph. So we need to find all the possible paths of reaching to king ( m,n ) and figure out then shortest path among all.
There are 2 ways to solve the problem :
1. Dijkstra's algorithm
2. Breadth First Traversal or BFS
We will follow the 2 option of BFS to solve it and following code snippet written in java to demonstrate the solution of the above problem.
----------------------------------------
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* @author sachin.srivastava
* tek9g.blogspot.coml
* @email tek9gworld@gmail.com
*
*/
public class KnightChess {
public static int traverseCount(Node start , Node end){
if(start ==null || end == null || (start.x == end.x && start.y == end.y) ){
return 0;
}
List<Node> visitedNodes = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
start.visited = true;
queue.add(start);
int minMoves = 0;
while (!queue.isEmpty()) {
Node head = queue.poll();
if(head.x < 1 || head.x > 8 || head.y <1 || head.y > 8 ){
continue;
}
if(head.x == end.x && head.y == end.y){
head.visited = true;
break;
}
List<Node> adjNodes = adjNodes(head, visitedNodes, end);
int count = printVisitedNodes(adjNodes,end,head);
if(count > 0){
if(minMoves <= count -1){
minMoves = count-1;
}
}
for (Node node : adjNodes) {
if(!node.visited){
queue.add(node);
node.visited = true;
}
}
}
return minMoves;
}
public static int printAllNodes(Node node, int count){
if(node == null){
System.out.print("\n");
return count;
}
count++;
System.out.print( "("+ node.x + "," +node.y + ")" + " ");
return printAllNodes(node.parent,count);
}
public static int printVisitedNodes(List<Node> visitedNodes,Node end,Node parent){
if(visitedNodes!=null && !visitedNodes.isEmpty()){
for (Node node : visitedNodes) {
if(matchEndNode(node, end)){
return printAllNodes(node,0);
}
}
}
return 0;
}
public static boolean nodeVisited(Node node,List<Node> visitedNodes,Node end ){
boolean flag = false;
if(node.x <1 || node.x >8 || node.y <1 || node.y >8 || (node.x == 1 && node.y == 1 || node.x==8 && node.y==8)) {
node.visited = true;
return true;
}
if(node!=null && !node.visited && visitedNodes!=null && !visitedNodes.isEmpty()){
for (Node node2 : visitedNodes) {
if(node2.x == node.x && node2.y == node.y ){
node.visited = true;
node2.visited = true;
flag= true;
break;
}
}
}
return flag;
}
public static boolean matchEndNode(Node start, Node end){
if(start.x== end.x && start.y == end.y){
return true;
}
return false;
}
public static List<Node> adjNodes(Node start , List<Node> visitedNodes,Node end){
int x = start.x;
int y = start.y;
Node parent = start;
List<Node> adjNodes = new ArrayList<>();
if(!nodeVisited(new Node(x+2, y+1,parent), visitedNodes,end)){
adjNodes.add(new Node(x+2, y+1,parent));
if(matchEndNode(new Node(x+2, y+1,parent), end)){
return adjNodes;
}
}
if(!nodeVisited(new Node(x+2, y-1,parent), visitedNodes,end)){
adjNodes.add(new Node(x+2, y-1,parent));
if(matchEndNode(new Node(x+2, y-1,parent), end)){
return adjNodes;
}
}
if(!nodeVisited(new Node(x+1, y+2,parent), visitedNodes,end)){
adjNodes.add(new Node(x+1, y+2,parent));
if(matchEndNode(new Node(x+1, y+2,parent), end)){
return adjNodes;
}
}
if(!nodeVisited(new Node(x-1, y+2,parent), visitedNodes,end)){
adjNodes.add(new Node(x-1, y+2,parent));
if(matchEndNode(new Node(x-1, y+2,parent), end)){
return adjNodes;
}
}
if(x > end.x){
if(!nodeVisited(new Node(x-2, y+1,parent), visitedNodes,end)){
adjNodes.add(new Node(x-2, y+1,parent));
if(matchEndNode(new Node(x-2, y+1,parent), end)){
return adjNodes;
}
}
if(!nodeVisited(new Node(x-2, y-1,parent), visitedNodes,end)){
adjNodes.add(new Node(x-2, y-1,parent));
if(matchEndNode(new Node(x-2, y-1,parent), end)){
return adjNodes;
}
}
}
if(y > end.y){
if(!nodeVisited(new Node(x+1, y-2,parent), visitedNodes,end)){
adjNodes.add(new Node(x+1, y-2,parent));
if(matchEndNode(new Node(x+1, y-2,parent), end)){
return adjNodes;
}
}
if(!nodeVisited(new Node(x-1, y-2,parent), visitedNodes,end)){
adjNodes.add(new Node(x-1, y-2,parent));
if(matchEndNode(new Node(x-1, y-2,parent), end)){
return adjNodes;
}
}
}
return adjNodes;
}
static class Node{
int x;
int y;
Node parent;
boolean visited;
public Node(int x , int y, Node parent) {
this.x = x;
this.y = y;
this.parent = parent;
}
}
public static void main(String[] args) {
Node start = new Node(1, 1, null);
Node end = new Node(1,7, null);
System.out.println("Minimum moves for knight="+ traverseCount(start, end));
}
}
Input : 1 , 1 , 1, 7
Output :
(1,7) (3,6) (4,4) (3,2) (1,1)
(1,7) (2,5) (4,4) (3,2) (1,1)
(1,7) (3,6) (2,4) (3,2) (1,1)
(1,7) (2,5) (1,3) (3,2) (1,1)
(1,7) (3,6) (4,4) (2,3) (1,1)
(1,7) (2,5) (4,4) (2,3) (1,1)
(1,7) (3,6) (1,5) (2,3) (1,1)
Minimum moves for knight=4
Input : 2 , 1 , 6, 5
Output :
(6,5) (8,4) (6,3) (4,2) (2,1)
(6,5) (7,3) (6,1) (4,2) (2,1)
(6,5) (5,3) (6,1) (4,2) (2,1)
(6,5) (7,3) (5,4) (4,2) (2,1)
(6,5) (4,6) (5,4) (4,2) (2,1)
(6,5) (5,3) (3,4) (4,2) (2,1)
(6,5) (4,6) (3,4) (4,2) (2,1)
(6,5) (7,3) (5,4) (3,3) (2,1)
(6,5) (4,6) (5,4) (3,3) (2,1)
(6,5) (7,3) (5,2) (3,3) (2,1)
(6,5) (4,4) (5,2) (3,3) (2,1)
(6,5) (5,7) (4,5) (3,3) (2,1)
(6,5) (4,6) (2,5) (3,3) (2,1)
(6,5) (4,4) (2,5) (3,3) (2,1)
(6,5) (5,3) (3,4) (1,3) (2,1)
(6,5) (4,6) (3,4) (1,3) (2,1)
(6,5) (5,3) (3,2) (1,3) (2,1)
(6,5) (4,4) (3,2) (1,3) (2,1)
(6,5) (4,6) (2,5) (1,3) (2,1)
(6,5) (4,4) (2,5) (1,3) (2,1)
Minimum moves for knight=4
Input : 5 , 5 , 6, 6
Output :
(6,6) (7,4) (5,5)
(6,6) (4,7) (5,5)
Minimum moves for knight=2
Enjoy the chess and coding !!!!!
No comments:
Post a Comment