No knowledge of chess or mastery of its play is required to solve the following problems, other than the knowledge (or the ability to look up) how some particular type of chess piece moves. (Considering the historical and social significance of chess in all cultures in both East and West, the basic chess pieces and their moves should pretty much be part of the assumed general knowledge of any educated person anyway.)

In this kind of problems, the chessboard can be of an arbitrary size n * n instead of the usual 8 * 8. The chess pieces still move and capture like they would in the normal 8 * 8 game of chess (but they can now move as far as they can within the board, not just up to the distance of 8 tiles), but otherwise any square can contain any piece of either colour, whatever each problem happens to need. (In some wacky chess problem, there could even be a thousand queens and another thousand kings simultaneously on the board!) The squares of the board are numbered same way as in Java two-dimensional arrays, with their row and column indices from the range 0 to n - 1.

Write the following methods in the class named ChessProblems. In each method, try to use as few levels of nested loops as possible. In each problem, the recommended number of nested loops is given in parentheses after the problem. (Try not to be a multidimensional Shlemiel, the k-dimensional generalization of the simple one-dimensional Shlemiel who uses two nested for-loops to do something to an array that could be done with just one loop. The JUnit tester methods are of course written to be heavy enough so that they will get very slow for multidimensional Shlemiels who use more than the necessary number of levels of nested loops.)

Start by copy-pasting the following method to your ChessProblems class, since it will come handy for both questions 2 and 3. This method checks whether the coordinates (i, j) are inside the n*n chessboard, to prevent your method from crashing because of index out of bounds error.

private static boolean inside(int i, int j, int n) { return 0 <= i && i < n && 0 <= j && j < n; }

Write a method public int countSafeSquaresRooks(int n, boolean[][] rooks) that is given an n * n board that is guaranteed to contain only rooks of the same colour, with the parameter array rooks telling whether a given square contains a rook. This method should count and return the number of empty squares on the board that are not threatened by any rook. A square is threatened by a rook in the same row or same column. (2 levels of nesting. Hint: use two one-dimensional boolean arrays to keep track which rows and columns have been discovered to have a rook somewhere in them.)

Write a method public int countKnightMoves(int n, boolean[][] knights) that counts how many moves are possible on an n * n chessboard where every piece is a knight of the same colour, with the array knights telling whether the given square contains a knight. This method should count how many different moves are possible in the current board, adding up the number of moves that each knight can do. Unlike other chess pieces, a chess knight can jump over other knights, but cannot move into a square that already contains another knight, or jump outside the board. (3 levels of nesting: two for the possible positions on the board, and one for the eight possible directions that each chess knight can potentially move to.) Hint: you might find the following two-dimensional array quite useful. Its each two-element row tells you how many steps the knight takes to the x- and y-directions when moving to the particular direction chosen from the eight possible directions of a chess knight. private static final int[][] knightMoves = { {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1} };

Write a method public int countPawnMoves(int n, char[][] board) that, similar to previous method, counts how many moves are possible on a board that contains some number of white and black pawns, and no other pieces, in arbitrary positions. The board is now given as an n*n array of characters, with the possible values 'w' for white pawn, 'b' for black pawn, and the whitespace character ' ' for an empty square. Each chess pawn has up to three possible moves: it can move either one step directly forward into an empty square, or either one step forward and left, or one step forward and right to capture a pawn of opposite colour. (In this problem, the en passant captures for pawns do not exist, nor does the promotion to higher rank when reaching the row on the opposite side.) A pawn cannot move outside the board or into a square occupied by another pawn of the same colour. Note that unlike in actual chess diagrams whose row numbering system conventionally increases to the the opposite direction than Java array indexing, for white pawns "forward" means the direction of decreasing row number (so a white pawn in square (i, j) might move to squares (i - 1, j - 1), (i - 1, j) and (i - 1, j + 1), depending on what is in those squares). For black pawns, "forward" means the direction of increasing row number. (Three nested loops, with the outermost loop running for exactly two rounds, once for white pawns, once for the blacks, with the two inner loops looping through the positions of the chessboard. This could be done by unrolling from three loops to two by copy-pasting the entire logic for two separate blocks for white and black pawns, but that would be ugly.)

Write a method public int countSafeSquaresQueens(int n, boolean[][] queens) that works the same as the first method, but this time for chess queens instead of rooks. A queen threatens every square not just in the same row and column, but also in the same diagonal for all four diagonal directions. (2 levels of nesting, by generalizing the boolean array approach used for rooks. See the hint below.) Hint: In an n * n chessboard, there are n rows, n columns, 2 * n - 1 diagonals going northeast, and 2 * n - 1 diagonals going southeast. Allocate four boolean arrays, two of which are size n just like in the rooks problem, and two are of size 2 * n for the diagonals. The square with coordinates (i, j) resides in row i, column j, SE diagonal (n - i + j) and NE diagonal (i + j). Your method should loop through the entire chessboard, and for each queen that you find, update the four boolean arrays using these indices. After this, loop through the entire chessboard again, and count how many squares are safe from attack from all directions.

