[HaBo]

**Elderan** · 09.08.06, 18:41

Hallo,
ich denke die meisten hab schon mal was von Sudoku gehört, und wissen wie man es spielt.
Für alle 'Unwissenden': Wikipedia

So für alle die Ungeduldig sind, wäre es schön ein 'Cheat' Programm zu schreiben.
Dies ist eigentlich eine sehr schöne Aufgabe, und hört sich am Anfang schwerer an, als es ist.

Aufgabe
Also der User gibt seine Zahlen der Sudoku-Vorlage ein, am besten per Interface, sonst kann man dies aber z.B. fest im Source Code verankern.
Der Computer soll dann ermitteln, was man in die freien Felder eintragen muss, um das Soduko zu lösen, und am Ende das Ergebnis ausgeben.

Evt. Erweiterung:
Generieren von eindeutigen Sodukos, bei dem der User den Schwierigkeitsgrad bestimmen kann.

Man kann hierbei die Backtracking-Methode verwenden.

Allgemeine Sachen:
Fertige Programme können ein vorgegebenes Sudoku in wenigen Sekunden knacken, also ist der Algorithmus nicht extrem Zeitintensiv, und sehr viele Code-Zeilen sind es auch nicht (der Algorithmus zum Lösen braucht ca. 30 Zeilen).
Aber die Theorie dahinter ist eigentlich ganz intressant.

Mehr zu Backtracking

Sven · 09.08.06, 18:52

Man muss es ja nicht zum Cheaten verwenden, je nach dem kann man es ja auch als "Lösungsvergleich" nehmen.

Hört sich auf jeden Fall interessant an

HaBo Ads

lagalopex · 09.08.06, 19:42

Hmm... genau so eine Aufgabe hab ich Xalon geschickt... mit der möglichen Erweiterung zum generieren eines (eindeutigen) Rätsels... (eine Lösung hab ich auch schon, werde aber noch warten)

LX · 09.08.06, 19:54

Ich hab vor ein paar Monaten mal eine Sudoku-Klasse in PHP für Sudokus beliebiger Größe geschrieben, die auch eine Lösungsmethode enthält. Darin sind mehrere Algorithmen implementiert, die versuchen das Ding logisch aufzulösen sowie auch ein Trial&Error-Mechanismus, falls man mit Logik allein nicht weiter kommt. Eine Demo des ganzen kann man hier angucken

Es ist allerdings nicht zu empfehlen, die Trial&Error-Methode als einzige anzuwenden, die ist ziemlich ressourcenfressend, da sie für jeden Versuch eine Kopie des aktuellen Sudokus anlegt, und dauert auch im Vergleich zu einer Kombination mit den anderen Methoden erheblich länger (bis zum Script-Timeout, den ich aus naheliegenden Gründen dafür nicht deaktivieren wollte *g).

lagalopex · 09.08.06, 20:06

Zitat:

Original von LX
Es ist allerdings nicht zu empfehlen, die Trial&Error-Methode als einzige anzuwenden, die ist ziemlich ressourcenfressend, da sie für jeden Versuch eine Kopie des aktuellen Sudokus anlegt, und dauert auch im Vergleich zu einer Kombination mit den anderen Methoden erheblich länger (bis zum Script-Timeout, den ich aus naheliegenden Gründen dafür nicht deaktivieren wollte *g).

Meine Lösung in C++ braucht etwa 5 ms (AMD64 3700+) für das Bsp bei Wikipedia, wobei aber auch keine Kopien benutzt werden (müssen).

NULL!=NULL · 09.08.06, 20:21

dann zeig uns die doch mal :-)

