Capture the Pawns Problem in Java
Apparently, there is an 8x8 chessboard, where each of the two players has one Pawn. Only after this move eliminates the opposing Pawn does a player's Pawn have to move every turn—either a single move forward or one move diagonally. Losing is the player who is unable to move at all. Given the number of rows and columns in which the white and black Pawn are placed. Assuming both players play to their maximum proficiency, the task is to determine who will win the game.
Example 1:
Input:
rWhite = 4, cWhite = 4, rBlack = 1, cBlack = 1
Output:
White Pawn will win the game
Explanation:
Given that the white Pawn is at row 4, column 4, and the black Pawn is at row 1, column 1. The white Pawn moves first from its initial position one square at a time, but on its first move, if it hasn't moved yet, it can move two squares. However, the white Pawn can catch diagonally. If the white Pawn moves to the black side, reaches the eighth rank, and then moves as a stronger piece, it can win in this particular situation. Hence, the White Pawn will win the game.
Approach: Naïve Approach(straightforward)
In the scenario that the white Pawn is in the lead, we must determine if it is on the eighth row. If not, the black wins because the white Pawn is out of action. In the circumstance that the black piece is in the lead, we must determine if it is on the first row, in which case the white wins because the black Pawn is out of options.
In the case that the white Pawn is in the lead and the black Pawn is diagonally adjacent, the white Pawn will eliminate the black piece and win; if not, the white Pawn will advance one step (if the black Pawn has not taken it already) and white will lose.
In the instance that the black Pawn is in turn and the white Pawn is diagonally adjacent, the black Pawn will eliminate the white piece and win; if not, the black Pawn will advance one step (if the white Pawn has not previously taken it) and black will lose.
Implementation:
FileName: CapturePawn.java
import java.io.*;
import java.util.*;
public class CapturePawn
{
static boolean WiningGame(int rWhite, int cWhite, int rBlack, int cBlack)
{
int w = 0, b = 0;
boolean flag=true;
while (flag)
{
// If White is moving
if (rWhite != 8)
{
// If the white piece is able to eliminate the black Pawn, White wins.
if (rBlack == rWhite + 1 && (cBlack == cWhite - 1 || cBlack == cWhite + 1))
return true;
// Take the next step and move forward
else
rWhite++;
}
// white Pawn loses the game if it has no moves
else
return false;
// If the Black can move
if (rBlack != 1)
{
// If the black piece is able to eliminate the white Pawn, White is defeated.
if (rBlack == rWhite + 1 && (cBlack == cWhite - 1 || cBlack == cWhite + 1))
return false;
// Take the next step and move forward
else
rBlack--;
}
// White wins because Black is immovable.
else
return true;
}
// If there are further moves for White
if (w > b)
return true;
return false;
}
public static void main(String args[])
{
int rWhite = 2, cWhite = 2, rBlack = 3, cBlack = 3;
if (WiningGame(rWhite, cWhite, rBlack, cBlack))
System.out.println("White Pawn will win the game");
else
System.out.println("Black Pawn will win the game");
}
}
Output:
White Pawn will win the game
Complexity Analysis:
The time complexity is O(1) and the space complexity is O(1) which remains constant.