Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
For each white piece check if black king is under attack. If black is under attack, find if it can be moved to a safe place. If it can't be moved then we have a checkmate. Perform similar stuff for white king ( if black is not under attack ).
from state of chess board you can know color of the player who's move it is.
question gets tricky, how you are going to find that your king is under attack.
from state of board you can find out the position of the king, then how you are going to iterate over the board to find whether its check
if yes, then find whether you can kill the opponent piece, how??
if no ,then in optimized way find the blocks where you want to move your king.
then componentization of the chess and moves of each player......
Oh, its more complicated then i thought. So here's improved version:
a) For each white piece check if black king is under attack.
b) If black king is under attack by any white piece x then find
1) if we can kill x using any black piece OR
2) can we block its attacking path( Path blocking will be possible if x is queen, rook or bishop ) OR
3) can we move black king to safe place.
If any of 1,2,3 is possible then there is no checkmate for black.
Perform same steps for white king checkmate.
well we can say that check board object has reference to player who's move it is or you can say that it is provided as separate input parameter.
Really we should think the state of the board has all the information necessary to save and restore the game at a later time. This includes castling status, en passant status, whose turn it is, how much time is left on each player's clock, the position of each piece. There are possibly yet other things.
One simple method would be reuse existing methods which are likely to exist:
1) Determine if King is in check (note, just cheque, not checkmate)
2) Enumerate possible next moves for a player.
3) Check if a move is valid (which entails calling 1).
For the player to play, try all possible next moves by calling 2, then call 3 for each move.
IF we can take a 8X8 array then this problem can be solved easily. Say you are given position of white king(X,Y). Now for each black piece of board check the positions it can travel to and increment all those positions by 1.
Check : If king is in check mode ? if no then return false;
else
{
1. Check if there is a 0 around king. that is a safe place. If yes then return.
2. Check if there is a place where the count is = 1. If yes you can remove that piece by cutting through king and then return false.
3. For each white piece except king check if it can be placed around the white king so that white king is covered by 0 on all sides.
}
We are missing one more possibility:
May be after blocking or cutting the attacking piece, we are opening check from some other path which might lead to check mate.
Initialize another chess board i.e. 8*8 grid. Fill each state with false state. For each component of opposition fill the opponents move with true value. And all the components' cell of the own marked with true.
- Psycho September 19, 2012Now for king's movement if there is any cell with false value - then there is no checkmate. otherwise if all cells which can be reached by king in its next move are true then its checkmate.