Satisfiability Problem · SAT solvers

Lesson 10

Nikolai Chukhin · Alexander S. Kulikov

Programming problem. A \(12 \times 10\) grid is partially filled with 0's and 1's. Fill in the remaining cells so that there are no four consecutive identical elements in any row, column, or diagonal.

  • Input format.  A grid is given as 12 lines each of which contain 10 space separated symbols from \(\{0, 1, *\}\).

  • Output format.  Output a fully filled grid in the same format. It is guaranteed that a solution exists.

5 points
Public samples
Public sample 1
Input
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
Expected output
0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 0
0 0 1 1 1 0 1 0 1 0
1 1 1 0 0 1 1 0 1 1
0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 0
1 0 1 0 1 0 1 1 1 0
0 1 1 0 1 1 0 0 0 1
0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 0
1 0 1 1 1 0 1 0 1 0
0 1 0 0 0 1 1 0 1 1