Transform to Chessboard

Problem Statement

You are working with an n x n binary grid known as board. Each cell of this grid contains either a 0 or a 1. Your objective is to transform this board into a "chessboard" arrangement. A chessboard is defined such that no two adjacent cells (those that share a side) contain the same number. You can make moves to achieve this pattern, where a single move allows you to swap any two rows or any two columns. The challenge is to determine the minimum number of such swaps needed to convert the given board into a chessboard pattern. If it's impossible to achieve such an arrangement, the function should return -1.

Examples

Example 1

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.

Example 2

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.

Example 3

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.

Approach and Intuition

To solve this problem, you'll need to carefully navigate through the board and calculate the optimal number of swaps:

1. Understand the Chessboard Pattern: The board should alternate between 0 and 1. This necessitates a pattern where rows and columns adhere to either of two combinations: starting with 0 or starting with 1.

2. Identify Swap Feasibility: Before delving into swaps, ascertain whether a chessboard configuration is possible. This involves:

   • Count rows and columns to see if they can be paired into two groups (one starting with 0 and the other with 1).
   • Ensure that positions where 0s and 1s are found can actually be swapped to form the desired alternating pattern.

3. Switch to Correct Placement:

   • For rows: Calculate how many rows already match either possible chessboard starting rows (either starts with 0 or 1). The number of swaps for rows will be the discrepancies divided by 2, as each swap corrects two rows.
   • For columns: Similarly, calculate mismatches and deduce the number of necessary swaps.

4. Calculate Minimum Swaps: Notably, if a row (or column) needs to be switched, all elements along it shift; thus affecting the entire column (or row). Hence, swaps need to be synchronized to minimize disruptions.

5. Return the Result: Sum the minimum swaps for rows and columns for the total minimal moves needed to form a chessboard. If any configuration checks indicate that the transformation is impossible, return -1.

Through these analysis steps, the code will determine the fewest moves required to convert any given binary grid into a chessboard arrangement, ensuring optimum efficiency and correctness.

Solutions

class Solution {
    public int calculateMoves(int[][] matrix) {
        int size = matrix.length;
    
        Map<Integer, Integer> linePattern = new HashMap<>();
        for (int[] line : matrix) {
            int binaryValue = 0;
            for (int element : line)
                binaryValue = 2 * binaryValue + element;
            linePattern.put(binaryValue, linePattern.getOrDefault(binaryValue, 0) + 1);
        }
    
        int rowAnalysis = checksum(linePattern, size);
        if (rowAnalysis == -1) return -1;
    
        linePattern = new HashMap<>();
        for (int column = 0; column < size; ++column) {
            int binaryValue = 0;
            for (int row = 0; row < size; ++row)
                binaryValue = 2 * binaryValue + matrix[row][column];
            linePattern.put(binaryValue, linePattern.getOrDefault(binaryValue, 0) + 1);
        }
    
        int columnAnalysis = checksum(linePattern, size);
        return columnAnalysis >= 0 ? rowAnalysis + columnAnalysis : -1;
    }
    
    public int checksum(Map<Integer, Integer> patternCount, int size) {
        if (patternCount.size() != 2) return -1;
    
        List<Integer> keys = new ArrayList(patternCount.keySet());
        int firstKey = keys.get(0), secondKey = keys.get(1);
    
        if (!(patternCount.get(firstKey) == size/2 && patternCount.get(secondKey) == (size+1)/2) &&
                !(patternCount.get(secondKey) == size/2 && patternCount.get(firstKey) == (size+1)/2))
            return -1;
    
        if ((firstKey ^ secondKey) != (1<<size) - 1)
            return -1;
    
        int binaryFullSet = (1 << size) - 1;
        int countOnes = Integer.bitCount(firstKey & binaryFullSet);
        int minimumSwapsNeeded = Integer.MAX_VALUE;
        if (size % 2 == 0 || countOnes * 2 < size)
            minimumSwapsNeeded = Math.min(minimumSwapsNeeded, Integer.bitCount(firstKey ^ 0xAAAAAAAA & binaryFullSet) / 2);
    
        if (size % 2 == 0 || countOnes * 2 > size)
            minimumSwapsNeeded = Math.min(minimumSwapsNeeded, Integer.bitCount(firstKey ^ 0x55555555 & binaryFullSet) / 2);
    
        return minimumSwapsNeeded;
    }
}