The 0-1 Game Puzzle

This is a binary puzzle where you need to fill an N×N board with the digits \(0\) and \(1\). Initially, some cells are already filled with fixed digits that cannot be changed. The goal is to fill all the remaining (empty) cells such that:

• Every empty cell is filled with either \(0\) or \(1\).
• In any row or column, the same digit does not appear three or more times consecutively. In other words, for any row or column, neither \(000\) nor \(111\) is allowed.
• Each row and each column must have an equal number of \(0\)s and \(1\)s. (For example, when \(N=4\) each row and column must contain exactly \(2\) zeros and \(2\) ones.)
• All rows are unique and all columns are unique; that is, no two rows (or columns) are exactly the same.

The input is guaranteed to have a unique solution.

inputFormat

The first line contains an even integer \(N\) representing the size of the board. The following \(N\) lines each contain a string of length \(N\) consisting of characters '0', '1', and '.' where the character '.' represents an empty cell.

Example:

4
0.11
11..
.101
1.10

outputFormat

Output the completed board in \(N\) lines. Each line should be a string of length \(N\) consisting solely of '0' and '1', which represents the solved board.

Example:

0011
1100
0101
1010

sample

4
0.11
11..
.101
1.10

0011
1100
0101
1010