cho.shBinary Sudoku
No attempts yetTime limit1sMemory limit128 MBProblem
Binary Sudoku is a variant of Sudoku. Like ordinary Sudoku, it is played on a 9 × 9 grid, and the whole board is divided into nine 3 × 3 sub-regions (blocks). Unlike ordinary Sudoku, every cell of Binary Sudoku holds only 0 or 1.
000 000 000
001 000 100
000 000 000
000 110 000
000 111 000
000 000 000
000 000 000
000 000 000
000 000 000
The goal of Binary Sudoku is to make the number of 1s in every row, every column, and every 3 × 3 block even, using as few toggles as possible. A toggle changes a single cell from 0 to 1 or from 1 to 0.
The puzzle above can be solved with three toggles, as shown below.
000 000 000
001 000 100
001 000 100
000 110 000
000 110 000
000 000 000
000 000 000
000 000 000
000 000 000
Given the initial state of a Binary Sudoku, write a program that computes the minimum number of toggles needed to solve the puzzle.
Input
The initial state of the Binary Sudoku is given over nine lines. Each line consists of nine characters, each either 0 or 1.
Output
Print the minimum number of toggles needed to solve the Binary Sudoku.
Hint
A toggle is the operation of changing a cell from 0 to 1 or from 1 to 0.