Transform to Chessboard

hard math bit-manipulation matrix

Problem

Given an n x n binary board, return the minimum number of row+column swaps to transform it into a chessboard pattern, or -1 if impossible.

Inputboard=[[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]

Output2

Swap second row with third, then second column with third.

input

def movesToChessboard(board):
    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
    rowSum = sum(board[0])
    colSum = sum(board[i][0] for i in range(n))
    if rowSum not in (n//2, (n+1)//2): return -1
    if colSum not in (n//2, (n+1)//2): return -1
    rowSwap = sum(board[i][0] == (i % 2) for i in range(n))
    colSwap = sum(board[0][i] == (i % 2) for i in range(n))
    if n % 2:
        if rowSwap % 2: rowSwap = n - rowSwap
        if colSwap % 2: colSwap = n - colSwap
    else:
        rowSwap = min(rowSwap, n - rowSwap)
        colSwap = min(colSwap, n - colSwap)
    return (rowSwap + colSwap) // 2

function movesToChessboard(board) {
  const n = board.length;
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++)
      if (board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) return -1;
  let rs = 0, cs = 0, rSwap = 0, cSwap = 0;
  for (let i = 0; i < n; i++) {
    rs += board[0][i]; cs += board[i][0];
    if (board[i][0] === (i & 1)) rSwap++;
    if (board[0][i] === (i & 1)) cSwap++;
  }
  if (rs !== n>>1 && rs !== (n+1)>>1) return -1;
  if (cs !== n>>1 && cs !== (n+1)>>1) return -1;
  if (n & 1) {
    if (rSwap & 1) rSwap = n - rSwap;
    if (cSwap & 1) cSwap = n - cSwap;
  } else {
    rSwap = Math.min(rSwap, n - rSwap);
    cSwap = Math.min(cSwap, n - cSwap);
  }
  return (rSwap + cSwap) / 2;
}

int movesToChessboard(int[][] board) {
    int n = board.length;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if ((board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) != 0) return -1;
    int rs = 0, cs = 0, rSwap = 0, cSwap = 0;
    for (int i = 0; i < n; i++) {
        rs += board[0][i]; cs += board[i][0];
        if (board[i][0] == (i & 1)) rSwap++;
        if (board[0][i] == (i & 1)) cSwap++;
    }
    if (rs != n/2 && rs != (n+1)/2) return -1;
    if (cs != n/2 && cs != (n+1)/2) return -1;
    if ((n & 1) == 1) {
        if ((rSwap & 1) == 1) rSwap = n - rSwap;
        if ((cSwap & 1) == 1) cSwap = n - cSwap;
    } else {
        rSwap = Math.min(rSwap, n - rSwap);
        cSwap = Math.min(cSwap, n - cSwap);
    }
    return (rSwap + cSwap) / 2;
}

int movesToChessboard(vector<vector<int>>& board) {
    int n = board.size();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) return -1;
    int rs = 0, cs = 0, rSwap = 0, cSwap = 0;
    for (int i = 0; i < n; i++) {
        rs += board[0][i]; cs += board[i][0];
        if (board[i][0] == (i & 1)) rSwap++;
        if (board[0][i] == (i & 1)) cSwap++;
    }
    if (rs != n/2 && rs != (n+1)/2) return -1;
    if (cs != n/2 && cs != (n+1)/2) return -1;
    if (n & 1) {
        if (rSwap & 1) rSwap = n - rSwap;
        if (cSwap & 1) cSwap = n - cSwap;
    } else {
        rSwap = min(rSwap, n - rSwap);
        cSwap = min(cSwap, n - cSwap);
    }
    return (rSwap + cSwap) / 2;
}

Explanation

A real chessboard has a hidden structure: it is made of only two row patterns that are exact opposites of each other. The solution checks the board is even legal, confirms the counts balance, then counts how many swaps fix row 0 and column 0.

First the validity test: for every cell, board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] must be 0. If any 2x2 corner breaks this, the board can never become a chessboard, so we return -1.

Next, a chessboard needs each row and column to have nearly half ones, so the number of ones in row 0 and column 0 must be n/2 or (n+1)/2; otherwise -1.

Then we count how far row 0 and column 0 are from the ideal 0,1,0,1... pattern. For even n we pick the cheaper of the two possible parities with min(swaps, n - swaps); for odd n the parity is forced. Since each swap fixes two misplaced cells, the answer is (rowSwaps + colSwaps) / 2.

For the example board the column needs one swap and the row needs one swap, giving (2 + 2) / 2 = 2.

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