Sudoku (EV3)
Diese Seite ist die Dokumentation des Projekts von Tim Ebert in der Q4 (2016) zum Thema Technische Informatik.
Inhaltsverzeichnis
Idee
Die Idee hinter meinem Projekt ist relativ simpel: Mein Roboter soll Sudokus lösen können.
Regeln des Sudokus
Ein Sudoku ist ein Rätsel, das aus 9x9 Feldern besteht, in die die Zahlen 1 bis 9 eingetragen werden müssen. Zu Beginn sind bereits einige Felder mit Zahlen gefüllt.
Beim Ausfüllen der Felder gibt es folgende Regeln:
- In jeder Reihe und jeder Spalte darf und muss jede Zahl nur genau 1x vorkommen.
- In jedem der 9 Unterquadrate (zu je 3x3 Feldern) darf und muss jede Zahl nur genau 1x vorkommen.
Genauere Vorstellungen
Da man einem Roboter nicht einfach ein Rätsel-Block mit Sudokus geben kann, die er lösen soll, werden hier Vereinbarungen für mein Projekt getroffen, sodass es für einen Roboter möglich wird, ein Sudoku zu lösen:
Übertragung auf eine maschinell lösbare Form:
- Anstatt der 9 verschiedenen Zahlen arbeitet der Roboter mit 9 verschiedenen Farben (Grautöne), die er mit Hilfe eines Farbsensors erkennen kann.
- Der Roboter arbeitet auf einem A4-Blatt, das unten in den Roboter an vorgegebener Stelle eingelegt wird.
- Auf dem Papier ist das 9x9 Sudoku-Feld enthalten und darunter eine Zeile mit allen 9 Zahlen mit hinterlegten Farben.
- Jeder Zahl ist genau eine Farbe zugeordnet (s. Bild). Die vorgegebenen Zahlen im Rätsel sind mit den Farben hinterlegt, die auch in der Farbreihe verwendet werden.
- Ansonsten gelten hier für den Roboter die gleichen Regeln wie beim klassischen Sudoku (s. oben) auch.
Der Ablauf:
- Mit Hilfe einer Vorlage erstellt man das Rätsel. Ausgedruckt wird es dann in den Roboter wie beschrieben eingelegt.
- Das Programm wird am Roboter gestartet.
- Der Roboter fährt in die Startposition zurück.
- Kalibrierung des Farbsensors mithilfe der Farbreihe.
- Das Sudokus wird mit dem Farbsensor eingelesen.
- Das eingelesene Sudoku wird mithilfe eines Backtracking-Algorithmus gelöst.
- Der Roboter gibt seine Lösung aus, indem er die leeren Zellen des Rätsels mithilfe des Stiftes ausfüllt.
Damit sind die notwendigen Vereinbarungen getroffen, die für das Projekt entscheidend sind. Die folgenden Abschnitte beschäftigen sich also mit der Umsetzung dieser Ideen und Vereinbarungen.
Bau des Roboters
Der Roboter fährt auf zwei Zahnradschienen vertikal über das beschriebene Spielfeld (x-Achse). Damit er sich auch in die horizontale Richtung bewegen kann, befinden sich auf der "Verbindungsbrücke" weitere Schienen (y-Achse). Der Stift und der Farbsensor, die an einem gemeinsamen Gestell befestigt sind, können sich hoch und runter bewegen und bilden somit die "z-Achse". Alle Achsen verfügen an einem Ende einen Taster, der die Nullposition bestimmt. Zu Beginn fährt der Roboter auf jeder Achse so lange zurück, bis der Taster gedrückt wird. Dadurch kann er bei jedem Start in genau die selbe Position fahren. Durch die Gradzahlmesser an den Motoren, die die Position der Achsen bestimmen, kann man jede Achse zu einer gradgenauen Position bewegen. Somit kann der Roboter sich mit einer hohen Genauigkeit über dem Spielfeld bewegen, um die Zahlen exakt in die Mitte der Zellen zu schreiben.
- Fehler beim Erstellen des Vorschaubildes: Datei mit Abmessungen größer als 12,5 MP
x-Achse
- Fehler beim Erstellen des Vorschaubildes: Datei mit Abmessungen größer als 12,5 MP
Taster an der x-Achse
- Fehler beim Erstellen des Vorschaubildes: Datei mit Abmessungen größer als 12,5 MP
y-Achse
- Fehler beim Erstellen des Vorschaubildes: Datei mit Abmessungen größer als 12,5 MP
Stift und Farbsensor
Programmierung
Den gesamten Quellcode meines Roboters könnt ihr hier herunterladen.
Das Programm enthält insgesamt 7 Klassen:
- SudokuRobot: Hauptklasse mit der main-Methode
- Motor: Klasse für den einfachen Zugriff auf die Motorfunktionen
- TouchSensor: Klasse für den einfachen Zugriff auf die Funktionen der Taster
- Axis: Klasse dient als Modell für eine Achse aus Motor und TouchSensor
- ColorSensor: Klasse für den einfachen Zugriff auf die Funktionen des Farbsensors und die Erkennung der Zahlen
- Pencil: Unterklasse von Axis für die Achse mit dem Stift und dem Farbsensor
- ButtonObserver: Beobachter eines Knopfes am EV3 für den Korrekturmodus
Dies sind die wichtigsten Dinge im gesamten Programm-Paket:
(Die folgenden Methoden und Funktionen enthalten nur die wichtigsten Aufrufe und sind zum besseren Verständnis vereinfacht. Der vollständige Quellcode steht hier zum Download bereit.)
SudokuRobot
- main(String[] args): Hauptmethode, Start des Programms
- start(): ruft nacheinander Methoden auf; enthält das eigentliche Programm
- int[][] sudoku: zweidimensionales Feld; dient als Speicher des Rätsels
Axis.moveToPosition()
Die Klasse Axis modelliert eine Achse aus Motor und Berührungssensor am Ende der Zahnradschiene. Diese Funktion bewegt die Achse zur gewünschten Position. Die Position einer Achse wird durch den Gradzahlmesser am zugehörigen Motor bestimmt. Beim ersten Aufruf mit dem Parameter 0, fährt die Achse solange zurück, bis der zugehörige Berührungssensor gedrückt wird. So wird die 0-Position festgelegt und der Gradzahlmesser ("TachoCount") des Motors zurückgesetzt. Bei weiteren Aufrufen mit newPosition > 0, wird die Klassen-Variable Position solange aktualisiert, bis sie nicht mehr größer/kleiner newPosition ist.
private void moveToPosition(int newPosition){
if(newPosition == 0){
isMoving = true;
motor.backward();
while(!touchSensor.isPressed())
Delay.msDelay(10);
motor.stop();
motor.resetTachoCount();
position = Math.abs(motor.getTachoCount());
isMoving = false;
}else if(position > -1){
isMoving = true;
if(position < newPosition){
motor.forward();
while(position < newPosition && position < maxPosition){
position = Math.abs(motor.getTachoCount());
Delay.nsDelay(10);
}
motor.stop();
}else if(position > newPosition){
motor.backward();
while(position > newPosition && position > 0 && !touchSensor.isPressed()){
position = Math.abs(motor.getTachoCount());
Delay.nsDelay(10);
}
motor.stop();
if(touchSensor.isPressed()){
position = 0;
}
}
isMoving = false;
}
}
ColorSensor.readNumber()
Beim Aufruf der Methode ColorSensor.calibrate() werden im globalen Feld colors[] der Länge 10 die Messwerte des Farbsensors für alle Zahlen (weiß, 1, 2, ..., 9) gespeichert. Die Methode readNumber() kann dann aus diesem Feld auslesen welche Zahl gerade unter dem Farbsensor liegt. Es sucht im Feld solange, bis der aktuelle Messwert value größer als der Wert in colors ist. Dann wird ein Schwellenwert in der Mitte der letzten und der aktuellen Zahl in colors berechnet und danach entschieden, welche Zahl vorliegt.
public int readNumber(){
if(colors == null) throw new IllegalStateException("ColorSensor not calibrated.");
float value = getValue();
for(int index = 0; index < colors.length; index++){
if(value == colors[index]){
return index;
}else if(value > colors[index]){
if(index == 0) return index;
else{
float major = colors[index - 1], minor = colors[index];
float threshold = minor + (major - minor)/2f;
if(value > threshold) return index - 1;
else return index;
}
}
}
if(value < colors[colors.length-1]) return colors.length-1;
else return -1;
}
SudokuRobot.searchSolution()
Diese Methode löst das Sudoku. Sie basiert auf einer Rekursion ausgehend vom Aufruf searchSolution(0, 0). Als erstes werden die Indizes für den nächsten rekursiven Aufruf berechnet. Wenn sudoku[x][y] größer als 0 ist, steht hier eine bereits gegebene Zahl. Dann wird direkt der Wert des rekursiven Aufrufs zurückgegeben. Ansonsten muss für dieses Feld noch eine passende Zahl gefunden werden. Dies realisiert die for-Schleife. Als erstes wird sudoku[x][y] auf -i gesetzt. Das negative Vorzeichen ist hier der Indikator für eine nicht gegebene Zahl, von der man noch nicht weiß, ob sie richtig ist. Mit isCellValid(x+1, y+1) wird überprüft, ob in der aktuellen Zelle eine richtige Zahl steht. Ist das der Fall, wird der nächste Aufruf der Funktion searchSolution() getätigt. Wenn dieser true zurückgibt, wird auch hier true zurückgegeben. Findet die Methode innerhalb der for-Schleife jedoch keine richtige Zahl, bei der der rekursive Aufruf auch true zurückgibt, wird die aktuelle Zelle wieder auf 0 gesetzt (sudoku[x][y] = 0) und false zurückgegeben, damit in der letzten Zelle die nächste mögliche Zahl ausprobiert wird. Kann die Methode gar keine Lösung für das gegebene Sudoku finden, wird am Ende false zurückgegeben. if(x == 8 && y == 8) dient hier als Rekursionsabbruch (8|8 sind die Indizes der letzten Zelle). Wird hier nämlich eine richtige Zahl gefunden, ist das Sudoku vollständig gelöst.
private boolean searchSolution(int x, int y){
int nextX = x, nextY = y + 1;
if(nextY > 8){
nextX++;
nextY = 0;
}
if(sudoku[x][y] > 0){
if(x == 8 && y == 8) return true;
else return searchSolution(nextX, nextY);
}
for(int i = 1; i <= 9; i++){
sudoku[x][y] = -i;
if(isCellValid(x+1, y+1)){
if(x == 8 && y == 8) return true;
if(searchSolution(nextX, nextY)) return true;
}
}
sudoku[x][y] = 0;
return false;
}
SudokuRobot.drawNumber()
Diese Methode füllt mithilfe des Stiftes die Zelle unter dem Stift mit der gewünschten Zahl (digitale Zahlenschreibweise). Zuerst wird wird anhand des Arguments festgestellt, in welcher Position der Stift starten soll (bei der 2 z. B. oben links). Der Stift wird in diese Position gebracht und wird angesetzt. In der großen switch-Anweisung gibt es für jede Zahl eine eigene Abfolge zum Schreiben. Mit den Strichlängen sX und sY werden die beiden Achsen immer so verschoben, wie die Zahlen gezeichnet werden sollten.
private void drawNumber(int number){
if(number < 1 || number > 9) return;
int previousX = axisX.getPosition(), previousY = axisY.getPosition();
final int sX = 180, sY = 90;
pencil.setWriting(false);
if(number == 2 || number == 3 || number == 4 || number == 7 || number == 8){
//Oben links anfangen
axisX.increasePosition(sX, false);
axisY.increasePosition(-sY/2, false);
}else if(number == 1 || number == 5 || number == 6) {
//Oben rechts anfangen
axisX.increasePosition(sX, false);
axisY.increasePosition(sY/2, false);
}else{
//In der Mitte rechts anfangen
axisY.increasePosition(sY/2, false);
}
while(axisX.isMoving() || axisY.isMoving())
Delay.msDelay(100);
pencil.setWriting(true);
switch(number){
case 1:
axisX.increasePosition(-2*sX, true);
break;
case 2:
axisY.increasePosition(sY, true);
axisX.increasePosition(-sX, true);
axisY.increasePosition(-sY, true);
axisX.increasePosition(-sX, true);
axisY.increasePosition(sY, true);
break;
//...
}
pencil.setWriting(false);
}
Probleme
Während dem Bau und der Programmierung des Roboters sind bei mir unter anderem folgende Problem bzw. Schwierigkeiten aufgetreten.
- Der Bau des Roboters selbst, war für mich persönlich die größte Herausforderung, da ich nicht so einfach ohne Bauanleitung drauf los bauen konnte. Als Inspiration hatte ich trotzdem ein Video von einem NXT-Roboter, der Schach spielen kann.
- Der Abruf der Sensor-Funktionen und auch die Nutzung der Motoren erschien mir im lejosj-API etwas zu kompliziert, weshalb ich die Klassen TouchSensor, ColorSensor und Motor geschrieben habe, die das ganze erleichtern sollten. Generell ist lejos nicht gerade sehr ausgereift und teils sehr verwirrend gestaltet. Als Hilfe habe ich immer wieder die Dokumentation des APIs herangezogen, aber auch die war an manchen Stellen nicht ganz leicht verständlich. Es hat eine Weile gedauert, bis ich mit lejos zurecht kam, aber als ich erstmal die beschriebenen Unterklassen erstellt hatte, war das Programmieren kein Problem mehr.
- Die Übersetzung des Motor auf der x-Achse war zu Beginn so groß, dass der Roboter sich mit einer Umdrehung des Motors über die gesamte Achse bewegen konnte. Mit einer veränderten Übersetzung auf allen Achsen habe ich dieses Problem behoben und der Roboter kann nun bis auf mindestens 5mm genau positioniert werden.
- Zur Erkennung der Zahlen wollte ich zuerst die vorgegebenen Zahlen im Rätsel bunt hinterlegen. Beim Testen bekam ich das Problem, dass der Farbsensor nur 4 von 9 Farben über den ColorID-Modus erkannt hat. Später habe ich den Red-Modus des Farbsensors entdeckt. Mit diesem misst der Sensor die reflektierte Strahlung des roten Lichtes. Mithilfe dieses Modi kann der Roboter nun die Grautöne, die sich eigentlich nur sehr gering unterscheiden, erkennen und diese eindeutig den Zahlen zuordnen. Da die Messwerte aber nicht allgemeingültig sind und von verschiedenen Faktoren wie dem Abstand zum Papier, der Umgebungshelligkeit usw. abhängen, habe ich auf dem Papier unter dem Sudoku-Rätsel die Farbreihe hinzugefügt. Wenn der Roboter zu Beginn der Ausführung über diese Farbreihe fährt und die Farben zur Kalibrierung einließt, wird die Farb-Zahlen-Zuordnung deutlich zuverlässiger.
- Da auch diese Methode noch nicht 100-prozentig funktionierte, weil der Farbsensor bereits auf kleine Unterschiede in der Distanz zum Papier sehr empfindlich reagierte, wollte ich sicher gehen, dass das Rätsel auf jeden Fall richtig eingelesen wird. Deshalb habe ich die Möglichkeit hinzugefügt, dass der Beobachter die eingelesenen Zahlen korrigieren kann. Nachdem das gesamte Sudoku eingelesen wurde, kann man die Zahlen mit den Tasten des EV3s korrigieren.
