You are given an n x n binary matrix called board. In one move, you can swap any two rows or any two columns of the matrix. Your goal is to transform the matrix into a chessboard pattern using the minimum number of moves.
A chessboard pattern is defined as a matrix where no two 0's or two 1's are adjacent horizontally or vertically. That is, every cell is different from its neighbors above, below, left, and right.
Return the minimum number of moves required to transform the given board to a chessboard. If it is not possible, return -1.
At first glance, this problem might seem to require checking all possible permutations of rows and columns to see if a chessboard can be formed. However, that would be extremely inefficient for larger matrices.
The key realization is that, because we can swap any rows or columns, the only thing that matters is the pattern of the rows and columns, not their order. If the board can be rearranged into a chessboard, then all rows (and all columns) must be of only two types: one type and its bitwise inverse.
Therefore, the problem reduces to checking if the board has the right structure, and then calculating the minimum swaps needed to arrange rows and columns into the required chessboard order.
Brute-force would involve generating all permutations, but with the above insight, we can optimize by just counting and matching patterns.
-1 (impossible).n, exactly equal; for odd n, differ by one).n, pick the minimum of both possibilities; for odd n, only the one that matches the majority.
The approach uses only a few passes over the board and simple counting, making it efficient.
Sample Input:
board = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]
The board is already a chessboard, so the answer is 0.
n! permutations of rows and columns → O((n!)^2) time. Not feasible for large n.
O(n^2). We scan all rows and columns a few times.
O(n) for storing row/column patterns.
The "Transform to Chessboard" problem is solved efficiently by recognizing that only the patterns of rows and columns matter, not their order, thanks to the ability to swap any of them. By verifying that the board only contains two valid patterns (and their inverses), and then counting the minimum swaps needed to arrange them in a chessboard configuration, we avoid brute-force and achieve a fast, elegant solution.
class Solution:
def movesToChessboard(self, board):
n = len(board)
import collections
def get_moves(lines):
ones = sum(lines[0])
if not n // 2 <= ones <= (n + 1) // 2:
return -1
pattern1 = [i % 2 for i in range(n)]
pattern2 = [1 - i % 2 for i in range(n)]
cnt1 = cnt2 = 0
for line in lines:
if line != pattern1 and line != pattern2:
return -1
# Count swaps needed
diff1 = sum(line != pattern1 for line in lines)
diff2 = sum(line != pattern2 for line in lines)
if n % 2 == 0:
return min(diff1, diff2) // 2
else:
if diff1 % 2 == 0:
return diff1 // 2
else:
return diff2 // 2
# Check rows
rows = [tuple(row) for row in board]
row_set = set(rows)
if len(row_set) != 2 or any(x ^ y for x, y in zip(*row_set)):
return -1
# Check columns
cols = [tuple(col) for col in zip(*board)]
col_set = set(cols)
if len(col_set) != 2 or any(x ^ y for x, y in zip(*col_set)):
return -1
# Calculate swaps for rows and columns
def min_swaps(lines):
n = len(lines)
ones = sum(line[0] for line in lines)
if not n // 2 <= ones <= (n + 1) // 2:
return -1
pattern = [i % 2 for i in range(n)]
line0 = [line[0] for line in lines]
swaps1 = sum(line0[i] != pattern[i] for i in range(n))
swaps2 = n - swaps1
if n % 2 == 0:
return min(swaps1, swaps2) // 2
else:
if swaps1 % 2 == 0:
return swaps1 // 2
else:
return swaps2 // 2
row_swaps = min_swaps(rows)
col_swaps = min_swaps(cols)
if row_swaps == -1 or col_swaps == -1:
return -1
return row_swaps + col_swaps
class Solution {
public:
int movesToChessboard(vector<vector<int>>& board) {
int n = board.size();
vector<int> rows, cols;
for (int i = 0; i < n; ++i) {
int r = 0, c = 0;
for (int j = 0; j < n; ++j) {
r = (r << 1) | board[i][j];
c = (c << 1) | board[j][i];
}
rows.push_back(r);
cols.push_back(c);
}
auto check = [](vector<int>& arr, int n) {
unordered_map<int,int> freq;
for (int x : arr) freq[x]++;
if (freq.size() != 2) return -1;
auto it = freq.begin();
int x = it->first, cx = it->second;
++it;
int y = it->first, cy = it->second;
if ((x ^ y) != (1 << n) - 1) return -1;
if (abs(cx - cy) > 1) return -1;
int mask = 0;
for (int i = 0; i < n; ++i) mask |= (i % 2) << (n-1-i);
int min_swaps = INT_MAX;
if (n % 2 == 0) {
int swap1 = 0, swap2 = 0;
for (int i = 0; i < n; ++i) {
if (((arr[i] ^ mask) & 1) != 0) swap1++;
if (((arr[i] ^ (~mask & ((1 << n)-1))) & 1) != 0) swap2++;
}
min_swaps = min(swap1, swap2) / 2;
} else {
int swap1 = 0;
for (int i = 0; i < n; ++i) {
if (((arr[i] ^ mask) & 1) != 0) swap1++;
}
if (swap1 % 2 != 0) swap1 = n - swap1;
min_swaps = swap1 / 2;
}
return min_swaps;
};
int row_swaps = check(rows, n);
int col_swaps = check(cols, n);
if (row_swaps == -1 || col_swaps == -1) return -1;
return row_swaps + col_swaps;
}
};
class Solution {
public int movesToChessboard(int[][] board) {
int n = board.length;
int[] rows = new int[n];
int[] cols = new int[n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
rows[i] = (rows[i] << 1) | board[i][j];
cols[i] = (cols[i] << 1) | board[j][i];
}
}
int rowSwaps = check(rows, n);
int colSwaps = check(cols, n);
if (rowSwaps == -1 || colSwaps == -1) return -1;
return rowSwaps + colSwaps;
}
private int check(int[] arr, int n) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
if (freq.size() != 2) return -1;
Iterator<Integer> it = freq.keySet().iterator();
int x = it.next(), y = it.next();
int cx = freq.get(x), cy = freq.get(y);
if ((x ^ y) != (1 << n) - 1) return -1;
if (Math.abs(cx - cy) > 1) return -1;
int mask = 0;
for (int i = 0; i < n; ++i) mask |= (i % 2) << (n - 1 - i);
int minSwaps = Integer.MAX_VALUE;
if (n % 2 == 0) {
int swap1 = 0, swap2 = 0;
for (int i = 0; i < n; ++i) {
if (((arr[i] ^ mask) & 1) != 0) swap1++;
if (((arr[i] ^ (~mask & ((1 << n) - 1))) & 1) != 0) swap2++;
}
minSwaps = Math.min(swap1, swap2) / 2;
} else {
int swap1 = 0;
for (int i = 0; i < n; ++i) {
if (((arr[i] ^ mask) & 1) != 0) swap1++;
}
if (swap1 % 2 != 0) swap1 = n - swap1;
minSwaps = swap1 / 2;
}
return minSwaps;
}
}
var movesToChessboard = function(board) {
const n = board.length;
// Helper to check lines (rows or columns)
function check(lines) {
let patterns = {};
for (let line of lines) {
let key = line.join('');
patterns[key] = (patterns[key] || 0) + 1;
}
let keys = Object.keys(patterns);
if (keys.length !== 2) return -1;
let a = keys[0], b = keys[1];
if (!a.split('').every((v, i) => v ^ b[i]) ) return -1;
let countA = patterns[a], countB = patterns[b];
if (Math.abs(countA - countB) > 1) return -1;
// Decide minimum swaps
let pattern = Array.from({length: n}, (_, i) => i % 2);
let arr = lines.map(line => line[0]);
let swaps1 = arr.filter((v, i) => v !== pattern[i]).length;
let swaps2 = n - swaps1;
if (n % 2 === 0) {
return Math.min(swaps1, swaps2) / 2;
} else {
if (swaps1 % 2 === 0) return swaps1 / 2;
else return swaps2 / 2;
}
}
// Check rows
let rows = board.map(row => row.slice());
let rowSwaps = check(rows);
if (rowSwaps === -1) return -1;
// Check columns
let cols = [];
for (let j = 0; j < n; ++j) {
let col = [];
for (let i = 0; i < n; ++i) col.push(board[i][j]);
cols.push(col);
}
let colSwaps = check(cols);
if (colSwaps === -1) return -1;
return rowSwaps + colSwaps;
};