바이너리 스도쿠

바이너리 스도쿠는 스도쿠를 변형한 퍼즐이다. 일반 스도쿠처럼 9 × 9 칸으로 이루어져 있으며, 전체 판은 3 × 3 크기의 작은 구간(블록) 아홉 개로 나뉜다. 일반 스도쿠와 달리 바이너리 스도쿠의 각 칸에는 0 또는 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

바이너리 스도쿠의 목표는 각 행, 각 열, 그리고 각 3 × 3 블록에 들어 있는 1의 개수가 모두 짝수가 되도록 만드는 것이다. 이때 토글 횟수를 최소로 해야 한다. 토글이란 한 칸의 값을 0에서 1로, 또는 1에서 0으로 바꾸는 연산이다.

위 퍼즐은 다음과 같이 토글을 세 번 사용하여 해결할 수 있다.

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

바이너리 스도쿠의 초기 상태가 주어졌을 때, 이 퍼즐을 해결하기 위해 필요한 최소 토글 횟수를 구하는 프로그램을 작성하시오.

아홉 개의 줄에 걸쳐 바이너리 스도쿠의 초기 상태가 주어진다. 각 줄은 0과 1로 이루어진 아홉 개의 문자로 구성된다.

바이너리 스도쿠를 해결하기 위해 필요한 최소 토글 횟수를 한 줄에 출력한다.

토글은 한 칸의 값을 0에서 1로, 또는 1에서 0으로 바꾸는 연산이다.