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.

&nbsp;
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.


&nbsp;
Constraints:


	n == board.length
	n == board[i].length
	2 &lt;= n &lt;= 30
	board[i][j] is either&nbsp;0 or 1.


class Solution(object):
    def movesToChessboard(self, board):
        N = len(board)
        ans = 0
        # For each count of lines from {rows, columns}...
        for count in (collections.Counter(map(tuple, board)),  # get row
                      collections.Counter(zip(*board))): #get column

            # If there are more than 2 kinds of lines,
            # or if the number of kinds is not appropriate ...
            if len(count) != 2 or sorted(count.values()) != [N/2, (N+1)/2]:
                return -1

            # If the lines are not opposite each other, impossible
            line1, line2 = count
            if not all(x ^ y for x, y in zip(line1, line2)):
                return -1

            # starts = what could be the starting value of line1
            # If N is odd, then we have to start with the more
            # frequent element
            starts = [int(line1.count(1) * 2 > N)] if N%2 else [0, 1]

            # To transform line1 into the ideal line [i%2 for i ...],
            # we take the number of differences and divide by two
            ans += min(sum((x-i) % 2 for i, x in enumerate(line1, start))
                       for start in starts) / 2            

        return ans
class Solution {
    public int movesToChessboard(int[][] board) {
        int N = board.length, colToMove = 0, rowToMove = 0, rowOneCnt = 0, colOneCnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (((board[0][0] ^ board[i][0]) ^ (board[i][j] ^ board[0][j])) == 1) {
                    return -1;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            rowOneCnt += board[0][i];
            colOneCnt += board[i][0];
            if (board[i][0] == i % 2) {
                rowToMove++;
            }
            if (board[0][i] == i % 2) {
                colToMove++;
            }
        }
        if (rowOneCnt < N / 2 || rowOneCnt > (N + 1) / 2) {
            return -1;
        }
        if (colOneCnt < N / 2 || colOneCnt > (N + 1) / 2) {
            return -1;
        }
        if (N % 2 == 1) {
            // we cannot make it when ..ToMove is odd
            if (colToMove % 2 == 1) {
                colToMove = N - colToMove;
            }
            if (rowToMove % 2 == 1) {
                rowToMove = N - rowToMove;
            }
        } else {
            colToMove = Math.min(colToMove, N - colToMove);
            rowToMove = Math.min(rowToMove, N - rowToMove);
        }
        return (colToMove + rowToMove) / 2;
    }

}
class Solution {
    const int inf = 1e9;
    void transpose(vector<vector<int>>& board) {
        const int n = board.size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                swap(board[i][j], board[j][i]);
    }
    
    bool isSame(vector<int> &r1, vector<int>& r2) {
        const int n = r1.size();
        for (int i = 0; i < n; i++)
            if (r1[i] != r2[i])
                return false;
        return true;
    }
    
    bool isOpposite(vector<int> &r1, vector<int>& r2) {
        const int n = r1.size();
        for (int i = 0; i < n; i++)
            if (r1[i] == r2[i])
                return false;
        return true;
    }
    
    int getSteps(vector<vector<int>> &&confusionMatrix) {
        int steps = inf;
        
        if (confusionMatrix[0][1] == confusionMatrix[1][0])
            steps = confusionMatrix[0][1];
        
        if (confusionMatrix[0][0] == confusionMatrix[1][1])
            steps = min(steps, confusionMatrix[0][0]);
        
        return steps;
    }
    
    vector<vector<int>> getConfusionMatrix(vector<int>& rowType) {
        const int n = rowType.size();
        vector<vector<int>> confusionMatrix(2, vector<int>(2, 0));
        for (int i = 0; i < n; i++)
            confusionMatrix[rowType[i]][i & 1]++;
        return confusionMatrix;
    }
    
    int solve1d(vector<int> &arr) {
        return getSteps(getConfusionMatrix(arr));
    }
    
    int makeColumnsAlternating(vector<vector<int>>& board) {
        const int n = board.size();
        vector<int> rowType(n, 0);
        for (int i = 1; i < n; i++)
            if (isOpposite(board[0], board[i]))
                rowType[i] = 1;
            else if (!isSame(board[0], board[i]))
                return inf;
        return solve1d(rowType);
    }
public:
    int movesToChessboard(vector<vector<int>>& board) {
        int steps = makeColumnsAlternating(board);
        transpose(board);
        steps += makeColumnsAlternating(board);
        if (steps >= inf)
            return -1;
        return steps;
    }
};
/**
 * @param {number[][]} board
 * @return {number}
 */
var movesToChessboard = function(board) {
    const boardSize = board.length;
    const boardSizeIsEven = boardSize % 2 === 0;

    if(!canBeTransformed(board)) return -1;

    // to convert to 010101
    let rowSwap = 0;
    let colSwap = 0;

    // to convert to 101010
    let rowSwap2 = 0;
    let colSwap2 = 0;

    for(let i=0; i<boardSize; i++) {
        if(board[i][0] === i % 2) {
            rowSwap++;
        } else {
            rowSwap2++;
        }
        if(board[0][i] === i % 2) {
            colSwap++;
        } else {
            colSwap2++;
        }
    }

    // no need to swap anything
    if((rowSwap + colSwap) === 0 || (rowSwap2 + colSwap2) === 0) return 0;

    if(boardSizeIsEven) {
        rowSwap = Math.min(rowSwap, rowSwap2);
        colSwap = Math.min(colSwap, colSwap2);
    } else {
        rowSwap = rowSwap % 2 === 0 ? rowSwap : rowSwap2;
        colSwap = colSwap % 2 === 0 ? colSwap : colSwap2;
    }

    return (rowSwap + colSwap) / 2;

    function canBeTransformed(board) {
        // number of 0 and 1 should be equal
        let sum = board[0].reduce((a,b) => a+b);
        if(boardSizeIsEven && sum != boardSize/2) return false;
        if(!boardSizeIsEven && sum > ((boardSize + 1)/2)) return false;

        let first = board[0].join('');
        let opposite = board[0].map((item) => item === 1 ? 0 : 1).join('');
        // each row should be equal to first or opposite
        let counter = [0,0];
        for(let i=0; i<boardSize; i++) {
            let str = board[i].join('');
            if(str == first) {
                counter[0]++;
            } else if(str == opposite) {
                counter[1]++;
            } else {
                return false;
            }
        }
        // for even board, two types of rows should be equal
        if(boardSizeIsEven) {
            return counter[0] == counter[1];
        }
        return Math.abs(counter[0] - counter[1]) === 1
    }
};
Transform to Chessboard