הפרות של Farmer John אוהבות לשחק בגרסה מעניינת של המשחק הפופולרי ״סודוקו״. גרסתן משתמשת בלוח $9 \times 9$ עם תתי־לוחות של $3 \times 3$, בדיוק כמו סודוקו רגיל. אולם גרסת הפרות משתמשת רק בספרות בינאריות:
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 \times 3$ תהיה בעלת זוגיות זוגית (כלומר תכיל מספר זוגי של אחדות). בדוגמה שלמעלה, קבוצה של 3 היפוכים נותנת פתרון תקין:
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
בהינתן המצב ההתחלתי של לוח סודוקו בינארי, עזרו לפרות לקבוע את המספר המינימלי של היפוכים הנדרש לפתרונו.
קלט
- שורות $1..9$: כל שורה מכילה מחרוזת בינארית בת 9 ספרות המתאימה לשורה אחת של הלוח ההתחלתי.
פלט
- שורה 1: המספר המינימלי של היפוכים הדרוש כדי שלכל שורה, עמודה ותת־לוח תהיה זוגיות זוגית.
דוגמאות
קלט 1
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
פלט 1
3
Note
לוח הסודוקו שבקלט לדוגמה זהה לזה שבטקסט הבעיה למעלה.
שלושה היפוכים מספיקים לפתרון החידה.
מחבר הבעיה: Brian Dean