Rank and File
Note: The chess piece images below were created by Colin M.L. Burnett and are used under the auspices of the BSD license, the text of which follows the problem statement.
Programs and algorithms for playing the game of chess have been around as long as computers themselves, with the first chess playing program being developed in the 50's by Alan Turing. Computer chess has come a long way since then, and in 1997 IBM's Deep Blue defeated chess grandmaster Garry Kasparov. One thing all these chess programs have in common though is a need to determine when the winning move, or checkmate, is reached. Your goal for this problem is to implement an algorithm such that, given the current layout of the chessboard, it will detect if a checkmate has occurred during that turn.
Chess is played on a board divided into a 8x8 grid of 64 squares. On a real chessboard, the 64 squares have alternating light and dark colors. For this problem the individual square colors are irrelevant and the entire board is simply treated as a uniform 8x8 grid.
The game is played by two opposing sides, white and black, with each side controlling up to six kinds of pieces: a king, queen, rook, bishop, knight, and one or more pawns. For simplicity's sake, however, this problem will only consider the first five and not make any use of the pawn chess piece. The two players take turns moving one piece at a time on every turn. It is up to each player to decide which piece they wish to move on their turn, but it is not possible for a player to "skip" or "pass"; each player must move one of their pieces in some fashion.
Each kind of chess piece moves in a distinct way as explained in the list below, and Figure 1 gives an example using an X to show each square that a chess piece can move to.
- Rook: The rook moves in a straight line by any number of squares in any of the four cardinal (horizontal and vertical) directions.
- Bishop: The bishop moves in a line by any number of squares in any of the four diagonal directions.
- Queen: The queen can move in a line by any number of squares in any of the eight cardinal and diagonal directions. As such, it is considered to be the most powerful piece in the game.
- Knight: The knight always moves by "jumping" two squares in one cardinal direction and one square in a direction perpendicular to the first. There are 8 possible squares that a knight can move to from a given position, and these are shown in the figure below.
- King: The king can move in any of the eight cardinal and diagonal directions but by one square only. Put another way, the king can only move into the eight immediately adjacent squares. As such, this makes the king one of the weakest pieces on the board.
Input to this problem will begin with a line containing a single integer D (1 ≤ D ≤ 100) indicating the number of data sets. Each data set consists of the following components:
- A line containing a single lower case "w" or upper case "B" indicating which side is to be analyzed for a check or checkmate (and which side is about to move on this turn), with "w" specifying the white side and "B" specifying black.
- A series of eight lines, with each line containing eight characters. These
lines specify the state of the chessboard to be analyzed in this data set.
The characters used on these eight lines are:
- A "." (period) to indicate an empty square
- The lower case letters "r", "b", "q", "n", and "k", to respectively indicate the white side's rook, bishop, queen, knight, and king pieces
- The capital letters "R", "B", "Q", "N", and "K", to indicate the same respective pieces but for the black side
For each data set in the input, print a single line. Begin the line with either "WHITE IS " or "BLACK IS " depending on which side was analyzed in the data set. Finally, complete the line with "CHECKED" or "CHECKMATED" if either is detected, or complete the line with "SAFE" if neither condition holds. If both check and checkmate are detected, print "CHECKMATED".
3 w ........ ........ ........ .Qk.K... ........ ........ ........ ........ B ........ ........ ........ .qK.k... ........ ........ ........ .r...... w ........ ..k..... ........ .Q..K... ........ ........ ........ ........
WHITE IS CHECKED BLACK IS CHECKMATED WHITE IS SAFE
The BSD License for the Chess Piece Images
Copyright © belongs to the uploader, Colin M.L. Burnett, all rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, with the name of the uploader, and this list of conditions;
- Redistributions in binary form must reproduce the above copyright notice, with the name of the uploader, and this list of conditions in the documentation and/or other materials provided with the distribution;
- Neither the name of the uploader nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.