2.5    Beispiel: Sudoku lösen

In diesem abschließenden Beispiel zeigen wir Ihnen, wie Sie im Zusammenspiel mit ChatGPT oder einem anderen KI-Tool ein Java-Programm zur Lösung von Sudokus entwickeln. Die Ausgangssituation ist die, dass Sie eigene Ideen verfolgen, mittels KI-Unterstützung aber mühsame Tipparbeit vermeiden möchten. Sie geben also klare Anweisungen, welchen Code die KI generieren soll, bauen diesen dann in Ihr Programm ein und entwickeln dieses selbstständig weiter, bis Sie auf Probleme stoßen. Wenn Sie so wollen, sind Sie der »Senior Developer«, der unangenehme Arbeit an einen »Junior AI Developer« delegieren kann.

Klassen-Setup

Sie arbeiten schrittweise. (Wir werden Ihnen am Ende des Abschnitts zeigen, dass Sie einen Sudoku-Solver auch mit einem einzigen Prompt bekommen – aber das ist nicht Ihr Ziel. Der Weg ist das Ziel, und im Verlauf dieses Wegs wollen Sie Ihre Fähigkeiten zur Strukturierung von Code vertiefen.)

Zu Beginn geben Sie die Struktur des Programms vor. Dabei lassen Sie dem KI-Bot wenig Wahl. Der Prompt enthält Informationen über Ihr Wissen, über die gewünschte Programmiersprache, über den geplanten Programmaufbau sowie über die Datenstruktur zur Speicherung des Sudokus.

Sie bitten das KI-Chat-System explizit darum, eine Sudoku-Klasse mit Instanzvariablen und Konstruktor einzurichten, aber ohne weitere Methoden. Außerdem soll das KI-Tool die Main-Klasse implementieren und dort ein einfaches Sudoku-Rätsel initialisieren. Sie brauchen ja ein Rätsel-Sudoku als Ausgangspunkt für die weiteren Tests.

Prompt: I am an intermediate Java programmer. I want to write a program to solve Sudokus. I want to do this step by step with your assistance. Please do NOT provide the complete code. Instead, help me to setup classes, add methods etc. in small steps.

My plan is to use (at least) two classes: Main with testing code and Sudoku to store and solve the Sudoku. More classes might follow.

The Sudoku is to be stored in a 9x9 int array. 0 means this cell is empty.

If this sounds OK, please provide the Sudoku class with a private instance variable for the array and a constructor to initialize the variable. The constructor should also verify the array size and its contents (only values between 0 and 9 allowed). Add no other code to the class.

Also provide the Main class which creates a Sudoku object and passes a simple but incomplete Sudoku to solve.

Sie kopieren die beiden Klassen in ein neues Java-Projekt und haben in zwei Minuten ein funktionsfähiges Grundgerüst für Ihren Code. Der Code für die Sudoku-Klasse sieht so aus:

import ...;
public class Sudoku {
    private int[][] grid;  // store Sudoku cells in array
    
     // constructor
     public Sudoku(int[][] grid) {
        // Check if the input grid is valid
        if (grid.length != 9 || grid[0].length != 9) {
            throw new IllegalArgumentException(
                "Grid must be a 9x9 array.");
        }
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (grid[i][j] < 0 || grid[i][j] > 9) {
                    throw new IllegalArgumentException(
                        "Grid values must be between 0 and 9.");
                }
            }
        }
        
        // Initialize the grid
        this.grid = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                this.grid[i][j] = grid[i][j];
            }
        }
     }
}

Einzelne Felder in Zeilen lösen

Nun gehen Sie vor, wie man ein Sudoku nun einmal löst: In einer ersten Methode soll Ihr Programm alle Zeilen durchlaufen. Wenn in einer Zeile nur ein Feld frei ist, kann dieses mit der einzigen Zahl, die in der Zeile bisher nicht vorkommt, gefüllt werden.

Im Prompt formulieren Sie als erstes Zwischenziel eine Schleife über alle Zeilen, fragen aber vorerst nur nach Vorschlägen für einen vernünftigen Namen der Methode.

Prompt: Perfect. Now we start the solving code. As a first step, I want to loop through the grid to find rows with exactly one empty cell. It should be easy to insert the missing value into these positions. I am unsure how to name this method. Do you have any ideas?

ChatGPT hat natürlich Ideen für den Namen und stellt gleich vier zur Wahl. Unaufgefordert liefert das KI-Tool auch gleich einen Code-Vorschlag, wobei es den Methodennamen fillSingleEmptyInRow verwendet.

