Erstellen Sie eine Turing Maschine, die das n-Damen Problem löst. Das Problem ist wie folgt definiert:
Wie können auf einem n x n Schachbrett n Damen plaziert werden, so dass sie sich paarweise nicht angreifen können?

Ausgangslage

Der Rand des Schachbretts ist durch #-Symbole markiert und der Lese/Schreibkopf befindet sich auf der Dame ("1") am weitesten rechts.
Die Damen erfüllen dabei zwei Kriterien:


mögliche Ausgangslagen

Schlussbedingungen

Ausgehend von der Startkonfiguration findet die Turing Maschine die nächste gültig Lösung.

Falls es keine mögliche Anordnung der Damen gibt, stoppt die Turing Maschine auf dem leeren Schachbrett.