Sudoku loesen / Mengenvariablen?

Servus!

Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
programmieren. Entscheidendes Problem ist zunächst einmal
das Datenmanagement. Ich würde gerne hierzu mit
Mengenvariablen arbeiten (IIRC ging das in Turbopascal).
Perl hat sowas ja nicht direkt. Man könnte es natürlich über
charakteristische Funtkionen simulieren. Sicherlich kann man
entsprechend auch Funktionen schreiben, um die gängigen
Mengenoperationen (Vereinigung, Durchschitt,
Mengesubstraktion) zu erreichen. Aber vielleicht gibt es das
ja schon in geeigneter Form (meine Google-Suche war
irgendwie nicht so prickelnd).

Völlig auf dem Schlauch stehe ich noch beim User-Interface.
Irgendwer Ideen und Lust, das gemeinsam zu machen?

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger schrieb:
> Servus!
>
> Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
> programmieren. (...).
>
> Völlig auf dem Schlauch stehe ich noch beim User-Interface.
> Irgendwer Ideen und Lust, das gemeinsam zu machen?

Hallo Boris,

http://www.behrenhoff.de/sudoku.exe

Den Source (Delphi) sende ich gerne zu, wenn du ihn haben willst. Und
ja, ich habe auch Sets verwendet.

Wolf

Re: Sudoku loesen / Mengenvariablen?

Wolf Behrenhoff wrote:

>> Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
>> programmieren. (...).
>>=20
>> Völlig auf dem Schlauch stehe ich noch beim User-Interface.
>> Irgendwer Ideen und Lust, das gemeinsam zu machen?
>
>http://www.behrenhoff.de/sudoku.exe

Danke für den Hinweis. Mir ging es hier durchaus aber um den
Spaß am Lösungbasteln (vulgo Programmiertechnik
verfeinern;-).

>Den Source (Delphi) sende ich gerne zu, wenn du ihn haben willst. Und
>ja, ich habe auch Sets verwendet.

Delphi kann ich leider nicht. Interessieren würde mich eher
der Algorithmus. Was kann das Programm? Kann es komplett
lösen?

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger <3.14@piology.org> schrob:
> Servus!
>
> Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
> programmieren. Entscheidendes Problem ist zunächst einmal
> das Datenmanagement. Ich würde gerne hierzu mit
> Mengenvariablen arbeiten (IIRC ging das in Turbopascal).
> Perl hat sowas ja nicht direkt. Man könnte es natürlich über
> charakteristische Funtkionen simulieren. Sicherlich kann man
> entsprechend auch Funktionen schreiben, um die gängigen
> Mengenoperationen (Vereinigung, Durchschitt,
> Mengesubstraktion) zu erreichen. Aber vielleicht gibt es das
> ja schon in geeigneter Form (meine Google-Suche war
> irgendwie nicht so prickelnd).

Mir fällt dazu erstmal perldoc -q intersect und
http://search.cpan.org/search?query=set&mode=module ein.

HTH, Lukas

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger schrieb:

> Servus!
>
> Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
> programmieren. Entscheidendes Problem ist zunächst einmal
> das Datenmanagement. Ich würde gerne hierzu mit
> Mengenvariablen arbeiten (IIRC ging das in Turbopascal).
> Perl hat sowas ja nicht direkt. Man könnte es natürlich über
> charakteristische Funtkionen simulieren. Sicherlich kann man
> entsprechend auch Funktionen schreiben, um die gängigen
> Mengenoperationen (Vereinigung, Durchschitt,
> Mengesubstraktion) zu erreichen. Aber vielleicht gibt es das
> ja schon in geeigneter Form (meine Google-Suche war
> irgendwie nicht so prickelnd).

Was habt ihr bloss immer mit eurem "gegoogle"?
Du hast ganz offensichtlich das Stichwort Sudoku noch nicht für eine
Suche im CPAN verwendet! Wenns dir nur um eine Lösung geht, dann kannst
du dir Programmierarbeit getrost sparen.

Gruß
Karlheinz

Re: Sudoku loesen / Mengenvariablen?

"Lukas Mai" wrote:

>Mir fällt dazu erstmal perldoc -q intersect und
>http://search.cpan.org/search?query=3Dset&mode=3Dmodule ein.

