Su Doku

Problem 96

Su Doku (japanisch für Zahlen platzieren) ist der Name eines bekannten Puzzle-Konzepts. Sein Ursprung ist unklar, aber Anerkennung muss Leonhard Euler gezollt werden, der eine ähnliche und deutlich schwierigere Puzzle-Idee namens Lateinische Quadrate erfand. Aber das Ziel bei Su-Doku-Rätseln ist es, alle Lücken (oder Nullen) in einem 9×9-Gittter so zu ersetzen, dass jede Reihe, Spalte und 3×3-Box jede der Ziffern von 1 bis 9 enthält. Unten ist ein Beispiel eines typischen Anfangs-Puzzle-Gitters und sein Lösungs-Gitter.

0 0 3
9 0 0
0 0 1
0 2 0
3 0 5
8 0 6
6 0 0
0 0 1
4 0 0
0 0 8
7 0 0
0 0 6
1 0 2
0 0 0
7 0 8
9 0 0
0 0 8
2 0 0
0 0 2
8 0 0
0 0 5
6 0 9
2 0 3
0 1 0
5 0 0
0 0 9
3 0 0
4 8 3
9 6 7
2 5 1
9 2 1
3 4 5
8 7 6
6 5 7
8 2 1
4 9 3
5 4 8
7 2 9
1 3 6
1 3 2
5 6 4
7 9 8
9 7 6
1 3 8
2 4 5
3 7 2
8 1 4
6 9 5
6 8 9
2 5 3
4 1 7
5 1 4
7 6 9
3 8 2

Ein gut konstruiertes Su-Doku-Rätsel hat eine eindeutige Lösung und kann mit Logik gelöst werden, obwohl es notwendig sein kann, "Raten und testen"-Methoden zu benutzen, um Möglichkeiten zu eliminieren (es gibt viele umstrittene Meinungen dazu). Die Komplexität der Suche bestimmt die Schwierigkeit des Puzzle; das Beispiel oben wird als einfach betrachtet, da es durch direkte Ableitung gelöst werden kann.

Die 6K Textdatei sudoku.txt (Rechtsklick und 'Link/Ziel speichern unter...') enthält fünfzig verschiedene Su-Doku-Puzzles in verschiedenen Schwierigkeiten, aber alle mit eindeutigen Lösungen (das erste Puzzle in der Datei ist das Beispiel oben).

Lösen Sie alle fünfzig Puzzles und finden Sie die Summe der dreistelligen Zahlen, die in der linken oberen Ecke jedes Lösungs-Gitters zu finden sind; Beispiel: 483 ist die dreistellige Zahl, die in der linken oberen Ecke im Lösungs-Gitter oben gefunden werden kann.