TopCoder problem "KnightsTour" used in SRM 447 (Division I Level One , Division II Level Two)

Problem Statement


Facebook engineers love playing chess. They also like to play other games on the chessboard. Today, they were wondering how many cells a knight would visit on the chessboard if it followed some predefined algorithm.

You are given a String[] board describing a standard 8x8 chessboard, where the c-th character of the r-th element corresponds to the cell in row r, column c. Some cells are blocked and cannot be jumped into. These will be represented with a '*'. All other cells are marked with a '.', except for the starting position of the knight, which is marked with a 'K'.

A valid jump for a knight consists of shifting one square along one axis and two squares along the other axis. A cell is "accessible" if it is not blocked and it has not been visited by the knight before. The starting position of the knight is considered to be visited, and each time the knight jumps into a new cell, that cell becomes visited. The accessibility number of a cell is the number of accessible cells that the knight can make a valid jump to from that cell. Note that accessibility numbers of cells may change as the knight moves through the board and visits more cells.

The knight will use the following simple algorithm to traverse the board. On each move, it will make a valid jump into the accessible cell with the lowest accessibility number. In case of a tie, it will choose the one with the lowest row number, and if there is still a tie, it will choose the one among them with the lowest column number. The knight will stop moving when it can no longer make a valid jump into an accessible cell.

Return the number of cells that the knight will visit (including the starting cell).



Method signature:int visitedPositions(String[] board)
(be sure your method is public)


-board will contain exactly 8 elements.
-Each element of board will contain exactly 8 characters '.', 'K' or '*'.
-Character 'K' will appear exactly once in board.


Returns: 39

From its starting cell K, the knight can jump to cells A, B and C, which have accessibility numbers of 3, 6 and 4, respectively (see first image below). It will jump to cell A because it has the lowest accessibility number.

From cell A, it can then jump to cells D, E and F, which have accessibility numbers of 1, 5 and 4, respectively (see second image). It will choose cell D. It will continue in this fashion and visit a total of 39 cells.

Returns: 64
If no cells are blocked, then the knight will end up visiting every cell by following the given algorithm.
Returns: 3

From its starting cell K, the knight can jump to cells A and B, which have accessibility numbers of 1 (see the image). Both A and B have the same accessibility number and the same row number, so it will jump to A because it has the lowest column number. It will then jump to C and stop, visiting a total of 3 cells.

Returns: 17
Returns: 27

Problem url:

Problem stats url:




PabloGilberto , ivan_metelsky , ged

Problem categories:

Geometry, Simulation