Cracking the Coding Interview Together – Problem 6.3: Dominoes on a Mutilated Chessboard

Picture this: You are in a high-stakes system design interview, and the interviewer hands you a grid-tiling problem. Your immediate instinct as a software engineer might be to start sketching out a complex backtracking algorithm, a dynamic programming state-compression model, or a heavy graph-matching framework. We love to write code, and we love to build complex systems. But as senior engineers, we must always remember one of our core tenets: The most elegant code is the code we never have to write.

Today, we are going to tackle a classic brain teaser from Cracking the Coding Interview: Problem 6.3 (Dominoes), also famously known in mathematics as the Mutilated Chessboard Problem. On the surface, it looks like a combinatorial search problem. But beneath its simple grid layout lies a profound lesson in mathematical invariants, graph theory, and algorithmic efficiency. Our goal today is to dissect this problem together, write a programmatic solver to prove our findings, and understand how to apply this style of thinking to real-world software architecture.

Problem Statement

The problem is defined as follows:

There is an 8x8 chessboard in which two diagonally opposite corners have been cut off. You are given 31 dominoes, and a single domino can cover exactly two adjacent squares. Can you use the 31 dominoes to cover the entire board?

Let's define our operational goals:

• Determine if a complete tiling of the mutilated board is mathematically possible.
• Provide a rigorous proof of our conclusion.
• Design and implement a programmatic simulation in Java to validate our proof and explore the state space of the generalized problem.

Analyze the Problem Together

Let's start by breaking down the raw numbers. A standard chessboard is an 8x8 grid, containing exactly 64 squares. If we cut off two diagonally opposite corners, we remove exactly 2 squares. This leaves us with:

64 - 2 = 62 squares

We are given 31 dominoes. Since each domino covers exactly 2 adjacent squares, 31 dominoes can cover:

31 * 2 = 62 squares

On paper, the arithmetic matches perfectly! It is incredibly tempting to assume that because the total area matches, a valid configuration must exist. A naive approach would attempt to place dominoes one by one, backtracking whenever we hit a dead end, hoping to find a valid layout.

But let's look closer. What is the defining characteristic of a chessboard? It alternates colors.

A standard 8x8 chessboard has exactly 32 white squares and 32 black squares. Now, let's think about the two diagonally opposite corners that we cut off. On any chessboard, diagonally opposite corners always share the same color. If the top-left corner is white, the bottom-right corner must also be white. Why? Because the sum of their coordinates (row + column) will have the same parity (both even or both odd).

By removing two diagonally opposite corners, we are removing two squares of the same color. Let's assume we removed two white squares. Our remaining board now contains:

• 32 black squares
• 30 white squares

Now, let's analyze the fundamental constraint of a domino. A single domino must cover exactly two adjacent squares. On a chessboard, any two adjacent squares must be of opposite colors—one black and one white. Therefore, no matter how you place a domino, it must cover exactly 1 black square and 1 white square.

This is our invariant. If we place 31 dominoes on the board, they must cover exactly 31 black squares and 31 white squares. But our mutilated board only has 30 white squares! We are short by 2 white squares, leaving 2 black squares permanently uncovered. Thus, it is mathematically impossible to tile the mutilated chessboard.

Comparing Approaches

Questions for the Interviewer

In an actual interview, a senior engineer doesn't just jump into coding. We ask clarifying questions to define the boundaries of the problem. Here are three questions we should ask:

1. "Are we strictly solving this for a standard 8x8 board, or should we design a generalized solver that can handle arbitrary grid dimensions and arbitrary missing cells?" (This shows we think about scalability and generalization).
2. "Can we assume the dominoes cannot be cut, bent, or placed diagonally?" (Confirms the physical constraints of the tiling).
3. "Is our goal to simply return a boolean indicating if a tiling is possible, or do we need to output the actual coordinates of the domino placements if a solution exists?" (Clarifies the expected output and API design).

Think About the Solution

Even though we have proven the 8x8 mutilated chessboard is impossible in O(1) time, an interviewer will often say: "Excellent proof. Now, write a program that can prove this programmatically for any arbitrary board configuration with missing cells."

To do this, we will build a programmatic solver in Java using backtracking (Depth-First Search). This allows us to demonstrate our coding proficiency while highlighting the massive difference in performance between brute-force search and mathematical invariants.

Here is our high-level architectural plan:

• Represent the board as an N x M boolean grid, where true represents an available square and false represents an unavailable (or already covered) square.
• We will initialize the board, marking the top-left and bottom-right corners as false (mutilated).
• Our recursive backtracking function will scan the board to find the first available uncovered square.
• For that square, it will attempt to place a domino either horizontally (covering the current square and its right neighbor) or vertically (covering the current square and its bottom neighbor).
• If a placement is valid, we mark both squares as false, recurse to place the next domino, and backtrack (mark them true again) if the path leads to a dead end.
• If we successfully cover all available squares, we return true. If we exhaust all possibilities and find no solution, we return false.

Write Code and Explain

Let's implement this elegant backtracking solver in Java. We will write clean, production-ready code with comprehensive comments.

public class ChessboardTiler {

    private final int rows;
    private final int cols;
    private final boolean[][] board;

