LeetCode 782: Transform to Chessboard

Problem Restatement

We are given an n x n binary board.

Each cell is either 0 or 1.

In one move, we may do one of these operations:

We need to return the minimum number of moves required to transform the board into a chessboard.

A chessboard means no two 4-directionally adjacent cells have the same value.

If it is impossible, return -1.

Input and Output

Function shape:

class Solution:
    def movesToChessboard(self, board: list[list[int]]) -> int:
        ...

Examples

Example 1:

board = [
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
]

The answer is:

2

One valid transformation uses one column swap and one row swap.

Example 2:

board = [
    [0, 1],
    [1, 0],
]

This is already a valid chessboard.

The answer is:

0

Example 3:

board = [
    [1, 0],
    [1, 0],
]

The answer is:

-1

Swapping rows or columns cannot make both rows alternate with each other.

First Thought: Try All Row and Column Orders

A brute force approach would try every permutation of rows and every permutation of columns.

For each arrangement, we check whether the board is a chessboard.

This is not feasible.

There are n! possible row orders and n! possible column orders.

So the number of arrangements is:

n! * n!

Since n can be up to 30, brute force is impossible.

Key Insight

Row swaps and column swaps do not change the internal relationship between cells.

A valid chessboard has a strict structure.

For any cells (0, 0), (i, 0), (0, j), and (i, j), a valid transformable board must satisfy:

board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] == 0

Why?

In a chessboard-like matrix, each cell is determined by its row type and column type. The value at (i, j) must be consistent with the first row and first column.

If this XOR expression equals 1 for any cell, the board has an invalid pattern that row and column swaps cannot fix.

After feasibility is checked, we only need to count how many row swaps and column swaps are needed.

Rows are controlled by the first column.

Columns are controlled by the first row.

Feasibility Conditions

There are two checks.

First, every cell must satisfy the XOR condition:

board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] == 0

Second, the number of 1s in the first row and first column must be valid.

For a chessboard of size n:

So:

row_sum in {n // 2, (n + 1) // 2}
col_sum in {n // 2, (n + 1) // 2}

If either condition fails, return -1.

Counting Swaps

After validation, compute row swaps and column swaps separately.

For rows, look at the first column:

board[i][0]

In a final chessboard, the first column must alternate.

So compare board[i][0] with:

i % 2

Count how many positions already match one alternating pattern.

For columns, do the same with the first row:

board[0][i]

Compare it with:

i % 2

Let:

row_swaps
col_swaps

be mismatch-like counts against one possible alternating pattern.

If n is even, either alternating pattern is valid, so choose the smaller side:

row_swaps = min(row_swaps, n - row_swaps)
col_swaps = min(col_swaps, n - col_swaps)

If n is odd, only one alternating pattern has the correct majority count. We must choose the count that is even.

if row_swaps % 2 == 1:
    row_swaps = n - row_swaps

if col_swaps % 2 == 1:
    col_swaps = n - col_swaps

Each swap fixes two misplaced rows or columns, so the answer is:

(row_swaps + col_swaps) // 2

Algorithm

1. Let n = len(board).
2. Check every cell using the XOR feasibility rule.
3. Count 1s in the first row and first column.
4. If either count is invalid, return -1.
5. Count row arrangement cost from the first column.
6. Count column arrangement cost from the first row.
7. Adjust the counts depending on whether n is odd or even.
8. Return half of the total misplaced count.

Correctness

A row swap only changes the order of rows. A column swap only changes the order of columns. Therefore, if the board has a structural inconsistency inside its row and column patterns, no sequence of swaps can fix it.

The XOR condition checks this structural consistency. For every cell (i, j), the relation among board[0][0], board[i][0], board[0][j], and board[i][j] must match a matrix formed by alternating row and column types. If any cell violates this relation, the board cannot become a chessboard.

The count condition is also necessary. In a valid chessboard, each row and each column has balanced values. If n is even, every row and column has exactly half 0s and half 1s. If n is odd, the counts differ by exactly one. Checking the first row and first column is sufficient after the XOR condition, because all other rows and columns are either the same pattern or its complement.

Once these conditions hold, the board can be transformed into a chessboard. The only remaining task is arranging the two row types and the two column types so that they alternate.

Rows can be solved independently from columns because row swaps do not change column patterns, and column swaps do not change row patterns.

The first column identifies which row type each row belongs to. Comparing it against an alternating pattern counts how many rows are placed in the wrong parity positions. One row swap fixes two wrong row positions, so row moves equal half the adjusted row count. The same reasoning applies to columns using the first row.

Therefore, the algorithm returns the minimum number of row and column swaps needed.

Complexity

Implementation

class Solution:
    def movesToChessboard(self, board: list[list[int]]) -> int:
        n = len(board)

        for i in range(n):
            for j in range(n):
                if board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]:
                    return -1

        row_sum = 0
        col_sum = 0
        row_swaps = 0
        col_swaps = 0

        for i in range(n):
            row_sum += board[0][i]
            col_sum += board[i][0]

            if board[i][0] == i % 2:
                row_swaps += 1

            if board[0][i] == i % 2:
                col_swaps += 1

        if row_sum != n // 2 and row_sum != (n + 1) // 2:
            return -1

        if col_sum != n // 2 and col_sum != (n + 1) // 2:
            return -1

        if n % 2 == 1:
            if row_swaps % 2 == 1:
                row_swaps = n - row_swaps

            if col_swaps % 2 == 1:
                col_swaps = n - col_swaps
        else:
            row_swaps = min(row_swaps, n - row_swaps)
            col_swaps = min(col_swaps, n - col_swaps)

        return (row_swaps + col_swaps) // 2

Code Explanation

The first loop checks whether the board has a transformable structure:

if board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]:
    return -1

If this expression is 1, the board cannot be transformed into a chessboard.

Next, we count the number of 1s in the first row and first column:

row_sum += board[0][i]
col_sum += board[i][0]

These counts must be valid for a chessboard.

We also count how many row and column positions match one alternating pattern:

if board[i][0] == i % 2:
    row_swaps += 1

if board[0][i] == i % 2:
    col_swaps += 1

For odd n, only one alternating pattern has the correct majority count, so we choose the even count:

if row_swaps % 2 == 1:
    row_swaps = n - row_swaps

For even n, both patterns are valid, so we take the smaller count:

row_swaps = min(row_swaps, n - row_swaps)

Finally, each swap fixes two misplaced positions:

return (row_swaps + col_swaps) // 2

Testing

def run_tests():
    s = Solution()

    assert s.movesToChessboard([
        [0, 1, 1, 0],
        [0, 1, 1, 0],
        [1, 0, 0, 1],
        [1, 0, 0, 1],
    ]) == 2

    assert s.movesToChessboard([
        [0, 1],
        [1, 0],
    ]) == 0

    assert s.movesToChessboard([
        [1, 0],
        [1, 0],
    ]) == -1

    assert s.movesToChessboard([
        [1, 1, 0],
        [0, 0, 1],
        [0, 0, 1],
    ]) == 2

    assert s.movesToChessboard([
        [1, 0, 1],
        [0, 1, 0],
        [1, 0, 1],
    ]) == 0

    print("all tests passed")

run_tests()

Test coverage: