Transform to Chessboard Python Solution

Tested Python solution for LeetCode 782 with 27 pytest cases. Generate a practice environment with lcpy.

LeetCode 782, Hard. Topics: Array, Math, Bit Manipulation, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 27 parametrized pytest cases, and a playground notebook:

lcpy gen -n 782   # by problem number
lcpy gen -s transform_to_chessboard   # by problem name

​

Problem

You are given an n x n binary grid board. In each move, you can swap any two rows with each other, or any two columns with each other.

Return the minimum number of moves to transform the board into a chessboard board. If the task is impossible, return -1.

A chessboard board is a board where no 0’s and no 1’s are 4-directionally adjacent.

​

Examples

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.

Input: board = [[0,1],[1,0]]
Output: 0
Explanation: Also note that the board with 0 in the top left corner, is also a valid chessboard.

Input: board = [[1,0],[1,0]]
Output: -1
Explanation: No matter what sequence of moves you make, you cannot end with a valid chessboard.

​

Constraints

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

def _line_swaps(masks: list[int], n: int) -> int:
    """Min swaps to make one axis alternate, or -1 if that axis cannot."""
    full = (1 << n) - 1
    first = masks[0]
    if set(masks) != {first, full ^ first}:
        return -1
    ones = bin(first).count("1")
    if ones * 2 not in (n - 1, n, n + 1):
        return -1
    count_first = masks.count(first)
    if abs(count_first - (n - count_first)) > 1:
        return -1
    need_even = (n + 1) // 2
    best = -1
    for even_mask in (first, full ^ first):
        if masks.count(even_mask) != need_even:
            continue
        target = [even_mask if i % 2 == 0 else full ^ even_mask for i in range(n)]
        misplaced = sum(1 for i in range(n) if masks[i] != target[i])
        swaps = misplaced // 2
        best = swaps if best < 0 else min(best, swaps)
    return best


class Solution:
    # Time: O(n^2)
    # Space: O(n)
    def moves_to_chessboard(self, board: list[list[int]]) -> int:
        n = len(board)
        rows = [sum(cell << j for j, cell in enumerate(row)) for row in board]
        cols = [sum(board[i][j] << i for i in range(n)) for j in range(n)]
        total = 0
        for masks in (rows, cols):
            swaps = _line_swaps(masks, n)
            if swaps < 0:
                return -1
            total += swaps
        return total

​

Complexity

Time	Space
O(n^2)	O(n)

​

Tags