Sie sehen sich den Code im Chat-System an und sind grundsätzlich zufrieden. Bevor Sie den Code in Ihr Programm übernehmen, haben Sie allerdings noch zwei Verbesserungswünsche, die Sie in den folgenden beiden Prompts ausdrücken. Zum einen sollen im Code aussagekräftigere Variablen verwendet werden (ChatGPT hat sich anfänglich für i und j entschieden), zum anderen soll die Methode einen Zähler integrieren und am Ende zurückgeben, wie viele Felder beim Durchlaufen der Schleife gelöst wurden.

Damit das KI-Tool nicht bei jeder Iteration den gesamten Code der Klasse ausgibt, bitten Sie darum, nur die gerade relevante Methode darzustellen. Beachten Sie, wie das KI-Tool ohne Zutun aus dem Kontext versteht, dass sich die zwei Prompts auf die vorherige Frage beziehen.

Prompt: Please replace i and j by row and column to make the code more clear.

Prompt: Add a counter to fillSingleEmptyInRow. The method should return the number of cells it has filled. Only output the changed method, not the entire class.

Die vollständig vom KI-Tool programmierte Methode sieht jetzt so aus:

public int fillSingleEmptyInRow() {
    int cellsFilled = 0;
    for (int row = 0; row < 9; row++) {
        int emptyCount = 0;
        int emptyColumn = -1;

        for (int column = 0; column < 9; column++) {
            if (grid[row][column] == 0) {
                emptyCount++;
                emptyColumn = column;
            }
        }
        if (emptyCount == 1) {
            boolean[] present = new boolean[10];
            for (int column = 0; column < 9; column++) {
                present[grid[row][column]] = true;
            }
            for (int number = 1; number <= 9; number++) {
                if (!present[number]) {
                    grid[row][emptyColumn] = number;
                    cellsFilled++;
                    break;
                }
            }
        }
    }
    return cellsFilled;
}

(explanation of changes …)

Einzelne Felder auch in Spalten und in Blöcken lösen

Sie bauen die vom KI-Tool vorgeschlagene Methode in Ihr Programm ein und testen diese. Nachdem alles zufriedenstellend funktioniert, bitten Sie ChatGPT, zwei äquivalente Methoden für Spalten sowie für 3×3-Blöcke zu schreiben.

Weil Sie in der Zwischenzeit ein paar kleinere Änderungen an der Klasse durchgeführt haben, übergeben Sie den gesamten Code der Klasse im aktuellen Zustand in den Prompt, sodass das KI-Tool über die richtige Ausgangsbasis verfügt. (Diesen Schritt ersparen Sie sich, wenn Sie einen in den Editor oder in die Entwicklungsumgebung integrierten KI-Assistenten verwenden.)

Prompt: I reorganized the code a bit. This is what the class looks like now. Please provide two more methods similar to fillSingleEmptyInRow to handle columns with only one cell missing and 3×3 areas with only one cell missing.

(Code der gesamte Sudoku-Klasse zum jetzigen Zeitpunkt, ca. 50 Zeilen)

Der Code der beiden neuen Methoden sieht ganz ähnlich aus wie fillSingleEmptyInRow. Sie integrieren die beiden Methoden in Ihren Code.

Test-Code und Probleme mit den Test-Daten

Um das Testen und Debugging einfacher zu machen, fordern Sie ChatGPT auf, zwei weitere Methoden zu programmieren. Die eine soll die Anzahl der noch ungelösten Felder zählen, die andere das Sudoku in gut lesbarer Form ausgeben.

Prompt: Please provide code for two more methods for the Sudoku class: One is to count the empty cells, the other one prints the Sudoku with empty spaces instead of 0.

Sie bauen den weitgehend trivialen Code dieser Methoden in Ihr Projekt ein. Wir haben den Code hier nicht abgedruckt. Werfen Sie gegebenenfalls einen Blick in die Beispieldateien zum Buch.

Der bisher von ChatGPT gelieferte Code war fehlerfrei. Allerdings haben Sie Probleme mit den Testdaten. Das am Beginn der Session von ChatGPT generierte Beispiel-Sudoku ist für Ihr Programm in der aktuellen Ausbaustufe zu schwierig. Also erbitten Sie einfachere Testdaten. Sie weisen im Prompt explizit darauf hin, dass Sie nur den Code für das Array brauchen (einmal ungelöst, einmal gelöst). Andernfalls gibt ChatGPT den gesamten Code der Main-Klasse neu aus.

