Last Updated: 13 Dec, 2021
Chessboard Game
Easy
Asked in companies
There is a chessboard of dimensions 15 X 15, and Alice and Bob start playing a game on it. The game is not chess, and involves just one coin.
The coordinates of the top left cell are (1,1) and the bottom right are (15,15). The coin is initially at (x,y). In each turn, the player whose turn it is can move the coin to any of the four cells (provided they are inside the board):
(x-2,y+1)
(x-2,y-1)
(x+1,y-2)
(x-1,y-2)
The figure below shows the possible moves of a coin at (5,4) (An 8 x 8 board is given in the image, but in the problem, it will always be a 15 x 15 board).
Alice makes the first move. Both Alice and Bob take alternate turns and move until it is not possible to move the coin anymore. The player unable to make a move loses.
For example:
If there is a coin at (1,1), Bob wins the game as Alice can make no move to start the game.
Input Format:
The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains three space-separated integers, ’X’ and ‘Y’.
Output Format:
For each query, if Alice wins, print “First” and if Bob wins, print “Second”..
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 5 * 10^3
1 <= 'X',’Y’ <= 15.
Time Limit: 1 sec
Approaches
Approach:
From the starting point, we have at most four possible cells we could move to. For the current cell to be a winning state, at least one of the cells it can move to must be a losing state, as from the current cell, we can move to the losing state, thereby guaranteeing the opponent’s loss. So all we need to do is recursively check all the cells that are reachable from the current cell.
Algorithm:
- Recursively do the following
- Current function call = is_Winning(x,y)
- Call is_Winning(x-2,y+1)
- Call is_Winning(x-2,y-1)
- Call is_Winning(x-2,y-2)
- Call is_Winning(x-2,y-2)
- If atleast one of the four functions called above return False
- Return True
- Else
- Return False
- If is_Winning(x,y) is true
- Return “First”
- Else
- Return “Second”
Approach: From the starting point, we have at most four possible cells we could move to. For the current cell to be a winning state, at least one of the cells it can move to must be a losing state, as from the current cell, we can move to the losing state, thereby guaranteeing the opponent’s loss.
We can recursively compute the value for all cells reachable from the current cell, and speed up this process by storing the value computed at each cell. This guarantees that each value gets computed at most once.
Algorithm:
- Recursively do the following
- Current function call = is_Winning(x,y)
- If dp[x][y] != -1
- Ret
- Call is_Winning(x-2,y+1)
- Call is_Winning(x-2,y-1)
- Call is_Winning(x-2,y-2)
- Call is_Winning(x-2,y-2)
- If atleast one of the four functions called above return False
- dp[x][y] = True
- Else
- dp[x][y] = False
- Return dp[x][y]
- If is_Winning(x,y) is true
- Return “First”
- Else
- Return “Second”