http://search.cpan.org/~swmcd/Set-IntSpan-1.09/IntSpan.pm
klingt ganz gut. Am Anfang liest sich die Erklärung aber
sehr mühsam.

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger schrieb:
> Wolf Behrenhoff wrote:
>
>>> Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
>>> programmieren. (...).
>>>
>>> Völlig auf dem Schlauch stehe ich noch beim User-Interface.
>>> Irgendwer Ideen und Lust, das gemeinsam zu machen?
>> http://www.behrenhoff.de/sudoku.exe
>
> Danke für den Hinweis. Mir ging es hier durchaus aber um den
> Spaß am Lösungbasteln (vulgo Programmiertechnik
> verfeinern;-).

Ok, ich weiß allerdings nicht, was dich besonders interessiert. Eine GUI
in Perl zu bauen, ist für mich persönlich zum Beispiel schwieriger als
das eigentliche Rätsel zu lösen.

Fang doch einfach mal an, ein Programm zu schreiben.

>> Den Source (Delphi) sende ich gerne zu, wenn du ihn haben willst. Und
>> ja, ich habe auch Sets verwendet.
>
> Delphi kann ich leider nicht. Interessieren würde mich eher
> der Algorithmus. Was kann das Programm? Kann es komplett
> lösen?

Ach, entschuldigung. Ich habe nicht darauf geachtet, dass in dieser
Newsgroup (wenn man sie sich als d.c.l.p.misc anzeigen lässt) das "p"
für Perl steht und nicht für Pascal :-( - und somit mein Delphi-Source
reichlich OT ist. Ja, es kann komplett lösen. Ist eingentlich
superleicht zu programmieren.

Mein Algorithmus geht so:
- suche "einfache" Zahlen, wo auf den ersten Blick klar ist, dass nur
diese Zahl in ein Feld darf
- wenn keine einfachen Zahlen mehr da sind, dann probiere einfach aus
(mit Backtracking)

Wolf

Re: Sudoku loesen / Mengenvariablen?

Wolf Behrenhoff wrote:

>Mein Algorithmus geht so:
>- suche "einfache" Zahlen, wo auf den ersten Blick klar ist, dass nur
>diese Zahl in ein Feld darf
>- wenn keine einfachen Zahlen mehr da sind, dann probiere einfach aus
>(mit Backtracking)

Du spielst da also so lange Möglichkeiten durch, bis es
Widersprüche gibt?

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger schrieb:
> Wolf Behrenhoff wrote:
>
>> Mein Algorithmus geht so:
>> - suche "einfache" Zahlen, wo auf den ersten Blick klar ist, dass nur
>> diese Zahl in ein Feld darf
>> - wenn keine einfachen Zahlen mehr da sind, dann probiere einfach aus
>> (mit Backtracking)
>
> Du spielst da also so lange Möglichkeiten durch, bis es
> Widersprüche gibt?

Ja. Das sind aber nicht viele. Meistens muss das Programm auch bei
schwierigen Rätseln nur 2 oder 3 Zahlen erraten. Okay, vielleicht
manchmal auch 4 oder 5. Das ist aber sehr überschaubar. Der Rest kann
dann durch einfache Logik ermittelt werden.

Einfache Logik ist bei mir:
- wenn in einer Spalte/Zeile/3x3-Feld eine Zahl nur auf einem Feld
erlaubt ist, muss sie dort hin
- wenn es ein Feld gibt, auf das nur eine einzige Zahl darf, ohne mit
der Spalte/Zeile/3x3-Feld zu kollidieren, muss sie dort hin

Wenn es ein Feld gibt, auf das keine Zahl darf, war der Lösungsweg
falsch. Wenn alle Felder ausgefüllt sind, ist das Rätsel gelöst.

Mein Programm zeigt übrigens an, welche Felder geraten wurden und wo
Logik benutzt wurde. Du kannst auch einzelne Schritte machen und dann
die Begründung sehen, sofern es sich um "einfache Logik" handelt.

Wolf

Re: Sudoku loesen / Mengenvariablen?

Wolf Behrenhoff wrote:
> Boris 'pi' Piwinger schrieb:
>> Wolf Behrenhoff wrote:
>>> Mein Algorithmus geht so:
>>> - suche "einfache" Zahlen, wo auf den ersten Blick klar ist, dass
>>> nur diese Zahl in ein Feld darf
>>> - wenn keine einfachen Zahlen mehr da sind, dann probiere einfach
>>> aus (mit Backtracking)
>>
>> Du spielst da also so lange Möglichkeiten durch, bis es
>> Widersprüche gibt?
>
> Ja. Das sind aber nicht viele. Meistens muss das Programm auch bei
> schwierigen Rätseln nur 2 oder 3 Zahlen erraten. Okay, vielleicht
> manchmal auch 4 oder 5. Das ist aber sehr überschaubar. Der Rest kann
> dann durch einfache Logik ermittelt werden.
>
> Einfache Logik ist bei mir:
> - wenn in einer Spalte/Zeile/3x3-Feld eine Zahl nur auf einem Feld
> erlaubt ist, muss sie dort hin
> - wenn es ein Feld gibt, auf das nur eine einzige Zahl darf, ohne mit
> der Spalte/Zeile/3x3-Feld zu kollidieren, muss sie dort hin

Die Logik habe ich mir bei meinem Versuch gespart. Es probiert einfach
alle Möglichkeiten durch (mit Backtracking) und gibt alle Lösungen aus.
Schneller als ich ist es immer noch :-), und ich habe nur ungefähr
gleich lang gebraucht, es zu schreiben, wie ein mittelschweres Sudoku
selber zu lösen.

> Wenn es ein Feld gibt, auf das keine Zahl darf, war der Lösungsweg
> falsch. Wenn alle Felder ausgefüllt sind, ist das Rätsel gelöst.

ACK.

hp

--
_ | Peter J. Holzer | Löschung von at.usenet.schmankerl?
|_|_) | Sysadmin WSR/LUGA |
| | | hjp@hjp.at | Diskussion derzeit in at.usenet.gruppen
__/ | http://www.hjp.at/ |

Re: Sudoku loesen / Mengenvariablen?

Wolf Behrenhoff wrote:

>Einfache Logik ist bei mir:
>- wenn in einer Spalte/Zeile/3x3-Feld eine Zahl nur auf einem Feld
>erlaubt ist, muss sie dort hin
>- wenn es ein Feld gibt, auf das nur eine einzige Zahl darf, ohne mit
>der Spalte/Zeile/3x3-Feld zu kollidieren, muss sie dort hin

Genau das habe ich eben in Excel gebaut. Ich habe Excel
gewählt, weil ich keine Lust auf das User-Interface
hatte;-). Dort wird nicht gesetzt, aber angezeigt, was man
setzen soll. Schritt für Schritt. Jetzt suche ich andere
Lösungsschritte, die das abrunden.

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger <3.14@piology.org> wrote:

>>- wenn in einer Spalte/Zeile/3x3-Feld eine Zahl nur auf einem Feld
>>erlaubt ist, muss sie dort hin
>>- wenn es ein Feld gibt, auf das nur eine einzige Zahl darf, ohne mit
>>der Spalte/Zeile/3x3-Feld zu kollidieren, muss sie dort hin
>
>Genau das habe ich eben in Excel gebaut. Ich habe Excel
>gewählt, weil ich keine Lust auf das User-Interface
>hatte;-). Dort wird nicht gesetzt, aber angezeigt, was man
>setzen soll. Schritt für Schritt. Jetzt suche ich andere
>Lösungsschritte, die das abrunden.

http://piology.org/Temp/Sudoku.xls

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Peter J. Holzer schrieb:
> Wolf Behrenhoff wrote:
>> Einfache Logik ist bei mir:
>> - wenn in einer Spalte/Zeile/3x3-Feld eine Zahl nur auf einem Feld
>> erlaubt ist, muss sie dort hin
>> - wenn es ein Feld gibt, auf das nur eine einzige Zahl darf, ohne mit
>> der Spalte/Zeile/3x3-Feld zu kollidieren, muss sie dort hin
>
> Die Logik habe ich mir bei meinem Versuch gespart. Es probiert einfach
> alle Möglichkeiten durch (mit Backtracking) und gibt alle Lösungen aus.
> Schneller als ich ist es immer noch :-), und ich habe nur ungefähr
> gleich lang gebraucht, es zu schreiben, wie ein mittelschweres Sudoku
> selber zu lösen.

Ja, es ist wesentlich einfacher, ein Lösungsprogramm zu schreiben als
ein kompliziertes Sudoku selbst zu lösen.

Nur finde ich es mit meiner "einfachen Logik" schöner, da das Programm
mir dann den Grund mitteilen kann, warum es eine Zahl auf ein bestimmtes
Feld gesetzt hat und ich mich dann mehr ärgern kann, dass ich das nicht
selbst gesehen habe.

Backtracking brauche ich zwar auch noch, aber oft reicht auch schon
diese einfache Logik aus.

Wolf

Re: Sudoku loesen / Mengenvariablen?

Boris 'pi' Piwinger schrieb:

> Völlig auf dem Schlauch stehe ich noch beim User-Interface.

Ich habe vor kurzem auch mal so ein Programm geschrieben. Das
Benutzerinterface sehr einfach gehalten.
Die Zahlen werden von der Standardeingabe oder von einer als Argument
übergenen Datei eingelesen. 0 repräsentiert ein leeres Feld. Man kann
zwischen den Zahlen soviele Whitespaces machen, wie man will.

Hier ein Link zum Script:
http://erwinh.er.funpic.de/homepage/download/ss-2.0.0.tar.gz
http://erwinh.er.funpic.de/homepage/download/ss-2.0.0.zip

Ich bin mir bewusst der Stil ist wahrscheinlich nicht optimal und die
Lösungsalgorithmen sind auch nicht der Hammer. Aber ich poste das Beispiel,
wegen dem Interface.

mfg Erwin
--
http://erwinherrsche.ch.vu (jeder fängt mal klein an...)

Re: Sudoku loesen / Mengenvariablen?

Hi Boris,

Am Sun, 19 Mar 2006 14:19:04 +0100 schrieb Boris 'pi' Piwinger:

> Servus!
>
> Ich überlege mir gerade, ein Lösungsprogramm für Sudoku zu
> programmieren. Entscheidendes Problem ist zunächst einmal

So etwas habe ich auch begonnen - jedoch in JavaScript und es ruht schon
wieder eine Weile. *g*

Da man es ja bei den herkömmlichen Sudokus mit 9 Blöcken und 3x3 Feldern zu
tuen hat, habe ich einfach 27 Bitfelder verwendet. Jeweils 9 für Spalte,
Reihe und Block mit entsprechend gesetztem Bit welche Zahlen schon
verbraucht sind.

> das Datenmanagement. Ich würde gerne hierzu mit
> Mengenvariablen arbeiten (IIRC ging das in Turbopascal).
> Perl hat sowas ja nicht direkt. Man könnte es natürlich über
> charakteristische Funtkionen simulieren. Sicherlich kann man
> entsprechend auch Funktionen schreiben, um die gängigen
> Mengenoperationen (Vereinigung, Durchschitt,
> Mengesubstraktion) zu erreichen. Aber vielleicht gibt es das
> ja schon in geeigneter Form (meine Google-Suche war
> irgendwie nicht so prickelnd).

Die Mengenoperationen kannst Du dann einfach per Bitoperationen
realisieren.

>
> Völlig auf dem Schlauch stehe ich noch beim User-Interface.
> Irgendwer Ideen und Lust, das gemeinsam zu machen?

DHTML hier.

Mir sind jedenfalls nur 3 Bedingungen zum Lösen der Belegung bekannt,
weshalb das Lösen eines Sudokus doch eher ne stupide Aufgabe ist. Aber
Spass machte es mir schon.

Grüsse,
..max

Re: Sudoku loesen / Mengenvariablen?

Max Dittrich wrote:

>Mir sind jedenfalls nur 3 Bedingungen zum Lösen der Belegung bekannt,

An welche denkst Du?

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html

Re: Sudoku loesen / Mengenvariablen?

Erwin Herrsche wrote:

>> Völlig auf dem Schlauch stehe ich noch beim User-Interface.
>
>Ich habe vor kurzem auch mal so ein Programm geschrieben. Das
>Benutzerinterface sehr einfach gehalten.
>Die Zahlen werden von der Standardeingabe oder von einer als Argument
>übergenen Datei eingelesen. 0 repräsentiert ein leeres Feld. Man =
kann
>zwischen den Zahlen soviele Whitespaces machen, wie man will.=20
>
>Hier ein Link zum Script:
>http://erwinh.er.funpic.de/homepage/download/ss-2.0.0.tar.g z
>http://erwinh.er.funpic.de/homepage/download/ss-2.0.0.zip

Soweit ich das verstehe, machst Du genau das, was ich in
meiner Excel-Lösung habe.

pi
--=20
Attachment? Nein: http://piology.org/ILOVEYOU-Signature-FAQ.html