Prompt: I added calls to the two new methods to my solve method. However, the test puzzle you provided is too difficult at this time. Can you provide a slightly easier puzzle for testing? (Provide just the int[][] array and the solved puzzle for reference, no other code.)

Tests mit dem neuen Sudoku sind ebenso erfolglos wie mit den ursprünglichen Testdaten. Sie brauchen ein Sudoku, in dem es zumindest eine Zeile, eine Spalte oder einen Block gibt, in dem nur eine Zahl fehlt. Sie formulieren diese Information in einem weiteren Prompt.

Prompt: Still easier please. We need at least one row, column and block with only one cell missing to test the code so far.

Absurderweise scheitert ChatGPT auch im dritten Anlauf, ein ausreichend einfaches Sudoku-Rätsel zu liefern. Auch gut, Sie nehmen ein vollständig gelöstes Sudoku und ersetzen selbst diverse Zellen durch 0 im Sinne von »nicht ausgefüllt« und führen Ihre Tests damit fort.

Ideenfindung

Damit gelangen Sie an den Punkt, wo Ihr Programm zwar prinzipiell funktioniert, aber eben nur für sehr einfache Sudokus. Jetzt wissen Sie nicht mehr so recht weiter. Sie fragen ChatGPT um Rat. Damit das KI-System eine Vorstellung hat, wie Ihre Lösungsmethode aktuell aussieht (diesen Code mit Aufrufen aller anderen Methoden haben Sie selbst verfasst), übergeben Sie diese Methode mit an den Prompt. Alternativ könnten Sie dem Prompt per Drag-and-drop die Datei der ganzen Klasse hinzufügen. Im Prompt bitten Sie explizit nicht um neuen Code, sondern um Ideen, wie Sie das Programm jetzt weiter verbessern könnten.

Prompt: I added a loop to my solve method. It calls all three fillSingleXxx methods until they are unable to solve a single cell.

// in der Klasse Sudoku
public boolean solve() {
    int n;
    do {
        n = 0;
        n += fillSingleEmptyInRow();
        n += fillSingleEmptyInColumn();
        n += fillSingleEmptyInBlock();
        System.out.println("Filled " + n + " cells.");
    } while (n > 0);
    if (countEmptyCells()==0) {
        System.out.println("Sudoku puzzle solved!");
        return true;
    }
    System.out.println("Could not solve the puzzle.");
    printSudokuWithSpaces();
    return false;
}

So far my program can solve only very simple Sudokus. Can you suggest a more sophisticated solution method? Just present the idea, no code please.

ChatGPT präsentiert nun einerseits gängige Lösungskonzepte für Sudokus (Naked Pairs/Triples, Hidden Pairs/Triples, X-Wing usw.) und schlägt andererseits einen rekursiven Backtracking-Algorithmus vor. Sie lassen sich zunächst einmal das Konzept von Naked Pairs/Triples erklären.

Prompt: Let’s start with Naked Pairs/Triples. Can you show me a Sudoku that can be solved with this concept so I can better understand the idea?

Speicherung der Lösungskandiaten pro Feld

ChatGPT erklärt das Konzept, wie der Umstand ausgenutzt wird, dass bei einem Paar freier Zellen nur noch ganz wenige Zahlen infrage kommen und auf diese Weise die Möglichkeiten weiter reduziert werden. Das bringt Sie auf eine neue Idee: Wäre es nicht sinnvoll, generell für jede Zelle zu speichern, welche Zahlen dort überhaupt noch zulässig sind? Diese Information würde jede weitere Lösungssuche beschleunigen.

Im Prompt formulieren Sie diese Idee. Ihre Frage bezieht sich dabei nur auf eine geeignete Datenstruktur. Natürlich könnten Sie einfach ChatGPT um einen Vorschlag bitten. Aber Sie wollen ja selbstständig programmieren lernen und machen sich stattdessen selbst Gedanken. Das KI-Tool dient hier mehr zur Verifikation Ihrer Ideen.

Prompt: I want to add an instance variable with 9x9 sets to store candidates for each cell. I want each set to be initialized with a set of all numbers from 1 to 9. Is

private Set<Integer>[][] candidates;

the correct data type? Later, I will add a method to remove all numbers already used within the same row, column, or 3×3 block.

