Number of Cells a Queen can move with Obstacles on the Chessboard
Consider an N X N chessboard with a Queen and K obstacles. The Queen is unable to pass through obstacles. The aim is to determine the number of cells a queen can move given the position (x, y).
Example 1:
Input:
int N = 8 int k = 0 int x = 4 int y= 4
Output:
Therefore, the number of cells that a queen moves with obstacles on the chessboard is 27
Explanation:
Here, the chessboard of size is 8 * 8 with no obstacles, and the position of the Queen is (4,4). Hence, the total number of moves that a queen can move is 27.
Example 2:
Input:
int N = 8 int k = 1 int x = 4 int y= 3 int kx1 = 4 int kx2 = 8
Output:
Therefore, the number of cells that a queen moves with obstacles on the chessboard is 23
Explanation:
Here, the chessboard of size is 8 * 8 with one obstacle, the obstacle position is (4,8), and the position of the Queen is (4,3). Hence, the total number of moves that a queen can move is 23.
Approach: Exploring all the Eight Directions
The goal is to repeat over the cells that the Queen can attack, stopping when an obstacle appears, or the board reaches the end. To accomplish this, we must iterate horizontally, vertically, and diagonally. The following are possible motions from position (x, y):
(x+1, y): Move one step to the right horizontally.
(x-1, y): Move one step to the left horizontally.
(x+1, y+1): diagonal goes one step to up-right.
(x-1, y-1): diagonal goes one step to down-left.
(x-1, y+1): diagonal goes one step to left-up.
(x+1, y-1): diagonal goes one step to right-down.
(x, y+1): one step downward direction.
(x, y-1): one step upward direction.
Implementation:
Filename: Queens1.java
import java.util.*;
import java.io.*;
public class Queens1
{
static class QueenPair
{
int first, second;
public QueenPair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Return true if the position on the chessboard is valid.
static boolean range(int N, int x, int y)
{
return (x <= N && x > 0 && y <= N && y > 0);
}
// Return the overall number of moves in a given direction.
static int check(int N, int x, int y, int xx, int yy,
HashMap pos)
{
int total = 0;
// Validating the Queen's move in a specific direction.
while (range(N, x, y) && ! pos.containsKey(new QueenPair(x, y)))
{
x += xx;
y += yy;
total++;
}
return total;
}
static int Position(int N, int K, int x, int y, int kx1[], int kx2[])
{
int x1, y1, ans = 0;
HashMap pos = new HashMap<>();
// Determining the location of each obstacle
while(K>0)
{
K--;
x1 = kx1[K];
y1 = kx2[K];
pos.put(new QueenPair(x1, y1), 1);
}
// Obtaining the number of positions a queen can advance in each direction.
ans += check(N, x + 1, y, 1, 0, pos);
ans += check(N, x-1, y, -1, 0, pos);
ans += check(N, x, y + 1, 0, 1, pos);
ans += check(N, x, y-1, 0, -1, pos);
ans += check(N, x + 1, y + 1, 1, 1, pos);
ans += check(N, x + 1, y-1, 1, -1, pos);
ans += check(N, x-1, y + 1, -1, 1, pos);
return ans;
}
public static void main(String[] args)
{
int N = 8; // size of chessboard
int K = 1; // obstacles occured
int Queenposx = 4; // Position of queen at x
int Queenposy = 3; // Position of queen at y
int kx1[] = { 4 }; // obstacles at x position
int kx2[] = { 8 }; // obstacles at y position
System.out.println("Therefore, the number of cells that a queen move with obstacles on the chessboard is: ");
System.out.print(Position(N, K, Queenposx, Queenposy, kx1, kx2) +"
");
}
}
Output:
Therefore, the number of cells that a queen moves with obstacles on the chessboard is: 23
Complexity Analysis:
The time complexity for the above approach is O(n2), and the space complexity is O(n), where 'n' is the size of the chess board taken.
Approach: Exploring over the obstacles
The goal is to iterate over the obstacles and compute the number of free cells in the Queen's path up to that obstacle. If there are no obstacles, we must count the number of free cells up to the end of the board in that direction.
For any (x1, y1) and (x2, y2) combination:
• If they are both on the same horizontal level: abs(x1 - x2 - 1)
• The amount of free cells between them if they are vertically at the same level is abs(y1 - y2 - 1).
• The amount of vacant cells between them if there is a diagonal: abs(x1 - x2 - 1) or abs(y1 - y2 - 1).
Implementation:
Filename: Queen2.java
import java.util.*;
import java.io.*;
public class Queen2
{
static int numberofPosition(int N, int K, int x,
int y, int kx1[], int kx2[])
{
// The variables d11, d12, d21, and d22 represent diagonal distances.
// r1 and r2 represent vertical distance.
// c1 and c2 represent horizontal distance.
int d11, d12, d21, d22, r1, r2, c1, c2;
// // Set the distance to the board's end
d11 = Math.min( x-1, y-1 );
d12 = Math.min( N-x, N-y );
d21 = Math.min( N-x, y-1 );
d22 = Math.min( x-1, N-y );
r1 = y-1;
r2 = N-y;
c1 = x-1;
c2 = N-x;
// Calculate the shortest distance between each obstacle.
// If an obstacle appears in any direction,
//The distance will be updated.
for (int i = 0; i < K; i++)
{
if ( x > kx1[i] && y > kx2[i] && x-kx1[i] == y-kx2[i] )
d11 = Math.min(d11, x-kx1[i]-1);
if ( kx1[i] > x && kx2[i] > y && kx1[i]-x == kx2[i]-y )
d12 = Math.min( d12, kx1[i]-x-1);
if ( kx1[i] > x && y > kx2[i] && kx1[i]-x == y-kx2[i] )
d21 = Math.min(d21, kx1[i]-x-1);
if ( x > kx1[i] && kx2[i] > y && x-kx1[i] == kx2[i]-y )
d22 = Math.min(d22, x-kx1[i]-1);
if ( x == kx1[i] && kx2[i] < y )
r1 = Math.min(r1, y-kx2[i]-1);
if ( x == kx1[i] && kx2[i] > y )
r2 = Math.min(r2, kx2[i]-y-1);
if ( y == kx2[i] && kx1[i] < x )
c1 = Math.min(c1, x-kx1[i]-1);
if ( y == kx2[i] && kx1[i] > x )
c2 = Math.min(c2, kx1[i]-x-1);
}
return d11 + d12 + d21 + d22 + r1 + r2 + c1 + c2;
}
public static void main (String[] args)
{
int N = 8; // size of chessboard
int K = 1; // obstacles occured
int Queenposx = 4; // Position of queen at x
int Queenposy = 4; // Position of queen at y
int kx1[] = { 3 }; // obstacles at x position
int kx2[] = { 5 }; // obstacles at y position
System.out.println("Therefore, the number of cells that a queen move with obstacles on the chessboard is: ");
System.out.println(numberofPosition(N, K, Queenposx, Queenposy, kx1, kx2));
}
}
Output:
Therefore, the number of cells that a queen moves with obstacles on the chessboard is: 24
Complexity Analysis:
The time complexity for the above approach is O(n), where 'n' is the size of the chess board taken, and the space complexity is O(1), which is constant.