ich habe shcon mal versucht ein lösungs algo für koruko (oder wie das heißt und nein ich meine nicht soduko!!) herzustellen bin aber gescheitert... :-(

LX · 09.08.06, 20:54

Zitat:

Original von lagalopex
Meine Lösung in C++ braucht etwa 5 ms (AMD64 3700+) für das Bsp bei Wikipedia, wobei aber auch keine Kopien benutzt werden (müssen).

Is' ja irre *g

Einfaches Doubletten-streichen mit meiner PHP-Klasse braucht dafür 33ms auf einem Athlon 2400+.

Mein Schwerpunkt bei der Klasse lag bei den übrigen Algorithmen, die möglichst intelligent vorgehen sollten, nicht beim stupiden ausprobieren. Das hab ich nur noch mit reingenommen, da es gelegentlich ja mal vorkommen kann, dass ein Sudoku allein durch Logik nicht lösbar ist.

**Elderan** · 09.08.06, 22:02

Hallo,
@LX: Bei solchen Sachen ist PHP eh super langsam, um den Faktor 1000 bis xxxx...

Guter Vergleich: Ackermann-Funktion mit n = 3 und m = 12

In C ca. 22 Sek, in PHP bricht der Script vorzeitig (zumindest bei mir):

Ackermann-Funktion in PHP

Vielleicht gehts woanders.

lagalopex · 10.08.06, 13:34

Mit n = 3 und m = 12 braucht C++ 7,2 Sekunden und PHP bricht mit einem Segfault ab.
Verkürzt man auf n = 3 und m = 10 braucht C++ nur noch 0.49 Sekunden und PHP 140 Sekunden. (Was etwa Faktor 285,7 entspricht.)

@NULL!=NULL: koruko kenn ich nicht und google bringt mich da auch nicht weiter. Worum geht es denn?

LX · 10.08.06, 13:57

Ich bin mir dessen bewusst, mit PHP sicherlich keinen Geschwindigkeitsrekord aufzustellen, darum ging's mir auch nicht. Also bitte wieder zum Thema "Sudoku-Solver" zurück und nicht "Programmiersprache X vs. PHP"

elite-noob · 15.08.06, 17:22

wollte nur mal so nebenbei fragen ob diese aufgabe einer von euch zufällig so programmiert hat das man zahlen selber vorgeben kann!?

ich habe mir von bild am sonntag (bitte jetzt nichts dazu sagen) ein sudoku aufs handy geholt und bis auf zwei alles durchbekommen, aber diese zwei bekommt einfach keiner gelöst daher wollte ich wissen ob wir alle zu doof oder das sudoku unlösbar ist!

lange reder kurzer sinn, hat des einer ja oder nein

christian

adrian90 · 15.08.06, 19:39

Eben, auf dieser PHP Seite kannst du ja die Zahlen angeben. Die 0 steht dafür, dass nichts vorhanden ist. Und du fängst die Zahlen von oben links nach rechts unten an anzugeben.

elite-noob · 16.08.06, 10:43

ups, danke, war z war auf der website, hatte aber das lösungsprinzip net ganz verstanden, nach genauen lesen dann schon *schäm*

christian

lagalopex · 17.08.06, 16:49

Wenn ich es richtig sehe, gibt es bisher nur eine Lösung in PHP. Es würde mich mal interessieren, ob noch jemand and dieser Aufgabe arbeitet oder schon alle aufgegeben haben.

mig · 17.08.06, 17:35

bin mehr oder weniger noch am Überlegen wie man das geschickt in Java anstellen könnte

Empfehlung

09.08.06, 18:41	#1 (permalink)
Elderan Moderator Registriert seit: 30.03.04 Likes: 14	Sudoku Cheat-Prog. Hallo, ich denke die meisten hab schon mal was von Sudoku gehört, und wissen wie man es spielt. Für alle 'Unwissenden': Wikipedia So für alle die Ungeduldig sind, wäre es schön ein 'Cheat' Programm zu schreiben. Dies ist eigentlich eine sehr schöne Aufgabe, und hört sich am Anfang schwerer an, als es ist. Aufgabe Also der User gibt seine Zahlen der Sudoku-Vorlage ein, am besten per Interface, sonst kann man dies aber z.B. fest im Source Code verankern. Der Computer soll dann ermitteln, was man in die freien Felder eintragen muss, um das Soduko zu lösen, und am Ende das Ergebnis ausgeben. Evt. Erweiterung: Generieren von eindeutigen Sodukos, bei dem der User den Schwierigkeitsgrad bestimmen kann. Man kann hierbei die Backtracking-Methode verwenden. Allgemeine Sachen: Fertige Programme können ein vorgegebenes Sudoku in wenigen Sekunden knacken, also ist der Algorithmus nicht extrem Zeitintensiv, und sehr viele Code-Zeilen sind es auch nicht (der Algorithmus zum Lösen braucht ca. 30 Zeilen). Aber die Theorie dahinter ist eigentlich ganz intressant. Mehr zu Backtracking

09.08.06, 18:52	#2 (permalink)
Sven Member of Honour Registriert seit: 14.09.03 Likes: 23	Man muss es ja nicht zum Cheaten verwenden, je nach dem kann man es ja auch als "Lösungsvergleich" nehmen. Hört sich auf jeden Fall interessant an __________________ Mein Portfolio best view with open eyes

09.08.06, 19:54	#4 (permalink)
LX Moderator Registriert seit: 14.02.06 Likes: 21	Ich hab vor ein paar Monaten mal eine Sudoku-Klasse in PHP für Sudokus beliebiger Größe geschrieben, die auch eine Lösungsmethode enthält. Darin sind mehrere Algorithmen implementiert, die versuchen das Ding logisch aufzulösen sowie auch ein Trial&Error-Mechanismus, falls man mit Logik allein nicht weiter kommt. Eine Demo des ganzen kann man hier angucken Es ist allerdings nicht zu empfehlen, die Trial&Error-Methode als einzige anzuwenden, die ist ziemlich ressourcenfressend, da sie für jeden Versuch eine Kopie des aktuellen Sudokus anlegt, und dauert auch im Vergleich zu einer Kombination mit den anderen Methoden erheblich länger (bis zum Script-Timeout, den ich aus naheliegenden Gründen dafür nicht deaktivieren wollte g). __________________ "Ever tried. Ever failed. No matter. Try again. Fail again. Fail better." - Samuel Beckett* JS BB LX UP

09.08.06, 22:02	#8 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, @LX: Bei solchen Sachen ist PHP eh super langsam, um den Faktor 1000 bis xxxx... Guter Vergleich: Ackermann-Funktion mit n = 3 und m = 12 In C ca. 22 Sek, in PHP bricht der Script vorzeitig (zumindest bei mir): Ackermann-Funktion in PHP hab PHP-Code: <?php set_time_limit(0); $start = time(); $n = 3; for($m=0;$m<=12;$m++) $x = ack($n,$m); $ende = time(); echo "Dauer: ".($ende-$start); function ack($m, $n) { $x=0; if($m != 0) { if($n == 0) { $x=ack($m-1,1); } else { $x = ack($m-1, ack($m, $n - 1)); } } else { $x= $n+1; } return $x; } ?> Vielleicht gehts woanders.

10.08.06, 13:57	#10 (permalink)
LX Moderator Registriert seit: 14.02.06 Likes: 21	Ich bin mir dessen bewusst, mit PHP sicherlich keinen Geschwindigkeitsrekord aufzustellen, darum ging's mir auch nicht. Also bitte wieder zum Thema "Sudoku-Solver" zurück und nicht "Programmiersprache X vs. PHP" __________________ "Ever tried. Ever failed. No matter. Try again. Fail again. Fail better." - Samuel Beckett JS BB LX UP

09.08.06, 19:42	#3 (permalink)
lagalopex Registriert seit: 01.11.03 Likes: 0	Hmm... genau so eine Aufgabe hab ich Xalon geschickt... mit der möglichen Erweiterung zum generieren eines (eindeutigen) Rätsels... (eine Lösung hab ich auch schon, werde aber noch warten)

09.08.06, 20:21	#6 (permalink)
NULL!=NULL Registriert seit: 18.07.05 Likes: 0	dann zeig uns die doch mal :-) ich habe shcon mal versucht ein lösungs algo für koruko (oder wie das heißt und nein ich meine nicht soduko!!) herzustellen bin aber gescheitert... :-(

10.08.06, 13:34	#9 (permalink)
lagalopex Registriert seit: 01.11.03 Likes: 0	Mit n = 3 und m = 12 braucht C++ 7,2 Sekunden und PHP bricht mit einem Segfault ab. Verkürzt man auf n = 3 und m = 10 braucht C++ nur noch 0.49 Sekunden und PHP 140 Sekunden. (Was etwa Faktor 285,7 entspricht.) @NULL!=NULL: koruko kenn ich nicht und google bringt mich da auch nicht weiter. Worum geht es denn?

15.08.06, 17:22	#11 (permalink)
elite-noob Registriert seit: 25.09.05 Likes: 1	wollte nur mal so nebenbei fragen ob diese aufgabe einer von euch zufällig so programmiert hat das man zahlen selber vorgeben kann!? ich habe mir von bild am sonntag (bitte jetzt nichts dazu sagen) ein sudoku aufs handy geholt und bis auf zwei alles durchbekommen, aber diese zwei bekommt einfach keiner gelöst daher wollte ich wissen ob wir alle zu doof oder das sudoku unlösbar ist! lange reder kurzer sinn, hat des einer ja oder nein christian

15.08.06, 19:39	#12 (permalink)
adrian90 Registriert seit: 06.04.05 Likes: 0	Eben, auf dieser PHP Seite kannst du ja die Zahlen angeben. Die 0 steht dafür, dass nichts vorhanden ist. Und du fängst die Zahlen von oben links nach rechts unten an anzugeben.

16.08.06, 10:43	#13 (permalink)
elite-noob Registriert seit: 25.09.05 Likes: 1	ups, danke, war z war auf der website, hatte aber das lösungsprinzip net ganz verstanden, nach genauen lesen dann schon schäm christian

17.08.06, 16:49	#14 (permalink)
lagalopex Registriert seit: 01.11.03 Likes: 0	Wenn ich es richtig sehe, gibt es bisher nur eine Lösung in PHP. Es würde mich mal interessieren, ob noch jemand and dieser Aufgabe arbeitet oder schon alle aufgegeben haben.

17.08.06, 17:35	#15 (permalink)
mig Registriert seit: 12.08.06 Likes: 0	bin mehr oder weniger noch am Überlegen wie man das geschickt in Java anstellen könnte

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Sudoku-Generator	CDW	Programmieraufgaben	1	04.08.09 02:12
Sudoku	Ook!	Code Kitchen	2	25.05.08 11:00
The Cheat Report	stone.dr	Fun Section	17	20.03.06 15:18
Sudoku programmieren	jami	Code Kitchen	1	16.10.05 15:05


HaBo Ads HaBOT

[HaBo]

Sudoku Cheat-Prog.