Chessboard

problem: using 31 dominoes, where one domino covers exactly two squares, can you cover all the empty squares on this chessboard (which has 62 spaces). if so, how? if not, why?   

Solution

i think everyone’s first inclination is to try and figure out how it is possible. then again, if you’ve heard a bunch of these questions before, you usually know that if the question says “if not, why?” or “prove whether its possible or impossible”, you can infer that it is not possible (otherwise, the question usually just asks for the solution).

after awhile fiddling around with the dominoes, you will start to realize that the most obvious solutions are not viable. if you start to think its impossible, think about why.

a reader emailed me telling me that using the picture of the chessboard without the squares colored will result in a very small percentage of people solving the problem. if i use the following picture

a much higher percentage of people will be able to solve the problem. the people who solve the problem using only the grid, usually represent the problem in their heads as the colored board.

still can’t figure it out? using the colored board, remember that a domino always covers a black square and a white square.

if you look at the board, you will see that the two squares missing are both black. this means that for all the squares on the board, each white square has a corresponding black square, except for two white ones. so even if you covered all the black/white pairs, you would still be left with two white squares, which will never be adjacent to each other, no matter how you lay out the dominoes.

2026 Update: Chessboard Problems — Combinatorics and Graph Theory

Chessboard problems test spatial reasoning, graph modeling, and combinatorics. Classic variants:

# Problem 1: Can you tile an 8×8 board (minus 2 opposite corners) with dominoes?
# Answer: NO. Opposite corners are same color. Dominoes always cover one black + one white.
# With 2 same-colored corners removed: 32 black, 30 white (or vice versa) → impossible.

def domino_tiling_possible(n, m, removed_squares):
    """
    Check if n×m board with removed squares can be tiled with 1×2 dominoes.
    Uses coloring argument: count black vs white squares.
    """
    # Standard chessboard coloring
    black = (n * m + 1) // 2 - sum(1 for r, c in removed_squares if (r+c) % 2 == 0)
    white = (n * m) // 2 - sum(1 for r, c in removed_squares if (r+c) % 2 == 1)
    # Necessary condition: equal black and white (not sufficient in general)
    return black == white

# 8×8 minus opposite corners (0,0) and (7,7) — both same color
print(domino_tiling_possible(8, 8, [(0,0), (7,7)]))  # False

# 8×8 minus (0,0) and (0,1) — different colors
print(domino_tiling_possible(8, 8, [(0,0), (0,1)]))  # True

# Problem 2: Knight's tour — Hamiltonian path on chessboard graph
def knights_tour(n=5):
    """Find a knight's tour on n×n board using Warnsdorff's heuristic."""
    moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]

    def valid(x, y, visited):
        return 0 <= x < n and 0 <= y < n and (x,y) not in visited

    def degree(x, y, visited):
        return sum(1 for dx,dy in moves if valid(x+dx, y+dy, visited))

    def solve(x, y, visited, path):
        if len(path) == n*n:
            return path
        neighbors = [(x+dx, y+dy) for dx,dy in moves if valid(x+dx, y+dy, visited)]
        # Warnsdorff: always move to square with fewest onward moves
        neighbors.sort(key=lambda p: degree(p[0], p[1], visited))
        for nx, ny in neighbors:
            visited.add((nx, ny))
            result = solve(nx, ny, visited, path + [(nx,ny)])
            if result:
                return result
            visited.discard((nx, ny))
        return None

    visited = {(0, 0)}
    tour = solve(0, 0, visited, [(0,0)])
    return tour

tour = knights_tour(5)
print(f"5×5 knight's tour found: {tour is not None}")  # True

# Problem 3: N-Queens on chessboard (see our dedicated post)
# Problem 4: Bishops on 8×8 — max non-attacking bishops?
# Answer: 14 (2*(n-1) for n×n board, all on edge squares of alternating colors)
print(f"Max non-attacking bishops on 8×8: {2*(8-1)}")  # 14

Interview insight: Chessboard problems test whether you can model a 2D problem as a graph. The coloring argument (domino tiling) is a proof technique that generalizes to many impossibility proofs. Knight’s tour = Hamiltonian path problem = NP-complete in general, but heuristics (Warnsdorff’s rule) work well on regular boards.

function solveNQueens(n) {
    const solutions = [];
    const board = Array(n).fill(null).map(() => Array(n).fill('.'));

    function isSafe(row, col) {
        // Check column
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }

        // Check diagonal (top-left)
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }

        // Check diagonal (top-right)
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }

        return true;
    }

    function backtrack(row) {
        if (row === n) {
            // Found a solution
            solutions.push(board.map(r => r.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';  // Undo
            }
        }
    }

    backtrack(0);
    return solutions;
}

// Test
const solutions = solveNQueens(4);
console.log(`Found ${solutions.length} solutions`);
solutions.forEach((sol, i) => {
    console.log(`nSolution ${i + 1}:`);
    sol.forEach(row => console.log(row));
});

function minKnightMoves(x, y) {
    // Make coordinates positive (symmetric problem)
    x = Math.abs(x);
    y = Math.abs(y);

    const moves = [
        [2, 1], [2, -1], [-2, 1], [-2, -1],
        [1, 2], [1, -2], [-1, 2], [-1, -2]
    ];

    const visited = new Set();
    const queue = [[0, 0, 0]];  // [x, y, steps]
    visited.add('0,0');

    while (queue.length > 0) {
        const [cx, cy, steps] = queue.shift();

        if (cx === x && cy === y) {
            return steps;
        }

        for (const [dx, dy] of moves) {
            const nx = cx + dx;
            const ny = cy + dy;
            const key = `${nx},${ny}`;

            // Limit search area (optimization)
            if (nx >= -2 && ny >= -2 && !visited.has(key)) {
                visited.add(key);
                queue.push([nx, ny, steps + 1]);
            }
        }
    }

    return -1;
}

console.log(minKnightMoves(2, 1));   // 1
console.log(minKnightMoves(5, 5));   // 4

function uniquePaths(m, n) {
    // m×n grid, move right or down only
    const dp = Array(m).fill(null).map(() => Array(n).fill(1));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

console.log(uniquePaths(3, 7));  // 28
console.log(uniquePaths(3, 2));  // 3