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

<p>Return <em>the minimum number of moves to transform the board into a <strong>chessboard board</strong></em>. If the task is impossible, return <code>-1</code>.</p>

<p>A <strong>chessboard board</strong> is a board where no <code>0</code>&#39;s and no <code>1</code>&#39;s are 4-directionally adjacent.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/chessboard1-grid.jpg" style="width: 500px; height: 145px;" />
<pre>
<strong>Input:</strong> board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/chessboard2-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[0,1],[1,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> Also note that the board with 0 in the top left corner, is also a valid chessboard.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/chessboard3-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[1,0],[1,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> No matter what sequence of moves you make, you cannot end with a valid chessboard.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 30</code></li>
	<li><code>board[i][j]</code> is either&nbsp;<code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)
        
        def fn(vals):
            """Return min moves to transform to chessboard."""
            total = odd = 0 
            # Iterate through values in vals and count total and odd occurrences
            for i, x in enumerate(vals): 
                if vals[0] == x: 
                    total += 1
                    if i & 1: odd += 1
                elif vals[0] ^ x != (1 << n) - 1: 
                    return inf
            ans = inf 
            # Check conditions for valid configurations and update ans accordingly
            if len(vals) <= 2 * total <= len(vals) + 1: 
                ans = min(ans, odd)
            if len(vals) - 1 <= 2 * total <= len(vals): 
                ans = min(ans, total - odd)
            return ans 
        
        # Initialize lists to store rows and columns
        rows, cols = [0] * n, [0] * n
        # Update rows and columns based on the input board
        for i in range(n): 
            for j in range(n): 
                if board[i][j]: 
                    rows[i] ^= 1 << j 
                    cols[j] ^= 1 << i
        # Calculate the minimum moves for rows and columns and sum them up
        ans = fn(rows) + fn(cols)
        # Return ans if it is less than inf, otherwise return -1
        return ans if ans < inf else -1
16400