Binary Sudoku
Time limit1sMemory limit128 MB
Given a 9x9 grid of 0s and 1s, find the fewest toggles so that every row, column, and 3x3 block has an even number of 1s.
- Level
Medium7 of 10
- Topics
- Math, Bit manipulation, Brute force
- Solved
- No attempts yet
Problem
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.