<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:
    # First we check if it is possible to turn the board into a chessboard
    # There are some important properties of a chessboard:
    # 1. Chessboards only have 2 types of rows
    # 2. Chessboards only have 2 types of cols
    # 3. Counts of the 2 row types must be equal (n/2 and n/2) - or if odd near equal (n - 1) / 2 and (n + 1) / 2
    # 4. Counts of the 2 col types must be equal
    # 5. The 2 row types MUST be an inverse of each other (if row1[i] == 0, then row2[i] must be 1 and vice-versa)
    # 6. The 2 col types MUST be an inverse of each other
    #
    # All of these properties also apply as requirements for a board, if it can be converted to a chessboard
    #
    # More insights:
    # If we fix either of the 2 row types, then we also fix the other row type.
    # The same applies for the 2 col types.
    #
    # To fix a row or a col, we need to count the differences between it and the actual line.
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)

        # calculate counts for rows and cols
        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
        
        # there should only be 2 types of rows and cols if it's possible to transform to chessboard
        if len(row_count) != 2 or len(col_count) != 2:
            return -1

        # for even n, we expect counts to be n / 2 and n /2. for odd n, we expect counts to be (n - 1) / 2 and (n + 1) / 2
        expected_counts = [n // 2, (n + 1) // 2] 
        if sorted(row_count.values()) != expected_counts or sorted(col_count.values()) != expected_counts:
            return -1

        # for it to be possible to transform to chessboard, the 2 types of rows must be an inverse of each other
        row1, row2 = row_count.keys()

        for n1, n2 in zip(row1, row2):
            if sorted([n1, n2]) != [0, 1]:
                return -1

        # at this point we are sure there is way to turn board into a chessboard
        ans = 0

        def count_moves(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

                min_moves = min(min_moves, differences // 2)
            return min_moves

        # for rows and cols, there's only 2 possible lines
        for (line1, line2) in (row_count.keys(), col_count.keys()):
            # if n is even, we 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 += count_moves(line1, starts)
        
        return ans

16400