Les vaches de Farmer John aiment jouer à une variante intéressante du jeu populaire « Sudoku ». Leur version utilise une grille de $9 \times 9$ composée de sous-grilles de $3 \times 3$, comme le sudoku ordinaire. Cependant, leur version n’utilise que des chiffres binaires :
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
Le but du sudoku binaire est d’inverser le moins de bits possible pour que chacune des neuf lignes, des neuf colonnes et des neuf sous-grilles de $3 \times 3$ ait une parité paire (c’est-à-dire contienne un nombre pair de $1$). Pour l’exemple ci-dessus, un ensemble de 3 inversions donne une solution valide :
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
Étant donné l’état initial d’une grille de sudoku binaire, aidez les vaches à déterminer le nombre minimal d’inversions nécessaires pour la résoudre.
Entrée
- Lignes $1..9$ : chaque ligne contient une chaîne binaire de 9 chiffres correspondant à une ligne de la grille initiale.
Sortie
- Ligne 1 : le nombre minimal d’inversions nécessaires pour que chaque ligne, colonne et sous-grille ait une parité paire.
Exemples
Entrée 1
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
Sortie 1
3
Remarque
La grille de sudoku de l’exemple d’entrée est la même que dans le texte du problème ci-dessus.
Trois inversions suffisent pour résoudre le puzzle.
Auteur du problème : Brian Dean