Get started

Transform to Chessboard — Hard Problem & Solution

board is an n x n binary grid. In one move you may swap any two rows or any two columns.

Problem statement

board is an n x n binary grid. In one move you may swap any two rows or any two columns.

A chessboard is a board in which no two cells that share an edge hold the same value — the 0s and 1s alternate along every row and every column.

Return the minimum number of moves that turn board into a chessboard, or -1 if it cannot be done.

Example 1

Input: board = [[1,1,0,0],[0,0,1,1],[1,1,0,0],[0,0,1,1]]
Output: 1
Explanation: The rows already alternate; swapping columns 1 and 2 finishes the job.

Example 2

Input: board = [[1,0],[0,1]]
Output: 0

Example 3

Input: board = [[1,1,0],[0,0,1],[1,0,0]]
Output: -1
Explanation: Rows `[0,0,1]` and `[1,0,0]` are neither equal nor complementary, which no swap can fix.

Constraints

  • n == board.length
  • n == board[i].length
  • 2 <= n <= 30
  • board[i][j] is 0 or 1

How to solve Transform to Chessboard

Row swaps and column swaps act independently, and a chessboard is fully determined by its first row and first column, so the problem splits into two 1D "make this 0/1 line alternate by swaps" problems.

Approach

  1. Check b[0][0] ^ b[i][0] ^ b[0][j] ^ b[i][j] == 0 for every cell; otherwise return -1 (some row is neither the first row nor its complement).
  2. Count the 1s in the first row and in the first column; each must be n / 2 or (n + 1) / 2 (rounded down/up), otherwise return -1.
  3. Let rowSwap be the number of i with b[i][0] == i % 2 and colSwap the number with b[0][i] == i % 2 — the mismatches against the pattern 1010….
  4. If n is odd, only one pattern has the right number of 1s and its mismatch count is even: replace an odd count x by n - x. If n is even, take min(x, n - x).
  5. Return (rowSwap + colSwap) / 2.

Why it works

Any reachable board has the same multiset of rows as the input, permuted, with all rows permuted by the same column order. A chessboard has exactly two row kinds (complements of each other) in alternating order, so the XOR condition and the balance are necessary — and sufficient, since the first column and first row can each be arranged independently. Fixing a 0/1 line needs one swap per pair of misplaced entries, i.e. mismatches / 2, and that is also a lower bound because a swap fixes at most two positions.

Complexity

  • Time — O(n²)
  • Space — O(1)

Pitfalls

  • For odd n, only the target whose majority value matches the line's majority is possible — do not take a plain minimum.
  • Checking only the first row and column is not enough; every row must be the first row or its complement.
  • Each swap fixes two mismatches, so divide the total by 2.

Reference solution

Python

from typing import List

def movesToChessboard(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 = sum(board[0])
    col_sum = sum(board[i][0] for i in range(n))
    if not (n // 2 <= row_sum <= (n + 1) // 2) or not (n // 2 <= col_sum <= (n + 1) // 2):
        return -1
    row_swap = sum(1 for i in range(n) if board[i][0] == i % 2)
    col_swap = sum(1 for i in range(n) if board[0][i] == i % 2)
    if n % 2 == 1:
        if row_swap % 2 == 1:
            row_swap = n - row_swap
        if col_swap % 2 == 1:
            col_swap = n - col_swap
    else:
        row_swap = min(row_swap, n - row_swap)
        col_swap = min(col_swap, n - col_swap)
    return (row_swap + col_swap) // 2

JavaScript

var movesToChessboard = function(board) {
    var n = board.length;
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if ((board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) !== 0) return -1;
        }
    }
    var rowSum = 0, colSum = 0, rowSwap = 0, colSwap = 0;
    for (var k = 0; k < n; k++) {
        rowSum += board[0][k];
        colSum += board[k][0];
        if (board[k][0] === k % 2) rowSwap++;
        if (board[0][k] === k % 2) colSwap++;
    }
    var lo = Math.floor(n / 2), hi = Math.floor((n + 1) / 2);
    if (rowSum < lo || rowSum > hi || colSum < lo || colSum > hi) return -1;
    if (n % 2 === 1) {
        if (rowSwap % 2 === 1) rowSwap = n - rowSwap;
        if (colSwap % 2 === 1) colSwap = n - colSwap;
    } else {
        rowSwap = Math.min(rowSwap, n - rowSwap);
        colSwap = Math.min(colSwap, n - colSwap);
    }
    return (rowSwap + colSwap) / 2;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal