Hallo Zusammen

Ich hatte in den letzten Wochen eine Klasse geschrieben und dachte ich teile Sie mit euch.
Hiermit lassen sich Sudokurätsel lösen / generieren und man kann die Klasse auch als Gameengine verwenden.
Feedback ist natürlich Willkommen.

Ihr findet die App mit einem kleinen solve.Sudoku Frontend, Dokumentation* und Sourcecode* unter http://23g.eu/sudoku/



Vielleicht kann daraus der ein oder andere lernen oder ich durch nützliches Feedback.

Liebe Grüße
addi

p.s. arbeite derzeit an einer "Schachengine" - da gibts dann auch demnächst coding sugar

Ich habe bei dir einfach mal in den ersten beiden Zellen links oben die eins und die zwei eingegeben. Dein Programm ist daran leider gescheitert und sagt mir, daß es keine Lösung gibt.

Mein eigener Sudoku-Löser gibt mir aber folgende Lösung aus:

...........
.127495368.
.893726154.
.546318297.
.389271546.
.764583921.
.251649783.
.972834615.
.638152479.
.415967832.
...........

-Thomas

_________________
"Programs must be written for people to read, and only incidentally
for machines to execute."
- H. Abelson and G. Sussman
(in "The Structure and Interpretation of Computer Programs)

hallo ?! dein sudokurätsel war nicht eindeutig lösbar. klar findet er dann keine eindeutige lösung. zahlen einsetzen kann jeder, aber es geht da auch um performance und logik

nimm ein expertensudokurätsel aus ner zeitschrift oder was weiß ich und es wird gelöst. das einzige wo es scheitert ist, wenn es keine eindeutige lösung gibt.

desweiteren ist die klasse nicht nur um ein sudoku zu lösen, sondern eine engine es kann auch rätsel generieren ect.

aber nett das du es ausprobiert hast

lg addi

edit: sollte jetzt nicht unfreundlich wirken

@ri hast du deinen sudokulöser den irgendwo veröffentlicht und mit welchen lösungsalgorythmen versuchst du ein sudoku zu lösen? ich meine es gibt das einsetzungsverfahren mit undo ect. mi rpersönlich ging es um effektivität, deswegen werden auch die schritte gezählt, wie viele er gebraucht hat ect. meine erste lösung hat für ein sudokurätsel (experten) ca. 30 sekunden gebraucht. diese version konnte das gleiche rätsel innerhalb von unter einer sekunde lösen, was viel effektiver und effizienter war.

von eindeutig lösbar stand aber bei deinem Ergebnis nichts, nur daß es nicht lösbar sei. Mein Sudoku-Löser sucht halt nach einer beliebigen Lösung für ein veröffentlichtes Sudoku. Ob es mehrere Lösungen gibt, ist mir dann z.B. beim Einsenden einer Lösung zu einem Gewinnspiel eigentlich egal.



hab' ich jetzt auch nicht so aufgefasst

-Thomas

_________________
"Programs must be written for people to read, and only incidentally
for machines to execute."
- H. Abelson and G. Sussman
(in "The Structure and Interpretation of Computer Programs)

Nein, bis jetzt noch nicht veröffentlicht. Mein Ansatz ist eigentlich recht trivial: Die Lösungsmethode bekommt ein Spielfeld mit teilweise belegten Zellen übergeben. Dann wird das erste freie Feld der Reihe nach mit 1 bis 9 belegt. Dann wird gecheckt, ob dadurch Ziffern mehrfach vorkommen. Falls ja, wird die Lösung nicht weiter verfolgt und mit der nächsten Ziffer weitergemacht. Falls es keine doppelten Ziffern gibt wird die Lösungsmethode rekursiv mit dem aktuellen Spielfeld wieder aufgerufen. Irgendwann ist die Matrix vollständig belegt, dann liegt eine Lösung vor.

-Thomas

_________________
"Programs must be written for people to read, and only incidentally
for machines to execute."
- H. Abelson and G. Sussman
(in "The Structure and Interpretation of Computer Programs)

Ohne den Spass verderben zu wollen (mehr, um Anregungen zu geben): Dieses Problem lässt sich sehr effizient mit einem Constraint Solver beschreiben und lösen. In dem lassen sich schnell 4 Bedingungen ausdrücken:

* Alle Spalten der Gesamtmatrix enthalten nur unterschiedliche Ziffern
* Alle Zeilen der Gesamtmatrix enthalten nur unterschiedliche Ziffern
* Jede Submatrix enthält nur unterschiedliche Zahlen
* Vorbelegte Zellen (im Constraint-Sprech "Variablen") dürfen ihren Wert nicht ändern

Natürlich nimmt einem das den Spass, die Constraint-Auflösung selbst zu programmieren . Kurz gesagt wird der Solver dann den gesamten Lösungsraum effizient durchlaufen und die erste oder alle Lösungen ausgeben.

Ich wollte eigentlich ein Beispiel programmieren, aber es gibt einen guten Solver in Ruby, der auch noch ein gutes Beispiel mitbringt:

require 'rubygems'
require 'gecoder'
require 'enumerator'

# Solves the sudoku problem: http://en.wikipedia.org/wiki/Soduko

# The sudoku we want to solve (0 represents that the square is empty).
sudoku = Matrix[
[0,0,0, 2,0,5, 0,0,0],
[0,9,0, 0,0,0, 7,3,0],
[0,0,2, 0,0,9, 0,6,0],

[2,0,0, 0,0,0, 4,0,9],
[0,0,0, 0,7,0, 0,0,0],
[6,0,9, 0,0,0, 0,0,1],

[0,8,0, 4,0,0, 1,0,0],
[0,6,3, 0,0,0, 0,8,0],
[0,0,0, 6,0,8, 0,0,0]]

solution = Gecode.solve do
# Verify that the input is of a valid size.
n = sudoku.row_size
sub_matrix_size = Math.sqrt(n).round
unless sudoku.square? and sub_matrix_size**2 == n
raise ArgumentError, 'Incorrect value matrix size.'
end
sub_count = sub_matrix_size

# Create the squares and initialize them.
squares_is_an int_var_matrix(n, n, 1..n)
sudoku.row_size.times do |i|
sudoku.column_size.times do |j|
squares[i,j].must == sudoku[i,j] unless sudoku[i,j] == 0
end
end

# Constraints.
n.times do |i|
# All rows must contain distinct numbers.
squares.row(i).must_be.distinct(:strength => :domain)
# All columns must contain distinct numbers.
squares.column(i).must_be.distinct(:strength => :domain)
# All sub-matrices must contain distinct numbers.
squares.minor(
(i % sub_count) * sub_matrix_size,
sub_matrix_size,
(i / sub_count) * sub_matrix_size,
sub_matrix_size).must_be.distinct(:strength => :domain)
end

# Branching, we use first-fail heuristic.
branch_on squares, :variable => :smallest_size, :value => :min
end.squares.values

# Output the solved sudoku in a grid.
puts solution.enum_slice(sudoku.row_size).map{ |slice| slice.join(' ') }.join($/)

Achtung, läuft nur unter Ruby 1.8 und benötigt:

gem install gecoder-with-gecode

Gruß,
Skade

@skade danke dir. werde ich mir mal näher anschauen. das ist mir tatsächlich neu

@thomas finde ich interessant. ich mein rekursiv nach Lösungen zu suchen ist die sichere variante. mein ziel (okay ich hab es nirgendwo nieder geschrieben) war es auf Rekursion zu verzichten und eine Lösung mithilfe von so wenig Schritten wie möglich zu finden.
Es gibt dort im Prinzip 3 Stufen zur Lösung eines Feldes.
1. Ein Feld hat nur eine Möglichkeit
2. Für ein Feld existiert eine Möglichkeit die in einer Zeile/Spalte/Block sonst nicht existiert
3. In den Umliegenden Blöcken wurde eine bestimmte Zahl eingetragen, die in dieses Feld eingesetzt werden kann.
Ich müsste diese Lösungsansätze noch Verbessern:
a. Es sollte auch möglich sein eine Lösung einer logische Kombination aus 2. und 3. zu generieren
b. Bei nicht Eindeutigkeit sollte eine variante eingesetzt werden um das sudoku zu lösen (z.B. bei diesem Rätsel hier)
c. Um mehr effizienz zu erreichen sollte es möglich sein, dass die einzelnen Felder über einen Stack eine Lösungsreihenfolge generiert, die die Hauptschleife beeinflusst.

Übrigens ist es so gehalten, dass ein einzelnes Feld ein Objekt ist, welches mit anderen Feldern verbunden ist. Diese werden von einem anderen Objekt (dem Sudokuspielfeld im prinzip) generiert. Ich arbeite mit caching über timestamps und arrays um die geschwindigkeit zu erhöhen.

lg addi

Na, dann hätte mir das eh' nichts genutzt. Woran liegt's? Weil dieses Gem nicht mit 1.9 läuft?

Aber davon abgesehen: Es macht halt einfach Spaß, selbst mal auszuprobieren, wie man beliebige Sudoku-Rätsel lösen lassen kann.

-Thomas

_________________
"Programs must be written for people to read, and only incidentally
for machines to execute."
- H. Abelson and G. Sussman
(in "The Structure and Interpretation of Computer Programs)

Rekursiv nach Lösungen zu suchen, mag auf den ersten Blick recht umständlich erscheinen, weil damit sozusagen ein Baum mit jeweils 9 Zweigen und einer Tiefe entsprechend der freien Felder aufgebaut wird. Wenn man sich die aktuelle Belegung der Felder zu Debug-Zwecken während der Lösungssuche anzeigen läßt, dann sieht man, daß maximal in etwa die Hälfte der Felder ausprobiert werden, bevor festgestellt wird, daß keine Lösungen möglich sind und diese Zweige "im Sande" verlaufen.
Bei einem Rätsel, daß in einer Zeitung als "schwierig" kategorisiert wurde, braucht mein Programm in der Größenordung um ca. 5 Sekunden - ohne jede Optimierung.

Gruß,
-Thomas

_________________
"Programs must be written for people to read, and only incidentally
for machines to execute."
- H. Abelson and G. Sussman
(in "The Structure and Interpretation of Computer Programs)

Nichts richtig großes. Fürs C++-Binding an die gecoder-Lib wird eine Bibliothek verwendet, die noch Doppelpunkte im case-statement verwendet. Das ist unter 1.9 illegal.



Wie gesagt, ich wollte nur mal zeigen, was für Ansätze man da fahren kann. Ich finde in der Hinsicht CLP (Constraint Logic Programming) sehr interessant und gerne ignoriert. Ich finds auch sehr interessant, dass in dem Programmierfeld zum Beispiel der Begriff einer Variable ein anderer ist.

Sich seinen Backtracker selbst zu schreiben (am Ende ist die Lösung hier ja auch rekursiv) ist _natürlich_ der große Spass an der Arbeit, davon will ich niemanden abhalten. Im übrigen, falls noch jemand ein interessantes Problem in der Richtung sucht: Labyrinth-Generatoren/Löser sind auch lustig.

Gruß,
Skade

Cool, ihr seid ja auch Rätsel-Freaks!

Ich beschäftige mich grade mit nem ähnlichen Programm - auch 9 Felder, 2 Spieler. Wisst ihr evtl., wie der auf die Codezeile 5 kommt bzw. die Formel?

Suag, sig.
--------------------------------------------------------------
...eine Methode, die uns ein bestimmtes Feld ausgibt. Schauen wir sie uns zunächst an.

01 # Methode, die ein bestimmtes Feld ausgibt. Entweder wird
02 # das Symbol für den Spieler ausgegeben, der das Feld besetzt hat,
03 # oder es wird die laufende Nummer des Feldes ausgegeben.
04 def print_feld(spalte, zeile, zuege)
05 feld = (spalte-1)*1 + (zeile-1)*3 + 1
06 for zug in zuege do
07 if zug[1] == spalte and zug[2] == zeile
08 feld = (zug[0] == ? "X" : "O")
09 break
10 end
11 end
12 print feld
13 end

Die Methode ist zwar kurz, aber es passiert hier eine Menge. Ich habe die Zeilen daher einmal nummeriert. Die Methode bekommt nun also die aktuelle Zeile und Spalte des Feldes, das sie ausgeben soll. Zusätzlich bekommt sie noch die Liste aller bisher gemachten Züge.
Die Methode muss nun folgendes machen:

Die laufende Nummer für das Feld berechnen.
Nachschauen, ob für das Feld bereits ein Zug existiert.
Wenn ein Zug existiert, feststellen, welcher Spieler ihn gemacht hat und dann die laufende Nummer mit dem entsprechenden Zeichen für den Spieler überschreiben.

Schauen wir uns zuerst die Berechnung der laufenden Nummer von 1 bis 9 an. Das passiert in Zeile 05 in obigem Code.

...
05 feld = (spalte-1)*1 + (zeile-1)*3 + 1
...

Die laufende Nummer wird durch eine mathematische Formel aus der Spalte und der Zeile bestimmt. Erforderlich ist dabei, dass die Zeilen und Spalten jeweils von 1 bis 3 von links nach rechts bzw. von oben nach unten gezählt werden. Wenn du nicht glaubst, dass das funktioniert, dann probier einfach alle Möglichkeiten für die Formel aus. Zum Beispiel, welche Nummer muss in Spalte 3 und Zeile 2 stehen (das Feld in der Mitte ganz rechts außen)?
-------------------------------------------------------------

_________________
Wir müssen umdenken ... (Helge-Film - Texas...)