    public ChessboardTiler(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.board = new boolean[rows][cols];
        
        // Initialize all squares as available (true)
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                board[r][c] = true;
            }
        }
    }

    /**
     * Mutilates the board by removing specific cells.
     */
    public void removeCell(int r, int c) {
        if (isValidCell(r, c)) {
            board[r][c] = false;
        }
    }

    /**
     * Public API to trigger the tiling solver.
     */
    public boolean canTile() {
        return solve(0, 0);
    }

    /**
     * Recursive backtracking solver.
     */
    private boolean solve(int r, int c) {
        // If we've reached past the last row, we have successfully tiled the board!
        if (r >= rows) {
            return true;
        }

        // Move to the next row if we've reached the end of the current column
        if (c >= cols) {
            return solve(r + 1, 0);
        }

        // If the current cell is already covered or removed, skip to the next cell
        if (!board[r][c]) {
            return solve(r, c + 1);
        }

        // Try placing a domino HORIZONTALLY (current cell and right neighbor)
        if (c + 1 < cols && board[r][c + 1]) {
            // Place domino
            board[r][c] = false;
            board[r][c + 1] = false;

            if (solve(r, c + 2)) {
                return true;
            }

            // Backtrack
            board[r][c] = true;
            board[r][c + 1] = true;
        }

        // Try placing a domino VERTICALLY (current cell and bottom neighbor)
        if (r + 1 < rows && board[r + 1][c]) {
            // Place domino
            board[r][c] = false;
            board[r + 1][c] = false;

            if (solve(r, c + 1)) {
                return true;
            }

            // Backtrack
            board[r][c] = true;
            board[r + 1][c] = true;
        }

        // If no placement is possible from this state, return false
        return false;
    }

    private boolean isValidCell(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    public static void main(String[] args) {
        // 1. Test a standard 8x8 board (Should be tileable)
        ChessboardTiler standardBoard = new ChessboardTiler(8, 8);
        System.out.println("Can tile standard 8x8 board? " + standardBoard.canTile()); // Expected: true

        // 2. Test the Mutilated 8x8 board (Opposite corners removed)
        ChessboardTiler mutilatedBoard = new ChessboardTiler(8, 8);
        mutilatedBoard.removeCell(0, 0);       // Top-left corner
        mutilatedBoard.removeCell(7, 7);       // Bottom-right corner
        
        long startTime = System.currentTimeMillis();
        boolean result = mutilatedBoard.canTile();
        long endTime = System.currentTimeMillis();
        
        System.out.println("Can tile mutilated 8x8 board? " + result); // Expected: false
        System.out.println("Time taken to prove programmatically: " + (endTime - startTime) + " ms");
    }
}

Code Walkthrough

Let's trace how this code executes on our mutilated board:

1. We instantiate an 8x8 board and call removeCell(0, 0) and removeCell(7, 7). This sets those two positions to false.
2. We invoke canTile(), which starts the recursion at (0, 0).
3. At (0, 0), the solver sees that board[0][0] is already false (removed). It immediately skips to (0, 1).
4. At (0, 1), the cell is available. The solver tries to place a horizontal domino covering (0, 1) and (0, 2). It marks them false and recurses.
5. The algorithm continues traversing the board, placing dominoes and backtracking whenever it hits a dead end. Because there is no valid configuration, the algorithm will exhaustively search the entire state space before finally returning false.

Time & Space Complexity

Let's analyze the complexity of our programmatic solution versus our mathematical proof:

• Backtracking Solver Time Complexity: In the worst case, this is O(2^(W * H)), where W is the width and H is the height of the board. For an 8x8 board, the search space is small enough to execute in a few milliseconds, but as the board size scales, this exponential complexity quickly becomes a bottleneck.
• Backtracking Solver Space Complexity: O(W * H) due to the recursion stack depth, which is bounded by the total number of cells on the board.
• Mathematical Invariant Complexity: O(1) time and O(1) space. By checking the parity of the removed cells, we can answer the question instantly without any search.

Why This Problem Matters (The Senior Perspective)

You might be wondering: "When am I ever going to tile a chessboard with dominoes in production?"

The answer is never. But the mental model used to solve this problem is highly relevant to modern software architecture. Here is why:

1. The Power of Invariants in Distributed Systems

In system design, we often deal with complex, asynchronous state transitions. Trying to trace every possible execution path (like our backtracking solver) is impossible. Instead, we rely on invariants—properties of a system that remain true regardless of the state transitions. For example:

• In double-entry bookkeeping, the sum of debits must always equal the sum of credits. If they don't, we don't need to trace every transaction to know there is a bug.
• In distributed consensus algorithms like Raft, the invariant that "there is at most one leader per term" prevents split-brain scenarios.

2. Graph Matching and Resource Allocation

The generalized version of this problem (tiling an arbitrary grid with dominoes) is equivalent to finding a Perfect Matching in a Bipartite Graph. In software engineering, bipartite matching is used to solve real-world resource allocation problems:

• Matching drivers to riders in ride-sharing applications (Uber/Lyft).
• Assigning tasks to servers in a cluster to maximize throughput.
• Scheduling shifts for employees based on availability constraints.

Final Thoughts

The Mutilated Chessboard Problem is a beautiful reminder that before we write a single line of code, we should always step back and analyze the underlying mathematical structure of the problem. A simple parity check saved us from running an exponential-time search algorithm.

Next time you are faced with a complex state-tracking problem, ask yourself: "What is the invariant here?" Finding that invariant might just save you hundreds of lines of code and hours of debugging.

Thanks for reading, and happy coding! If you enjoyed this deep dive, share it with your team, and let's keep learning together.