ChatGPT bestätigt, dass der Datentyp eine gute Wahl ist, und steuert ungefragt auch den Code zur anfänglichen Initialisierung bei. Dabei wird jedes Set mit allen neun Zahlen initialisiert. Sie bauen die Änderungen ein und geben dann die nächste Methode in Auftrag.

Im Prompt erklären Sie, was die Methode machen soll: Sie soll alle 81 Felder des Sudokus durchlaufen und aus dem Set der möglichen Lösungen für dieses Feld alle Ziffern eliminieren, die in dieser Zeile, in dieser Spalte oder in diesem Block bereits vorkommen. Damit bleiben nur die Lösungskandidaten übrig. Die manuelle Programmierung dieser Methode wäre nicht besonders schwierig, aber wegen vieler ineinander verschachtelter Schleifen mühsam und fehleranfällig.

Prompt: Next, I need a method to loop over all the cells. For each cell, remove entries from the candidate set if the same number is used within the row, column, or 3×3 block. Can you provide code to do this?

Sie bauen die neue Methode updateCandidates ein und rufen diese nach den drei fillSingleXxx-Methoden auf. Mit anderen Worten: Zuerst versucht der Lösungsalgorithmus, Zeilen, Spalten oder 3×3-Blöcke mit nur einer freien Zelle zu finden. Danach eliminiert updateCandidates alle bereits in einer Zeile, Spalte oder im 3×3-Block genutzten Zahlen aus dem Set der Lösungskandidaten. Wenn es jetzt eine Zelle gibt, für die nur noch ein Lösungskandidat infrage kommt, ist wieder ein Feld des Sudokus gelöst.

Felder ausfüllen, bei denen nur eine Lösungszahl möglich ist

Im nächsten Prompt bitten Sie Ihren KI-Junior-Programmierer, eine weitere Methode zu programmieren, die genau nach solchen Feldern sucht und dort die Lösungszahl einträgt. Wie bisher soll die Methode mitzählen, wie viele Felder auf diese Weise gelöst werden.

Prompt: Could you write a method to loop over all the cells that are still empty. If the candidate set contains exactly one number, set that cell accordingly. Again, the method should return the number of cells solved.

Sie bauen die neue Methode in die Schleife zum Lösen von Sudokus ein – und siehe da: Das Programm kann jetzt selbst mittelschwere Rätsel lösen. An dieser Stelle sind Sie mit Ihrer Arbeit und den KI-Beiträgen zufrieden und schließen das Projekt vorerst ab. Die Sudoku-Klasse hat inzwischen einen Umfang von knapp 300 Zeilen. (Sie finden den kompletten Code in den Beispieldateien zum Buch.)

Persönliches Fazit

Ich muss vorausschicken, dass ich schon vor einigen Jahren – ohne KI-Hilfe – in der Sprache Kotlin einen Sudoku-Solver programmiert habe. Bis zu dem hier skizzierten Zustand des Programms hat mich das etwa zwei Tage Zeit gekostet. Mir hat die Programmierung damals Spaß gemacht, gerade auch die Recherche über verschiedene Sudoku-Lösungsstrategien. Im Anschluss habe ich noch ein, zwei weitere Methoden hinzugefügt und schließlich einen rekursiven Suchalgorithmus implementiert. Zeitaufwand ungefähr weitere zwei Tage:

https://kofler.info/sudokus-mit-kotlin-loesen

Als ich dieses Beispiel gestartet habe, hatte ich also schon etwas Vorwissen. Trotzdem war es verblüffend, dass ich mit KI-Hilfe nach zwei Stunden in etwa so weit war wie bei meinem ersten Versuch nach zwei Tagen!

Was mir an diesem Beispiel am besten gefällt: Auch bei dieser Neuimplementierung habe ich das Gefühl, dass das mein Code ist. Sicher, dank KI-Hilfe habe ich mir das öde Ausformulieren der verschachtelten Schleifen erspart. Das ist nicht schwierig, aber fehleranfällig. Aber der KI-generierte Code ist für mich klar verständlich, ich hätte ihn an jeder Stelle ändern oder bei Bedarf korrigieren können. (Letzeres war nicht notwendig. Der von ChatGPT 4o generierte Code war fehlerfrei.)

Warum hat es so gut funktioniert? Einerseits weil es im Netz diverse Sudoku-Solver gibt, weil es zum Training des Sprachmodells also genug Material gab. Andererseits weil mein eigenes Wissen relativ hoch war. Ich habe die Richtung der Code-Entwicklung vorgegeben, und ich konnte bei jeder neuen Methode – nahezu mit einem Blick – sicherstellen, dass der Code sinnvoll und korrekt ist.