TEST

import static org.junit.Assert.*; import org.junit.After; import org.junit.Before; import org.junit.Test; import java.util.*; import java.util.zip.Adler32; // TESTER UPDATED NOVEMBER 21 TO FIX BUG IN ROOKS public class TestChessProblems { private static final int SEED = 12345; private ChessProblems mp = new ChessProblems(); @Test public void testCountSafeSquaresRooks() { java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); int total = 0, answer; LinkedList qxl = new LinkedList(); LinkedList qyl = new LinkedList(); for(int n = 3; n < 100; n++) { boolean[][] board = new boolean[n][n]; int count = 1; for(int trials = 0; trials < n + 1; trials++) { answer = mp.countSafeSquaresRooks(n, board); total += answer; check.update(answer); int nx, ny; for(int i = 0; i < count; i++) { do { // find a square that does not have a rook yet nx = rng.nextInt(n); ny = rng.nextInt(n); } while(board[nx][ny]); board[nx][ny] = true; qxl.add(nx); qyl.add(ny); answer = mp.countSafeSquaresRooks(n, board); total += answer; check.update(answer); } for(int i = 0; i < count - 1; i++) { nx = qxl.removeFirst(); ny = qyl.removeFirst(); board[nx][ny] = false; answer = mp.countSafeSquaresRooks(n, board); total += answer; check.update(answer); } count++; } } assertEquals(23172158, total); assertEquals(3601595543L, check.getValue()); } @Test public void testCountSafeSquaresQueens() { java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); int total = 0, answer; LinkedList qxl = new LinkedList(); LinkedList qyl = new LinkedList(); for(int n = 3; n < 30; n++) { boolean[][] board = new boolean[n][n]; int count = 1; for(int trials = 0; trials < (n * n) / 20 + 3; trials++) { answer = mp.countSafeSquaresQueens(n, board); total += answer; check.update(answer); int nx, ny; for(int i = 0; i < count; i++) { do { // find a square that does not have a queen yet nx = rng.nextInt(n); ny = rng.nextInt(n); } while(board[nx][ny]); board[nx][ny] = true; qxl.add(nx); qyl.add(ny); answer = mp.countSafeSquaresQueens(n, board); total += answer; check.update(answer); } for(int i = 0; i < count - 1; i++) { nx = qxl.removeFirst(); ny = qyl.removeFirst(); board[nx][ny] = false; answer = mp.countSafeSquaresQueens(n, board); total += answer; check.update(answer); } count++; } } assertEquals(100838, total); assertEquals(3505386471L, check.getValue()); } @Test public void testCountKnightMoves() { java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); int total = 0, answer; LinkedList kxl = new LinkedList(); LinkedList kyl = new LinkedList(); for(int n = 3; n < 25; n++) { boolean[][] board = new boolean[n][n]; int count = 1; for(int trials = 0; trials < (n * n) / 8; trials++) { answer = mp.countKnightMoves(n, board); total += answer; check.update(answer); int nx, ny; for(int i = 0; i < count; i++) { do { // find a square that does not have a knight yet nx = rng.nextInt(n); ny = rng.nextInt(n); } while(board[nx][ny]); board[nx][ny] = true; kxl.add(nx); kyl.add(ny); answer = mp.countKnightMoves(n, board); total += answer; check.update(answer); } for(int i = 0; i < count - 1; i++) { nx = kxl.removeFirst(); ny = kyl.removeFirst(); board[nx][ny] = false; answer = mp.countKnightMoves(n, board); total += answer; check.update(answer); } count++; } } assertEquals(14630390, total); assertEquals(2101292833L, check.getValue()); } @Test public void testCountPawnMoves() { char[] pieces = {'b', 'b', 'w', 'w', ' '}; java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); int total = 0, answer; for(int n = 3; n < 25; n++) { char[][] board = new char[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { board[i][j] = ' '; } } for(int c = 0; c < n * n * n; c++) { int i = rng.nextInt(n); int j = rng.nextInt(n); board[i][j] = pieces[rng.nextInt(pieces.length)]; answer = mp.countPawnMoves(n, board); total += answer; check.update(answer); } } assertEquals(25063550, total); assertEquals(1049171076L, check.getValue()); } }