<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)

        # calculate counts for each rows type and col type
        row_count = defaultdict(int)
        col_count = defaultdict(int)

        for row in board:
            row_count[tuple(row)] += 1
        
        for col in zip(*board):
            col_count[tuple(col)] += 1
        
        # Check requirements 1 and 2
        if len(row_count) != 2 or len(col_count) != 2:
            return -1

        # Check requirements 3 and 4
        row1, row2 = row_count.keys()
        for n1, n2 in zip(row1, row2):
            if sorted([n1, n2]) != [0, 1]:
                return -1

        # Check requirements 5 and 6
        expected_counts = [n // 2, (n + 1) // 2] 
        if sorted(row_count.values()) != expected_counts or sorted(col_count.values()) != expected_counts:
            return -1

        # We have checked all requirements, there is an answer
        ans = 0

        # This loop will run once for rows and once for keys
        for (line1, line2) in (row_count.keys(), col_count.keys()):
            # For rows and cols, there's only 2 possible types: line1 and line2
            # By default, assume line1 can start with either 0 or 1
            starts = [0, 1]

            # If n is odd, we need to see whether 1 is more common or 0 in line1
            # and the start value for that line HAS to be the more common number
            if n % 2 == 1:
                starts = [1] if line1.count(1) > line1.count(0) else [0]
            ans += self.count_moves(line1, starts)
        
        return ans

    # Number of moves needed to convert line to the correct value
    def count_moves(self, line, starts):
        min_moves = float('inf')
        inverse = [1, 0]

        for start in starts:
            differences = 0

            for i, val in enumerate(line):
                if i % 2 == 1:
                    differences += 0 if val == inverse[start] else 1
                else:
                    differences += 0 if val == start else 1

            # If there are 6 differences, we can fix the line
            # In 3 moves (since each move affects two lines)
            min_moves = min(min_moves, differences // 2)
        return min_moves
16600