Und genau da sehe ich die Idealvoraussetzungen für den KI-Einsatz beim Coding: Sie wissen, was Sie tun, und sind von der Komplexität des KI-generierten Codes nicht überfordert. Sie können mühelos abschätzen, ob der Code funktioniert.

Zugegebenermaßen treffen diese Voraussetzungen nicht zu, wenn Sie gerade erst dabei sind, programmieren zu lernen. Dann ist die Lösung typischer Übungsaufgaben sehr wohl eine große Herausforderung. Im Idealfall können Sie auch dann anhand der KI-Vorschläge lernen. Allerdings brauchen Sie dann viel Selbstdisziplin: Nur wenn Sie Teilprobleme zuerst selbst lösen, nur wenn Sie den vom KI-Tool gelieferten Code so lange hinterfragen, bis Sie ihn im Detail verstanden haben, wird Ihr Coding-Wissen wachsen.

Alternative Vorgehensweise

Bei diesem Beispiel haben wir relativ klar vorgegeben, welche Strategien zum Lösen des Sudokus genutzt werden sollen. Wir haben dabei einen sehr »menschlichen« Ansatz gewählt und per Code umgesetzt, wie wir selbst ein Sudoku lösen würden.

Wie der folgende Prompt zeigt, besteht eine Alternative darin, den Lösungsweg vollkommen dem KI-Tool zu überlassen. Der eigene Beitrag am Code sinkt damit aber auf null.

Prompt: Can you show me a short, concise way to solve a Sudoku with Java?

Die meisten KI-Tools schlagen dann den Backtracking-Algorithmus vor. Das ist eine Vorgehensweise, die im Prinzip so funktioniert: In jede freie Zelle werden der Reihe nach die Zahlen 1, 2, 3 bis 9 eingesetzt. Sobald eine Zahl keine offensichtlichen Fehler verursacht (keine Doppelgänger in der Zeile, Spalte oder im 3×3-Block), setzt die Methode diese Vorgehensweise bei der nächsten freien Zelle fort. Sollte dort keine der Zahlen 1 bis 9 passen, wurde offensichtlich früher ein Fehler gemacht. Die Methode bricht an dieser Stelle ab, geht zum vorigen Feld zurück und setzt dort die nächste Zahl ein.

Der Backtracking-Algorithmus ist rekursiv, basiert also darauf, dass sich eine Methode immer wieder selbst aufrufen kann. Der rekursive Ansatz hat den Vorteil, dass es bei Fehlern einfach ist, zu einer früheren Phase der Lösungssuche zurückzukehren. Daher stammt auch der Name dieses Konzepts.

Diese Vorgehensweise ist allerdings vollkommen »unmenschlich«. Anstatt mit Feldern zu beginnen, wo es offensichtliche, einfache Lösungen gibt, probiert das Programm systematisch alle Möglichkeiten durch. Der rekursive Ansatz ist zudem nur sehr schwer zu verstehen, vor allem wenn Sie gerade erst dabei sind, programmieren zu lernen. Immerhin können Sie das KI-Tool bitten, Ihnen den Code zu erklären!

Prompt: Great! However, it is hard for me to understand the code. Could you add some comments to the code and explain the relevant concepts?

Der Code mit dem Backtracking-Algorithmus ist zwar schwer verständlich, hat dafür im Vergleich zur vorhin präsentierten Lösung zwei entscheidende Vorteile:

Richtig »prompten«

In diesem Buch geht es grundsätzlich nicht um die Lösung von Programmierproblemen, ganz egal, ob es sich nun um Sudokus, REST-APIs oder Datenbankanwendungen handelt. Vielmehr geht es darum, mit KI-Tools effizient und verantwortungsvoll umgehen zu lernen.

In diesem Abschnitt haben wir Ihnen gezeigt, wie Sie – aus unserer Sicht vernünftig – ein komplexes Problem mit KI-Hilfe lösen können. Als alternativen Ansatz haben wir aber auch demonstriert, dass Sie unter Umständen viel schneller ans Ziel kommen, wenn Sie die Möglichkeiten von KI-Tools hemmungslos einsetzen. (Nicht immer gelingt das so gut wie beim Sudoku-Lösen!)

Wir glauben, dass der zweite Weg der falsche ist: