Article Top 5 Interview Questions on Chess
The game of Chess emerged in Europe during the second half of the 15th century after evolving from a much older game - Shatranj of Indian origin. It has always been associated with strategical thinking and intelligence so much so that even a few interview questions are based on this game :-). Lets see the top 5 chess interview questions and how to solve them!
1. Consider a pawn positioned at bottom left corner of the NxN chessboard. This pawn can move only in the East or North direction. What is the minimum number of moves needed by this pawn to reach the top right corner of the chessboard? What is the total number of paths this pawn can take during this tour?
The first part of the question is simple. The pawn can move only in the East or North direction. So, it needs (N-1) steps in the East direction and (N-1) steps in the North direction. So, in total, the pawn needs 2 * (N-1) steps to reach from the bottom left corner to the top right corner. For a regular 8x8 chessboard, this result will be 14 moves.
The second part of the question can be solved using permutations and combinations. Every route from bottom left to top right covers 2 * (N-1) blocks of which (N-1) must be East. This is equivalent to the number of ways we can choose (N-1) East blocks from 2 * (N-1), which is 2 * (N-1)C(N-1). For a regular 8x8 chessboard, the result will be 14C2, which is 3432 ways.
The second part can also be solved by another approach. One of the possible route is:
NNNNN...(N-1)times EEEEE..(N-1)times, where N stands for North and E stands for East. We need to figure out the total number of different ways we can arrange these letters. That will be 2 * (N-1)!/(N-1)! * (N-1)!, which is again 2 * (N-1)C(N-1). For a regular 8x8 chessboard, this result is 14!/7! * 7!, which is 3432 again.
Let's see how to code this. To keep things simple, let's assume a value of 15 as the maximum value of N. You can checkout the code here
The first part of the question is simple. The pawn can move only in the East or North direction. So, it needs (N-1) steps in the East direction and (N-1) steps in the North direction. So, in total, the pawn needs 2 * (N-1) steps to reach from the bottom left corner to the top right corner. For a regular 8x8 chessboard, this result will be 14 moves.
The second part of the question can be solved using permutations and combinations. Every route from bottom left to top right covers 2 * (N-1) blocks of which (N-1) must be East. This is equivalent to the number of ways we can choose (N-1) East blocks from 2 * (N-1), which is 2 * (N-1)C(N-1). For a regular 8x8 chessboard, the result will be 14C2, which is 3432 ways.
The second part can also be solved by another approach. One of the possible route is:
NNNNN...(N-1)times EEEEE..(N-1)times, where N stands for North and E stands for East. We need to figure out the total number of different ways we can arrange these letters. That will be 2 * (N-1)!/(N-1)! * (N-1)!, which is again 2 * (N-1)C(N-1). For a regular 8x8 chessboard, this result is 14!/7! * 7!, which is 3432 again.
Let's see how to code this. To keep things simple, let's assume a value of 15 as the maximum value of N. You can checkout the code here
2.The famous N Queens problem. Place N queens (N <= 10) in a NxN chessboard so that no queen attacks none of the other queens.
This is a very simple problem which can be solved using depth-first backtracking algorithm. Backtracking improves upon brute-force search by building solutions step-by-step, and being able to discard a partial solution together with all solutions that would be built from it. This works for the N-queens problem: we start from an empty board and add queens one-by-one; the moment we add a queen that creates a conflict, we know adding more queens will not remove the conflict, so we can avoid all solutions that would be generated from it.
You can view the code snippet here
The code snippet has the main function which initializes the chessboard and calls the recursive function recursivePlaceQueen which places a new queen in the chessboard during each call. The function canKeepNewQueen(x,y) checks if we can place a new queen at position x, y. It returns true if we can place a queen at the position(x,y). The function printChessBoard prints the chessboard, after we've found a solution.
This is a very simple problem which can be solved using depth-first backtracking algorithm. Backtracking improves upon brute-force search by building solutions step-by-step, and being able to discard a partial solution together with all solutions that would be built from it. This works for the N-queens problem: we start from an empty board and add queens one-by-one; the moment we add a queen that creates a conflict, we know adding more queens will not remove the conflict, so we can avoid all solutions that would be generated from it.
You can view the code snippet here
The code snippet has the main function which initializes the chessboard and calls the recursive function recursivePlaceQueen which places a new queen in the chessboard during each call. The function canKeepNewQueen(x,y) checks if we can place a new queen at position x, y. It returns true if we can place a queen at the position(x,y). The function printChessBoard prints the chessboard, after we've found a solution.
3. Knights Distance. Find the shortest number of hops needed by a knight to jump from bottom left corner to the top right corner of a NxN chessboard ( N <= 1000).
This is a classic example of Breadth First Search(BFS). BFS is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal. You can find the code snippet here
This is a classic example of Breadth First Search(BFS). BFS is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal. You can find the code snippet here
4.Given a N*N (N <= 10) chessboard, can one cover the chessboard with the following piece 
When we cover with the above piece, each piece covers 4 squares which can either cover 3 white squares and 1 black square or 3 black squares and 1 white square.
If N is odd, then the total number of squares in the chessboard is odd. So, we can never cover the chessboard using the given piece.
When we cover with the above piece, each piece covers 4 squares which can either cover 3 white squares and 1 black square or 3 black squares and 1 white square.
If N is odd, then the total number of squares in the chessboard is odd. So, we can never cover the chessboard using the given piece.
- If N is 2, obviously, we can't cover the chessboard.
- If N is 4, chessboard has 16 squares. One piece covers 4 squares. That means we need 4 pieces. There is equal number of black and white squares in a chessboard, so we need equal pieces of type 1 and type 2. 4 is divisible by 2 and hence we can cover the chessboard.
- If N is 6, chessboard has 36 squares. We need 9 pieces and also equal number of pieces of type 1 and 2. Hence we can not cover the chessboard.
- If N is 8, we can cover the chessboard. (refer n = 4)
- If N is 10, we can not cover the chessboard. (refer n = 6)
5.Find the total number of squares and rectangles in a NxN chessboard, where N <= 100
First, let's solve the squares problem.
Now to calculate the number of rectangles. A rectangle in a chessboard is formed by picking any 2 lines in the horizontal direction and 2 lines in the vertical direction. So, in a nxn chessboard, there are n+1 horizontal lines and n+1 vertical lines. Therefore, the number of rectangles are (n+1)C2 * (n+1)C2. View the code snippet here
First, let's solve the squares problem.
- If N = 1, then we have 1 square.
- If N = 2, then we have 1 + 4 = 5 squares.
- If N = 3, then we have 1 + 4 + 9 = 14 squares.
- If N = 4, then we have 1 + 4 + 9 + 16 = 30 squares.
- If N = 5, then we have 1 + 4 + 9 + 16 + 25 = 45 squares.
Now to calculate the number of rectangles. A rectangle in a chessboard is formed by picking any 2 lines in the horizontal direction and 2 lines in the vertical direction. So, in a nxn chessboard, there are n+1 horizontal lines and n+1 vertical lines. Therefore, the number of rectangles are (n+1)C2 * (n+1)C2. View the code snippet here
About the Author:
Harishankaran is a graduate from National Institute of Technology, Trichy. You can hardly find him without a computer/laptop next to him. He worked in IBM for a year and is passionate about technology, Computer Science and Algorithms. He blogs at sp2hari.com
Harishankaran is a graduate from National Institute of Technology, Trichy. You can hardly find him without a computer/laptop next to him. He worked in IBM for a year and is passionate about technology, Computer Science and Algorithms. He blogs at sp2hari.com Share this post
