# 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:

| Move | Meaning |
|---|---|
| Swap two rows | Exchange any two complete rows |
| Swap two columns | Exchange any two complete columns |

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

| Item | Meaning |
|---|---|
| Input | An `n x n` binary matrix `board` |
| Output | Minimum number of row or column swaps |
| Valid move | Swap any two rows or any two columns |
| Valid final board | Adjacent cells must alternate between `0` and `1` |
| Impossible case | Return `-1` |

Function shape:

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

## Examples

Example 1:

```python
board = [
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
]
```

The answer is:

```python
2
```

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

Example 2:

```python
board = [
    [0, 1],
    [1, 0],
]
```

This is already a valid chessboard.

The answer is:

```python
0
```

Example 3:

```python
board = [
    [1, 0],
    [1, 0],
]
```

The answer is:

```python
-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:

```text
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:

```python
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:

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

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

For a chessboard of size `n`:

| `n` parity | Count of `1`s in a row or column |
|---|---|
| Even | Exactly `n / 2` |
| Odd | Either `n // 2` or `(n + 1) // 2` |

So:

```python
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:

```python
board[i][0]
```

In a final chessboard, the first column must alternate.

So compare `board[i][0]` with:

```python
i % 2
```

Count how many positions already match one alternating pattern.

For columns, do the same with the first row:

```python
board[0][i]
```

Compare it with:

```python
i % 2
```

Let:

```python
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:

```python
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.

```python
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:

```python
(row_swaps + col_swaps) // 2
```

## Algorithm

1. Let `n = len(board)`.
2. Check every cell using the XOR feasibility rule.
3. Count `1`s 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 `0`s and half `1`s. 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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We scan all cells for the feasibility check |
| Space | `O(1)` | Only counters are used |

## Implementation

```python
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:

```python
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 `1`s in the first row and first column:

```python
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:

```python
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:

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

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

```python
row_swaps = min(row_swaps, n - row_swaps)
```

Finally, each swap fixes two misplaced positions:

```python
return (row_swaps + col_swaps) // 2
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `4 x 4` standard case | Requires both row and column swaps |
| Already valid `2 x 2` board | Checks zero moves |
| Impossible `2 x 2` board | Checks feasibility rejection |
| Odd-sized transformable board | Checks odd majority handling |
| Already valid `3 x 3` board | Checks odd board with zero moves |