Chessboard Game

Easy
0/40
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
PayPalMorgan StanleyAmdocs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 2
2 2
Sample Output 1
Second
Second
Explanation for Sample Input 1:
For test case 1:


Alice starts at the red square, and moves to either of the blue squares. However, whichever blue square Alice moves to, Bob can move to one of the green squares. It is not possible to make any moves from the green squares, and hence Bob wins. (Only the top 5 x 5 part of the board is shown).

For Test case 2:
   Alice cannot make any move, so Bob wins.
Sample Input 2:
1
2 3
Sample Output 2:
First
Hint

Can we simulate all possible outcomes of the game?

Approaches (2)
Brute Force

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”
Time Complexity

O(4^N), where ‘N’ is the length of the chessboard.

From each state, we can move to at most four different states, so in the worst case, the complexity would be 4^N.

Space Complexity

O(N^2), where ‘N’ is the length of the chessboard.

Because there are N^2 cells, there would be at most N^2 elements in the recursion stack, hence the space complexity is O(N^2).

Code Solution
(100% EXP penalty)
Chessboard Game
Full screen
Console