Sodoku mathematisch beschrieben
Tino Raspari
ich habe ein kleines Problem. Ich soll für Info ein Programm schreiben
welches zufällig eines aller möglichen Sodokus ausgibt...
Also ein ausgefülltes Sodoku zu erstellen ist ja nicht schwierig, was mir
allerdings Schwierigkeiten bereitet, ist, dass man ja auch Lücken lassen
muss, damit es ein Rätsel wird. Meine Frage ist nun, wie ich die Lücken
setzen muss, damit das Sodoku, eindeutig zu lösen bleibt. Die Maßgabe ist
also, dass es nur eine mögliche Lösung gibt...
Ich hab mir mal ein Paar schwere Sodokus angesehen und habe festgestellt,
dass immer wenigstens 28 von 81 Feldern mit Zahlen gefüllt sind, außerdem
befinden sich in einem der Kästchen immer 2;3 oder 4 Zahlen, so dass es
zusammen 28 werden.
Fällt da jemandem ein Algorithmus ein oder so?!
Mfg Tino
--
-=Computer tun nicht, was sie sollen, sie tun das, was man ihnen sagt.=-
Rainer Rosenthal
> ich habe ein kleines Problem. Ich soll für Info ein Programm schreiben
> ... Fällt da jemandem ein Algorithmus ein oder so?!
Eher "oder so": versuche Deine Anfragen geschickter zu stellen.
Etwa so: ich bin ein begeisterter Sudoku-Löser und habe mir
einfach mal so die Frage gestellt, wie die Leute das schaffen,
diese Rätsel zu bauen. Lösen ist (oft) schwierig, aber solche
Aufgaben zu stellen, so dass sie möglichst eindeutig lösbar
sind, davor habe ich alle Hochachtung. Steckt da Mathematik
dahinter? Und wenn ja, welche und wie könnte man so etwas selbst
machen?
Andernfalls stellt sich beim durchschnittlichen dsm-Leser die
Frage: Äh was bitte? Der hat Hausaufgaben auf und ich soll sie
ihm lösen?
Gruss,
Rainer Rosenthal
r.ros...@web.de
Tino Raspari
Ich verstehe dich^^
Es ist ja keine Hausaufgabe, sondern eher eine Aufgabe die uns gestellt
wurde, damit wir unsere Fähigkeiten verbessern können.
Allerdings müsste ich lügen um zu sagen, dass ich ein begeisterter
Sodokulöser bin! Das ist ja das eigentliche Problem.. Ich weiß halt nicht
genau ,wie das aufgebaut ist..
Mein Ansatz wäre gewesen, zufällig felder leer zu lassen und dann zu
überprüfen ob es noch lösbar, und wenn, eindeutig lösbar ist...
Das hab ich allerdings mal so Pi mal daumen überschlagen, und bin zu dem
Schluss gekommen, dass das viel zu lange dauert..
Ich hoffe, dass sich hier schonmal jemand damit beschäftigt hat!
mfg Tino
Thomas Nordhaus
> Hallo,
>
> ich habe ein kleines Problem. Ich soll für Info ein Programm schreiben
> welches zufällig eines aller möglichen Sodokus ausgibt...
> Also ein ausgefülltes Sodoku zu erstellen ist ja nicht schwierig, was mir
> allerdings Schwierigkeiten bereitet, ist, dass man ja auch Lücken lassen
> muss, damit es ein Rätsel wird. Meine Frage ist nun, wie ich die Lücken
> setzen muss, damit das Sodoku, eindeutig zu lösen bleibt. Die Maßgabe ist
> also, dass es nur eine mögliche Lösung gibt...
> Ich hab mir mal ein Paar schwere Sodokus angesehen und habe festgestellt,
> dass immer wenigstens 28 von 81 Feldern mit Zahlen gefüllt sind, außerdem
> befinden sich in einem der Kästchen immer 2;3 oder 4 Zahlen, so dass es
> zusammen 28 werden.
> Fällt da jemandem ein Algorithmus ein oder so?!
Na, das schreit aber direkt nach einer Internetrecherche, oder? Schau
mal bei wikipedia unter Sudoku (schreib das Wort in Zukunf um Gottes
Willen richtig!) nach. Da steht ein Algorithmus zum Erstellen neuer
Sudokus. Wenn das nicht reicht, dann googeln: Vernünftige Stichwörter
suchen und los!
--
Thomas Nordhaus
Stefan Kirchner
> Hallo,
>
> ich habe ein kleines Problem. Ich soll für Info ein Programm schreiben
> welches zufällig eines aller möglichen Sodokus ausgibt...
> Also ein ausgefülltes Sodoku zu erstellen ist ja nicht schwierig,
... das ist doch schon einmal brauchbar. Sei P so ein Sudoku.
> was mir
> allerdings Schwierigkeiten bereitet, ist, dass man ja auch Lücken lassen
> muss, damit es ein Rätsel wird. Meine Frage ist nun, wie ich die Lücken
> setzen muss, damit das Sodoku, eindeutig zu lösen bleibt. Die Maßgabe ist
> also, dass es nur eine mögliche Lösung gibt...
Zäume das Pferd von hinten auf: Angenommen Du hast einen Algorithmus A,
der entscheidet, ob ein Sudoku eindeutig ist. Dann kannst Du von P aus
sukzessive ein mit einer Zahl belegtes Feld (x,y) herausnehmen, sofern es
eindeutig bleibt (das sagt Dir A). Also in Pseudocode:
while (es gibt ein mit einer Zahl belegtes Feld (x,y), so dass
P-(x,y) eindeutig lösbar ist)
P=P-(x,y) // Die Zahl auf (x,y) wird gelöscht
endwhile
Damit erhältst Du ein minimales Sudoku, d.h. egal welche Zahl Du jetzt
noch entfernst, macht es mehrdeutig.
Die Korrektheit kannst Du induktiv beweisen:
Induktionsanfang: P ist sicherlich eindeutig, ist ja schon fertig gelöst.
Induktionsschritt: bleibt dem Leser überlassen
Bleibt also noch offen, wie man A bastelt und weiterhin, wie man auch
"interessante" Sudokus hinbekommt, aber zu diesem Thema gibt es einiges im
Netz.
> Ich hab mir mal ein Paar schwere Sodokus angesehen und habe festgestellt,
> dass immer wenigstens 28 von 81 Feldern mit Zahlen gefüllt sind, außerdem
> befinden sich in einem der Kästchen immer 2;3 oder 4 Zahlen, so dass es
> zusammen 28 werden.
Das mag bei Deiner Stichprobe der Fall gewesen sein. Generell stimmt es
nicht. Unter http://people.csse.uwa.edu.au/gordon/sudokumin.php findest Du
47499 strukturverschiedene eindeutig lösbare Sudokus mit 17 vorgegebenen
Zahlen. Ob es welche mit 16 Zahlen gibt, ist ein noch offenes Problem.
Wenn Du eines mit der oben beschriebenen Mehthode finden solltest, teile
es uns bitte mit. :-)
Nebenbei: ob ein Sudoku "leicht" oder "schwer" ist, ist relativ unabhängig
davon, wie viele Zahlen am Anfang vorgegeben sind.
Gruß Stefan
PS. Es heißt S_u_doku
Roland Damm
Tino Raspari schrub:
> ich habe ein kleines Problem. Ich soll für Info ein Programm
> schreiben welches zufällig eines aller möglichen Sodokus
> ausgibt... Also ein ausgefülltes Sodoku zu erstellen ist ja
> nicht schwierig, was mir allerdings Schwierigkeiten bereitet,
> ist, dass man ja auch Lücken lassen muss, damit es ein Rätsel
> wird. Meine Frage ist nun, wie ich die Lücken setzen muss,
> damit das Sodoku, eindeutig zu lösen bleibt. Die Maßgabe ist
> also, dass es nur eine mögliche Lösung gibt... Ich hab mir mal
> ein Paar schwere Sodokus angesehen und habe festgestellt, dass
> immer wenigstens 28 von 81 Feldern mit Zahlen gefüllt sind,
> außerdem befinden sich in einem der Kästchen immer 2;3 oder 4
> Zahlen, so dass es zusammen 28 werden. Fällt da jemandem ein
> Algorithmus ein oder so?!
Ich glaube, das Problem ist ein solches, welches kaum einfach
lösbar ist. Ich habe zu Weihnachten einen Sudoku-Computer
verschenkt, und der ist ein Reinfall: Der erzeugt keine
eindeutig lösbaren Rätsel. Gut, nur weil jemand sowas schlecht
programmiert hat, heißt das ja nicht, dass es nicht besser
ginge. Aber ich fürchte, die Eindeutigkeit eines Rätsels lässt
sich nur experimentell ermitteln, sprich du brauchst ein
Lösungsalgorithmus, der das gegebene Rätsel überprüft.
Eine Variante, aber vermutlich keine gute, währe der
rückwärts-Aufbau. Du ermittelst ein gefülltes Rätsel. Dann
wählst du zufällig Felder aus und überprüfst, ob die Zahl in dem
Feld eindeutig ist. Wenn ja, streichst du die Zahl, das Feld ist
dann leer. Das machst du so lange, bis genügend freie Felder da
sind. Ich würde aber annehmen, dass auf diese Weise nur recht
einfache Rätsel entstehen. Ich sehe gerade, 'ksudoku'
(Linux-Programm) macht das genau so, b.z.w. für höhere
Schwierigkeitsgrade werden zufällig weitere Zahlen entfernt.
Dann habe ich hier noch ein Progrämmchen namens 'sudoku-solver'
(auch Linux), welches solche Rätsel lösen kann, bei
Mehrdeutigkeiten auch alle Lösungen ausgeben kann. Man eben
getestet, ein nicht eindeutiges Sudoku eingegeben und das
Programm errechnete über 2000 verschiedene Lösungen und gibt sie
in Textform auf dem Bildschirm aus - in deutlich unter einer
Sekunde Rechenzeit.
Was du brauchst, ist ja ein Test auf Eindeutigkeit, ich vermute
der sollte schneller sein, als ein Verfahren, dass alle Lösungen
ermittelt und ausgibt.
Sprich: So riesig ist der Rechenaufwand garnicht, es ist durchaus
machbar: zunächst sind alle Felder gefüllt, dann werden zufällig
einzelen Felder leer gemacht und jeweils überprüft, ob das
Rätsel noch eindeutig ist. Wenn die Eindeutigkeit verloren ging,
wird die Zahl wieder hingeschrieben und eine andere gestrichen.
Und das so lange, bis keine Zahl mehr streichbar ist b.z.w.
genügend Felder leer sind.
CU Rollo
Holger Korn
> dass immer wenigstens 28 von 81 Feldern mit Zahlen gefüllt sind, außerdem
> befinden sich in einem der Kästchen immer 2;3 oder 4 Zahlen, so dass es
> zusammen 28 werden.
ich kann mich leider nicht mehr ins Detail daran erinnern, in einer
sogenannten populärwissenschaftlichen Zeitschrift habe ich mal vor 1-2
Jahren gelesen dass die geringste Zahlenmenge für ein eindeutig zu lösenden
Soudoku bei 17 liegt.
(vermutlich wurde das auch mathematisch bewiessen)
--
cu |_|
|olger
Marc Olschok
>[...]
> sogenannten populärwissenschaftlichen Zeitschrift habe ich mal vor 1-2
> Jahren gelesen dass die geringste Zahlenmenge für ein eindeutig zu
> lösenden Soudoku bei 17 liegt.
> (vermutlich wurde das auch mathematisch bewiessen)
Zumindest ist sie minimale Anzahl nach oben durch 17 beschränkt.
Dazu reicht es, ein eindeutig lösbares Sudoku mit 17 Einträgen
anzugeben. Siehe etwa:
<http://www.ams.org/notices/200706/tx070600708p.pdf>
Marc
P.S.: die Diskussion, ob man nun soudoku, sudoku oder suudoku
schreiben soll, kann man natürlich umschiffen, indem man
gleich 数獨verwendet.
Roland Damm
Stefan Kirchner schrub:
> Nebenbei: ob ein Sudoku "leicht" oder "schwer" ist, ist relativ
> unabhängig davon, wie viele Zahlen am Anfang vorgegeben sind.
Dabei habe ich obendrein noch den Verdacht, dass es noch keinen
vernünftigen Algorithmus gibt, um die Schwierigkeit eines Sudoku
zu bewerten b.z.w. ein Sudoku gegebener Schwierigkeit zu
erzeugen.
CU Rollo
Stefan Kirchner
Ersteres ist nicht besonders schwierig. Wenn ein Mensch ein Sudoku löst,
hat er in der Regel ein paar Heuristiken, die es ihm gestatten, ein freies
Feld eindeutig mit einer Zahl zu belegen, und die er so lange wie möglich
anwendet. Diese Heuristiken können natürlich implementiert werden und man
kann schauen, ob sich das Sudoku damit vollständig lösen lässt bzw. ab
wann Backtracking notwendig wird und wie weit sich dann der Suchbaum -
unter weiterer Anwendung der Heuristiken - verzweigt. Die Größe dieses
Suchbaums ist dann ein ganz gutes Maß für die Schwierigkeit eines Sudokus,
wenn ein Mensch es lösen soll.
Ein Sudoku zu finden, das unter einer Menge von Heuristiken den
dazugehörigen Suchbaum maximiert, ist deutlich schwieriger.
Gruß Stefan
Rainer Rosenthal
> <http://www.ams.org/notices/200706/tx070600708p.pdf>
Auf Seite 713 fand ich den Begriff "doppelt stochastische
Matrix", den ich Anfang Jahr das erste Mal in meinem Leben
gelesen habe. Da ging es um das nette 2008-Rätsel von
Jan Fricke in de.rec.denksport: Zähle alle 4x4-Matrizen,
deren Einträge 0, 1, 2 oder 3 sein dürfen, und in denen sich
alle Zeilen und alle Spalten zu 3 aufsummieren.
An Marc: ich würde mich über eine Mail freuen.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Roland Damm
Stefan Kirchner schrub:
>> Dabei habe ich obendrein noch den Verdacht, dass es noch
>> keinen vernünftigen Algorithmus gibt, um die Schwierigkeit
>> eines Sudoku zu bewerten b.z.w. ein Sudoku gegebener
>> Schwierigkeit zu erzeugen.
>
> Ersteres ist nicht besonders schwierig. Wenn ein Mensch ein
> Sudoku löst, hat er in der Regel ein paar Heuristiken, die es
> ihm gestatten, ein freies Feld eindeutig mit einer Zahl zu
> belegen, und die er so lange wie möglich anwendet. Diese
> Heuristiken können natürlich implementiert werden und man kann
> schauen, ob sich das Sudoku damit vollständig lösen lässt bzw.
> ab wann Backtracking notwendig wird und wie weit sich dann der
> Suchbaum - unter weiterer Anwendung der Heuristiken -
> verzweigt.
Genauso ist es aber wichtig, die verschiedenen Heuristiken zu
bewerten, die Nötig sind, um ein Rätsel zu lösen.
> Die Größe dieses Suchbaums ist dann ein ganz gutes
> Maß für die Schwierigkeit eines Sudokus, wenn ein Mensch es
> lösen soll.
Nur dann, wenn der Computer die gleichen Heuristiken beherrscht,
wie der menschliche Löser. Und nicht mehr und nicht weniger. Und
auch dann hilft es nur bei Rätseln weiter, bei denen mehr oder
weniger viele 'Raten'-Schritte (also Schritte, die den Suchbaum
aufblähen und Rekursion erfordern) erforderlich sind.
> Ein Sudoku zu finden, das unter einer Menge von Heuristiken den
> dazugehörigen Suchbaum maximiert, ist deutlich schwieriger.
Wenn ersteres gelöst ist, geht zweiteres via BruteForce.
CU Rollo
Carlos Naplos
Benno Hartwig
"Roland Damm" <rolan...@arcor.de> schrieb
>> Nebenbei: ob ein Sudoku "leicht" oder "schwer" ist, ist relativ
>> unabhängig davon, wie viele Zahlen am Anfang vorgegeben sind.
>
> Dabei habe ich obendrein noch den Verdacht, dass es noch keinen
> vernünftigen Algorithmus gibt, um die Schwierigkeit eines Sudoku
> zu bewerten b.z.w. ein Sudoku gegebener Schwierigkeit zu
> erzeugen.
Ich hatte mal den Verdacht, dass Sodokus eher leichter
zu lösen sind, wenn man mehr Zahlen geboten bekommt.
Und so mutmaßte ich, dass die 17er-Sodokus wohl besonders
schwierig sind.
Ich zeigte mal jemandem, der ganz gern und regelmäßig
Sodokus löst, einige solche 17er-Sodokus.
Und er meinte, dass diese 17er-Sodokus _nicht_
besonders schwierig waren, dass er schon an
deutlich schwierigeren herumgerätselt hatte.
Benno
Benno Hartwig
"Roland Damm" <rolan...@arcor.de> schrieb
> Wenn ersteres gelöst ist, geht zweiteres via BruteForce.
Auch Schach ist prinzipiell BruteForce-mäßig
komplett durchrechenbar.
Allein es mangelt an der Rechenzeit
(oder Rechengeschwindigkeit)
Ist es hier ähnlich?
Benno
Herbert Kleebauer
> Ersteres ist nicht besonders schwierig. Wenn ein Mensch ein Sudoku löst,
> hat er in der Regel ein paar Heuristiken, die es ihm gestatten, ein freies
> Feld eindeutig mit einer Zahl zu belegen, und die er so lange wie möglich
> anwendet. Diese Heuristiken können natürlich implementiert werden und man
> kann schauen, ob sich das Sudoku damit vollständig lösen lässt bzw. ab
> wann Backtracking notwendig wird und wie weit sich dann der Suchbaum -
> unter weiterer Anwendung der Heuristiken - verzweigt. Die Größe dieses
> Suchbaums ist dann ein ganz gutes Maß für die Schwierigkeit eines Sudokus,
> wenn ein Mensch es lösen soll.
Ich denke es gibt überhaupt nur zwei Schwierigkeitstufen. Ich habe mal ein
ein sehr einfaches Prgramm geschrieben um ein Sudoku zu lösen. Bevor ich
eine Rekursion einbaute, wollte ich den Code testen. Und ich habe bisher
nur zwei Klassen von Sudokus gefunden. Die eine lassen sich direkt lösen
(durch Auschluß nicht möglicher Zahlen) und bei den anderen muß man
genau einmal raten um den Rest dann ebenfalls direkt lösen zu können.
Aber vielleicht hat ja jemand ein Sudoku, daß sich nicht mit einem
einzigen Ratevorgang lösen läßt sondern wirklich eine Rekursion erfordert.
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
@echo off
echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
echo hhpbbnpljhoxolnhaigidpllnbkdnhlkfhlflefblffahfUebdfahhfkokh>>sudo.com
echo wPajQJ///MKiF0///M5uqA///k1AmNDRFkH1r0jNl7hNDgekbNKWKgC1bNq>>sudo.com
echo l5///yDUN2OA0b8CpaVyX1///aVCK0///axUUj0///M5uq1///ErLat@L4/>>sudo.com
echo //aZPI////bNqW5I7kplXN0XC3adf/////apP1////aJ7ooVVNcX4///kNa>>sudo.com
echo Zc4aVyS////oFXNcP4///UNF@iNBJ6ra4AsEQaN8OUN2OA0b8ShaV@B4///>>sudo.com
echo fnVNsOE0//kuCM5iqH///gC2aV@54///aVyz0///aVCL1///aVib1///a0a>>sudo.com
echo NymJ0//UNz1e0//kuCM5Mat@c5///ax@L4///aZPI////nTaNZOKMEOqka0>>sudo.com
echo aNymJ0//UNt54///UNlwzNahc041QRPNqUD6UN0XC3adf/////a4nqapP1/>>sudo.com
echo ///aJ7ooBmNaZc4aViJ////nZUN2ywza42ofvUN4iRR4MKWHjC0aBsmzPKo>>sudo.com
echo WPKHp4hN4iBRbUb0bNKWSgC1a4AsEQaN8OUN2OA0b8iZaJszax/WxxzzzPK>>sudo.com
echo MEWjN2PqU76UNV0NyaBgNUNajQJ///MKi8////Mqi7////QaN@OUN89wNaB>>sudo.com
echo /0SSaN@EVbahIRmbXkaxEVt2///MKke2VN8/RDyDUNDI7u////aBclYQas3>>sudo.com
echo PajQJ///MKi8////Mqi7////QaN@OUN89wNap7@PRaNBmKP/QaN2EUfbNq1>>sudo.com
echo IseN@Jrtt7gNDIcd////a4guEMK1ErXz2Mq24K8///UN2OA0b8Siat@L4//>>sudo.com
echo /aZv/////ahv/////bNqW5MKW1TaN2M30bNq1KFkNaBUF7QaN@M41bNq/5F>>sudo.com
echo mNahUJYQaN2M39bNq1KVmNaBUFgQaN@M4@bNq/5VoNahUJ7RaN2M3HbNq1K>>sudo.com
echo loNaBUFERaN@M4It7QRVMKke2VN8/RDyDERJMqU5nUN@JLYaBcl7Ras3OKM>>sudo.com
echo EWjN2PKMEajN2P5MkqUNcf7////g9M5u11///MajQJ///Mqi8////MKj8//>>sudo.com
echo //QaN@OVN2OA0aZf1////k1XNFfiQ6M5Eb8ixkuWNcv3///UNBJbqkqUNc@>>sudo.com
echo 3////g9M5uu////MqGp0gNV0dN2P5MaZclbl9V/H61aVC7////f@jNV0dN2>>sudo.com
echo P5MoyXiMJEi0/EAPrQ7a45YaxUh5UJ0aBgNU89K4E@EuWJ0t5//v5//B6WN>>sudo.com
echo V0dN2X@/ApQ7BcEOglKNb45PUYaPkJ6R/oU1YZaQZB5RgZ67nx5PqJ5N/oU>>sudo.com
echo 1nx5PqJ5NUQLOoV57jtKNU7LNXJbQnZqPi0E29sqPo0mQjlaRZ4aMgJ57rZ>>sudo.com
echo 5Rc0mPiJ57mJqMp8rQdxaP//UP.>>sudo.com
:::::::::::::::::::::::::: puzzle 1
echo 000 000 501 >a1
echo 000 040 060 >>a1
echo 620 300 000 >>a1
echo 001 702 000 >>a1
echo 000 406 083 >>a1
echo 007 000 000 >>a1
echo 083 000 009 >>a1
echo 700 050 400 >>a1
echo 000 900 100 >>a1
:::::::::::::::::::::::::: puzzle 2
echo 000 060 080 >a2
echo 700 500 000 >>a2
echo 000 801 000 >>a2
echo 009 006 000 >>a2
echo 000 000 201 >>a2
echo 000 024 600 >>a2
echo 030 000 052 >>a2
echo 105 003 000 >>a2
echo 020 900 408 >>a2
:::::::::::::::::::::::::: puzzle 3
echo 060 700 080 >a3
echo 040 050 900 >>a3
echo 000 001 003 >>a3
echo 002 000 001 >>a3
echo 070 004 060 >>a3
echo 800 003 500 >>a3
echo 900 800 000 >>a3
echo 001 020 070 >>a3
echo 050 006 000 >>a3
:::::::::::::::::::::::::: puzzle 4
echo 070 080 050 >a4
echo 900 000 002 >>a4
echo 000 405 000 >>a4
echo 006 040 700 >>a4
echo 300 702 004 >>a4
echo 000 050 900 >>a4
echo 004 803 000 >>a4
echo 700 000 009 >>a4
echo 030 090 010 >>a4
:::::::::::::::::::::::::: puzzle 5
echo 000 005 009 >a5
echo 001 000 300 >>a5
echo 040 902 010 >>a5
echo 506 030 007 >>a5
echo 000 020 000 >>a5
echo 003 000 408 >>a5
echo 090 500 020 >>a5
echo 007 000 900 >>a5
echo 000 008 000 >>a5
:::::::::::::::::::::::::: puzzle 6 (an easy one)
echo 400 000 582 >a6
echo 000 503 000 >>a6
echo 700 028 090 >>a6
echo 897 000 050 >>a6
echo 304 090 108 >>a6
echo 060 000 937 >>a6
echo 070 630 005 >>a6
echo 000 807 000 >>a6
echo 238 000 001 >>a6
:::::::::::::::::::::::::: puzzle 7
echo 000 000 002 >a7
echo 009 700 100 >>a7
echo 050 301 040 >>a7
echo 023 000 650 >>a7
echo 000 000 000 >>a7
echo 046 000 790 >>a7
echo 000 507 000 >>a7
echo 002 600 300 >>a7
echo 800 000 001 >>a7
:::::::::::::::::::::::::: puzzle 8
echo 300 070 005 >a8
echo 070 009 000 >>a8
echo 400 005 020 >>a8
echo 701 060 008 >>a8
echo 008 000 300 >>a8
echo 090 000 700 >>a8
echo 020 700 009 >>a8
echo 050 800 040 >>a8
echo 000 010 000 >>a8
sudo <a1
pause
sudo <a2
pause
sudo <a3
pause
sudo <a4
pause
sudo <a5
pause
sudo <a6
pause
sudo <a7
pause
sudo <a8
pause
for %%i in (a1 a2 a3 a4 a5 a6 a7 a8 sudo.com) do del %%i
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Philipp Zumstein
Sudoku is NP-schwer, wobei man dabei ein Sudoku der Grösse n^2xn^2
gegeben sowie eine Lösung und entscheiden muss ob es noch eine andere
Lösung gibt.
Siehe dazu auch:
http://www-ti.informatik.tu-cottbus.de/Studium/07SemSpiele/index.html
Grüsse,
Philipp
Tino Raspari schrieb:
Roland Damm
Herbert Kleebauer schrub:
> Ich denke es gibt überhaupt nur zwei Schwierigkeitstufen. Ich
> habe mal ein ein sehr einfaches Prgramm geschrieben um ein
> Sudoku zu lösen. Bevor ich eine Rekursion einbaute, wollte ich
> den Code testen. Und ich habe bisher nur zwei Klassen von
> Sudokus gefunden. Die eine lassen sich direkt lösen (durch
> Auschluß nicht möglicher Zahlen) und bei den anderen muß man
> genau einmal raten um den Rest dann ebenfalls direkt lösen zu
> können. Aber vielleicht hat ja jemand ein Sudoku, daß sich
> nicht mit einem einzigen Ratevorgang lösen läßt sondern
> wirklich eine Rekursion erfordert.
Das kommt darauf an, wie ausgefeilt der Programmteil ist, der
ohne Rekursion hinkommt.
> :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
> @echo off
> echo
>
hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
> echo
> ......
Was bietest du hier für einen Virus an? :-)
CU Rollo
Klaus Nagel
>
> Ich denke es gibt überhaupt nur zwei Schwierigkeitstufen. Ich habe mal ein
> ein sehr einfaches Prgramm geschrieben um ein Sudoku zu lösen. Bevor ich
> eine Rekursion einbaute, wollte ich den Code testen. Und ich habe bisher
> nur zwei Klassen von Sudokus gefunden. Die eine lassen sich direkt lösen
> (durch Auschluß nicht möglicher Zahlen) und bei den anderen muß man
> genau einmal raten um den Rest dann ebenfalls direkt lösen zu können.
> Aber vielleicht hat ja jemand ein Sudoku, daß sich nicht mit einem
> einzigen Ratevorgang lösen läßt sondern wirklich eine Rekursion erfordert.
>
Ich habe vor längerer Zeit ein interaktives Sudoku-Lösungsprogramm
geschrieben und dieses auf das heutige mittelschwere Problem aus der
Süddeutschen Zeitung angesetzt:
http://nagel-klaus.homepage.t-online.de/Sudoko.jpg
Die großen schwarzen Zahlen sind die vorgegebenen Werte, die roten die
schon gelösten, während die kleinen Zahlen die verbleibenden
Möglichkeiten für jedes Feld anzeigen. Acht Zahlen ergaben sich
zwangsmäßig, aber dann muß zwischen mindestens zweien geraten werden,
und das geschieht bis zur endgültigen Lösung noch mehrmals.
Gruß,
Klaus Nagel
Steffen Buehler
> Ich habe vor längerer Zeit ein interaktives Sudoku-Lösungsprogramm
> geschrieben und dieses auf das heutige mittelschwere Problem aus der
> Süddeutschen Zeitung angesetzt:
>
> http://nagel-klaus.homepage.t-online.de/Sudoko.jpg
>
> Die großen schwarzen Zahlen sind die vorgegebenen Werte, die roten die
> schon gelösten, während die kleinen Zahlen die verbleibenden
> Möglichkeiten für jedes Feld anzeigen. Acht Zahlen ergaben sich
> zwangsmäßig, aber dann muß zwischen mindestens zweien geraten werden,
> und das geschieht bis zur endgültigen Lösung noch mehrmals.
Ich bin nicht sehr erfahren mit Sudokus, aber in Deiner Lösung sollte es
jetzt mit der 1 in Reihe7/Spalte6 weitergehen. Das erzwingt danach die 1
in Reihe8/Spalte2. Weiter habe ich jetzt nicht gemacht, aber vielleicht
schaust Du Dein Programm nochmal durch.
Nix für ungut
Steffen
Herbert Kleebauer
> Herbert Kleebauer wrote:
> Ich habe vor längerer Zeit ein interaktives Sudoku-Lösungsprogramm
> geschrieben und dieses auf das heutige mittelschwere Problem aus der
> Süddeutschen Zeitung angesetzt:
>
> http://nagel-klaus.homepage.t-online.de/Sudoko.jpg
>
> Die großen schwarzen Zahlen sind die vorgegebenen Werte, die roten die
> schon gelösten, während die kleinen Zahlen die verbleibenden
> Möglichkeiten für jedes Feld anzeigen. Acht Zahlen ergaben sich
> zwangsmäßig, aber dann muß zwischen mindestens zweien geraten werden,
> und das geschieht bis zur endgültigen Lösung noch mehrmals.
Es ergeben sich alle Zahlen direkt, kein Raten erforderlich:
89.36....
..1.928..
7....8...
..7.1.56.
5.....37.
.4.....8.
...7.....
6...39...
3.....1.9
892367415
461592837
735148296
927813564
586924371
143675982
259781643
614239758
378456129
directly solved
Marko Renner
> Ich habe vor längerer Zeit ein interaktives Sudoku-Lösungsprogramm
> geschrieben und dieses auf das heutige mittelschwere Problem aus der
> Süddeutschen Zeitung angesetzt:
>
> http://nagel-klaus.homepage.t-online.de/Sudoko.jpg
>
> Die großen schwarzen Zahlen sind die vorgegebenen Werte, die roten die
> schon gelösten, während die kleinen Zahlen die verbleibenden
> Möglichkeiten für jedes Feld anzeigen. Acht Zahlen ergaben sich
> zwangsmäßig, aber dann muß zwischen mindestens zweien geraten werden,
> und das geschieht bis zur endgültigen Lösung noch mehrmals.
die 9, findest du nicht ohne Raten raus?
(Wenn in einem Teilquadrat, einer Zeile oder einer Spalte eine Zahl
nur noch einmal als Möglichkeit vorkommt, ist das doch auch schon
eindeutig.)
Marko
Herbert Kleebauer
> Herbert Kleebauer <kl...@unibwm.de> writes:
> >echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
>
> Was ist das denn für ein Betriebssystem, bei dem
> alle Oktette in einem ausführbaren Programm auch
> druckbare Zeichen der ASCII-Abbildung sind?
32 Bit Windows auf x86. Bei 64 Bit Windows werden leider keine 16 Bit Programme
mehr unterstützt (dank AMD). Hoffe Microsoft baut noch einen Softwaresimulator ein.
Herbert Kleebauer
> Herbert Kleebauer schrub:
> > :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
> > @echo off
> > echo
> >
> hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
> > echo
> > ......
>
> Was bietest du hier für einen Virus an? :-)
Dann halt der Sourcecode:
@=$100
bclr.w #10,sr
;***********************************************************************
; read 81 digits from stdin, anything else is ignored, 0 for unknown
;***********************************************************************
move.l #brett,r5
move.l #81,r2
_10: bsr.l getc
sub.b #'0',r0
blo.b _10
beq.b _20
cmp.b #9,r0
bhi.b _10
eor.l r1,r1
bset.l r0,r1
move.l r1,(r5)
br.b _30
_20: move.l #$03fe0000,(r5)
_30: addq.l #4,r5
dbf.l r2,_10
;***********************************************************************
bsr.l display
bsr.l check
bcs.l _err
bsr.l reduce
beq.b _found0
;***********************************************************************
; if not found directly, do one level of recursion of try and error
;***********************************************************************
move.l #brett,r5
move.l #81,r2
_50: move.l (r5),r0
tst.w r0,r0
bne.b _40
lsr.l #16,r0
move.l #2,r1
move.l #9,r4
_60: tst.l r1,r0
beq.b _70
bsr.l save
move.l r1,(r5)
bsr.l reduce
beq.b _found1
bsr.l restore
_70: lsl.l #1,r1
dec.l r4
bne.b _60
_80: lsl.l #16,r0
move.l r0,(r5)
_40: addq.l #4,r5
dbf.l r2,_50
move.l #text4,r0
br.b _130
_found0:move.l #text2,r0
br.b _120
_err: move.l #text1,r0
br.b _130
_found1:move.l #text3,r0
_120: bsr.l display
_130: bsr.l out_text
bsr.l exit
;***********************************************************************
save: movem.l r0-r7,-(sp)
move.l #brett,r5
move.l #brett1,r6
br.b rest1
restore:movem.l r0-r7,-(sp)
move.l #brett1,r5
move.l #brett,r6
rest1: move.l #81,r2
rep_r2 move.l (r5)+-,(r6)+-{s1}
movem.l (sp)+,r0-r7
rts.l
;***********************************************************************
; remove all impossible configurations
; carry: 1: unsolveabel
; 0: solveabel
; zero: 1: solved
; 0: not solved
;***********************************************************************
reduce: movem.l r0-r7,-(sp)
_90: move.l #brett,r5
move.l #81,r2
eor.l r6,r6
_50: move.l (r5),r0
tst.w r0,r0
bne.b _40
orq.l #1,r6
lsr.l #16,r0
move.l #2,r1
eor.l r3,r3
move.l #9,r4
_20: tst.l r1,r0
beq.b _10
move.l r1,(r5)
bsr.l check
bcc.b _70
orq.l #-1,r6
eor.l r1,r0
br.b _10
_70: tst.l r3,r3
bne.b _30
move.l r1,r3
br.b _10
_30: orq.l #-1,r3
_10: lsl.l #1,r1
dec.l r4
bne.b _20
tst.l r3,r3
beq.b _err
bmi.b _80
move.l r3,(r5)
br.b _40
_80: lsl.l #16,r0
move.l r0,(r5)
_40: addq.l #4,r5
dbf.l r2,_50
tst.l r6,r6
bmi.l _90
movem.l (sp)+,r0-r7
bclr.w #0,sr ; carry=0 zero=1(solution found) or 0
rts.l
_err: orq.l #1,r0 ; clear zero flag
movem.l (sp)+,r0-r7
bset.w #0,sr
rts.l
;***********************************************************************
; check if legal
; carry: 0: legal
; 1: illegal
;***********************************************************************
check: movem.l r0-r7,-(sp)
move.l #brett,r5
move.l #9,r2
_40: move.l #8,r3
move.l (r5),r0
move.l r0,r1
_30: add.l (r5,r3*4),r0
or.l (r5,r3*4),r1
dec.l r3
bne.b _30
cmp.w r0,r1
bne.l _err
lsr.l #16,r1
or.l r1,r0
cmp.w #$03fe,r0
bne.l _err
addq.l #9*4,r5
dbf.l r2,_40
move.l #brett,r5
move.l #9,r2
_60: move.l #8,r3
move.l (r5),r0
move.l r0,r1
_50: lea.l (r3,r3*2),r4
lea.l (r4,r4*2),r4
add.l (r5,r4*4),r0
or.l (r5,r4*4),r1
dec.l r3
bne.b _50
cmp.w r0,r1
bne.l _err
lsr.l #16,r1
or.l r1,r0
cmp.w #$03fe,r0
bne.l _err
addq.l #4,r5
dbf.l r2,_60
move.l #brett,r5
move.l #3,r2
_20: move.l #3,r3
_10: move.l (r5),r0
move.l r0,r1
add.l 0*36+1*4.b(r5),r0
or.l 0*36+1*4.b(r5),r1
add.l 0*36+2*4.b(r5),r0
or.l 0*36+2*4.b(r5),r1
add.l 1*36+0*4.b(r5),r0
or.l 1*36+0*4.b(r5),r1
add.l 1*36+1*4.b(r5),r0
or.l 1*36+1*4.b(r5),r1
add.l 1*36+2*4.b(r5),r0
or.l 1*36+2*4.b(r5),r1
add.l 2*36+0*4.b(r5),r0
or.l 2*36+0*4.b(r5),r1
add.l 2*36+1*4.b(r5),r0
or.l 2*36+1*4.b(r5),r1
add.l 2*36+2*4.b(r5),r0
or.l 2*36+2*4.b(r5),r1
cmp.w r0,r1
bne.b _err
lsr.l #16,r1
or.l r1,r0
cmp.w #$03fe,r0
bne.b _err
addq.l #3*4,r5
dec.l r3
bne.b _10
addq.l #2*9*4,r5
dbf.l r2,_20
movem.l (sp)+,r0-r7
bclr.w #0,sr
rts.l
_err: movem.l (sp)+,r0-r7
bset.w #0,sr
rts.l
;***********************************************************************
display:movem.l r0-r7,-(sp)
move.b #13,r0
bsr.l putc
move.b #10,r0
bsr.l putc
move.l #brett,r5
move.l #9,r3
_40: move.l #9,r4
_30: move.l (r5),r1
addq.l #4,r5
move.l #10,r2
move.b #'0',r0
_20: lsr.l #1,r1
bcs.b _10
inc.l r0
dbf.l r2,_20
move.b #'.',r0
_10: bsr.l putc
dec.l r4
bne.b _30
move.b #13,r0
bsr.l putc
move.b #10,r0
bsr.l putc
dec.l r3
bne.b _40
movem.l (sp)+,r0-r7
rts.l
;***********************************************************************
out_text:
movem.l r0-r7,-(sp)
move.l r0,r5
_20: move.b (r5)+-,r0
tst.b r0,r0
beq.b _10
bsr.l putc
br.b _20
_10: movem.l (sp)+,r0-r7
rts.l
;***********************************************************************
;*************** start OS dependent functions **************************
;***********************************************************************
getc: movem.l r0-r7,-(sp)
move.b #$3f,m0
move.w #buf,r1
move.w #1,r2
eor.w r3,r3
trap #$21
movem.l (sp)+,r0-r7
movu.bl buf,r0
rts.l
putc: movem.l r0-r7,-(sp)
move.b r0,buf
move.b #$40,m0
move.w #buf,r1
move.w #1,r2
move.w #1,r3
trap #$21
movem.l (sp)+,r0-r7
rts.l
exit: move.w #$4c00,r0
trap #$21
;***********************************************************************
;***************** end OS dependent functions **************************
;***********************************************************************
text1: dc.b 13,10,"illegal input",0
text2: dc.b 13,10,"directly solved",0
text3: dc.b 13,10,"solved with one recursion",0
text4: dc.b 13,10,"not solveable with one recursion",0
even 4
buf: blk.l 1
brett: blk.l 9*9
brett1: blk.l 9*9
steffen bruentjen
Nein. Das hängt natürlich davon ab, welche Strategien Du implementiert
hast. Bei diesem Rätsel kommt man ohne raten zu müssen noch weiter.
Beispiel #1:
Die 1 im Quadrat mitte/oben und die 1 im Quadrat mitte erzwingen eine
1 im Quadrat mitte/unten in der rechten Spalte. Mit der 1 im Quadrat
rechts/unten muss die 1 im Quadrat mitte/unten im Feld rechts oben
sein.
Steht ja auch schon da, nur nicht in groß: Im gesamten Quadrat findet
sich nur eine 1.
Beispiel #2:
In den drei Quadraten rechts muss eine 1 in jedem genau einmal
vorkommen. Im Quadrat rechts/unten ist sie in der linken Spalte. Im
Quadrat rechts/mitte ist die mittlere Spalte voll, so dass die 1 im
Quadrat rechts/oben in der mittleren Spalte stehen muss. (Deshalb kann
z.B. die 1 im Feld ganz rechts oben gestrichen werden.) Da es außerdem
schon eine 1 in der untersten Zeile im Quadrat mitte/oben gibt, steht
die 1 im Quadrat rechts/oben in der oberen Zeile (mittlere Spalte).
Anzumerken ist, dass die beiden Beispiele zwei unterschiedliche
Strategien zeigen.
schöne grüße, steffen
Thomas Plehn
bewundere die Leute, die durch sowas noch durchfinden. Ich habe mal ein
ähnliches Programm, welches die Rekursion via Backtracking mit dem
einfachen Ausschlussverfahren kombiniert in VB.net geschrieben.
Es ist natürlich wesentlich langsamer, als purer Assembler, schwere
Rätsel dauern schon mal 10sec.
Wer Interesse hat: Download mit Sourcecode hier:
http://www.sourceforge.net/projects/xicalc
Herbert Kleebauer schrieb:
Robin Koch
>> http://nagel-klaus.homepage.t-online.de/Sudoko.jpg
>>
>> Die großen schwarzen Zahlen sind die vorgegebenen Werte, die roten die
>> schon gelösten, während die kleinen Zahlen die verbleibenden
>> Möglichkeiten für jedes Feld anzeigen. Acht Zahlen ergaben sich
>> zwangsmäßig, aber dann muß zwischen mindestens zweien geraten werden,
>> und das geschieht bis zur endgültigen Lösung noch mehrmals.
>
> Ich bin nicht sehr erfahren mit Sudokus, aber in Deiner Lösung sollte es
> jetzt mit der 1 in Reihe7/Spalte6 weitergehen. Das erzwingt danach die 1
> in Reihe8/Spalte2. Weiter habe ich jetzt nicht gemacht, aber vielleicht
> schaust Du Dein Programm nochmal durch.
FACK. Ich bevorzuge andere Rätsel, aber für Sudokus benutze ich meist
"Simple Sudoku" (http://angusj.com/sudoku)[1]. Dort braucht man nicht
raten und noch nicht mal anspruchsvolle Algorithmen anwenden.
[1] Das Programm zeigt einem einerseits die noch möglichen Zahlen für
ein Kästchen, so wie Deins, und es verfügt über Filter, die einem alle
Kästchen anzeigen, in denen die Ziffer n noch möglich ist.
Das gezeigte Rätsel ist nur mit diesen beiden Methoden leicht lösbar.
--
Robin Koch
Es gibt wichtigeres im Leben als beständig dessen
Geschwindigkeit zu erhöhen. - (Mahatma Ghandi)
Herbert Kleebauer
> Herbert Kleebauer <kl...@unibwm.de> writes:
> >>>echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
> >>>[...]
> >>Was ist das denn für ein Betriebssystem, bei dem
> >>alle Oktette in einem ausführbaren Programm auch
> >>druckbare Zeichen der ASCII-Abbildung sind?
> >32 Bit Windows auf x86.
>
> Laut der Wikipädie
>
> http://de.wikipedia.org/wiki/COM-Datei
>
> enthält eine COM-Datei »Code und Daten«, darunter
> x86-Code. Es erscheint mir als praktisch unmöglich,
> daß dies zufällig alles druckbare ASCII-Zeichen sind.
Zufällig ist das sicher nicht. Aber wenn man sich ein bißchen Mühe
gibt, dann schafft man es auch Programme zu schreiben, bei denen
nur Befehle verwendet werden deren Opcode im druckbaren ASCII
Bereich (0x21-0x7e ohne <>|%&!^) liegt.
@echo off
echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
echo hhpbbnpljhoxolnhaigidpllnbkdnhlkfhlflefblffahfUebdfahhfkokh>>sudo.com
echo wPajQJ///MKiF0///M5uqA///k1AmNDRFkH1r0jNl7hNDgekbNKWKgC1bNq>>sudo.com
echo l5///yDUN2OA0b8CpaVyX1///aVCK0///axUUj0///M5uq1///ErLat@L4/>>sudo.com
echo //aZPI////bNqW5I7kplXN0XC3adf/////apP1////aJ7ooVVNcX4///kNa>>sudo.com
Hierbei sind eigentlich nur die ersten zwei Zeilen auf diese Weise geschrieben,
der Rest ist einfach das codierte Sudoko Programm, welches dann vom Code der
ersten zwei Zeilen wieder decodiert wird.
Roland Damm
Klaus Nagel schrub:
> Ich habe vor längerer Zeit ein interaktives
> Sudoku-Lösungsprogramm geschrieben und dieses auf das heutige
> mittelschwere Problem aus der Süddeutschen Zeitung angesetzt:
>
> http://nagel-klaus.homepage.t-online.de/Sudoko.jpg
>
> Die großen schwarzen Zahlen sind die vorgegebenen Werte, die
> roten die schon gelösten, während die kleinen Zahlen die
> verbleibenden Möglichkeiten für jedes Feld anzeigen. Acht
> Zahlen ergaben sich zwangsmäßig, aber dann muß zwischen
> mindestens zweien geraten werden, und das geschieht bis zur
> endgültigen Lösung noch mehrmals.
Angenommen - nicht exakt durchgedacht, ob das dein Programm auch
merken würde, aber folgendes:
im rechten unteren 9er-Block kann die 6 nur noch in der oberen
Zeile (rechts oder links) stehen. Die mittlere Zeile fällt ja
wegen der 6 im links/unten Block aus, die mittlere Spalte fällt
wegen der 6 im Block rechts/mitte aus und die unteren äußeren
Felder, weil da schon was steht.
Ergo wird die 6 im rechts/unten-Block oben stehen, im
links/unten-Block steht sie in der zweiten Zeile,
=> also muss sie im mitte/unten-Block in der unteren Zeile
stehen. Damit ist die Auswahl an Feldern auf denen sie stehen
kann um eins kleiner, also bei dem Ergebnis deiner Auszählung.
Und für diesen Hinweis war kein Raten erforderlich.
Gute Heuristiken gehen wohl stufenlos in Ausprobieren-Strategien
über.
CU Rollo
Roland Damm
Benno Hartwig schrub:
>> Wenn ersteres gelöst ist, geht zweiteres via BruteForce.
>
> Auch Schach ist prinzipiell BruteForce-mäßig
> komplett durchrechenbar.
> Allein es mangelt an der Rechenzeit
> (oder Rechengeschwindigkeit)
>
> Ist es hier ähnlich?
Kommt auf die Aufgabenstellung an: In ein leeres Sudoku-Blatt
kann man auf 9^81 verschiedene Weisen die Ziffern 1..9
eintragen. Das ist sicher zu viel zum durchrechnen. Andererseits
sind extrem viele dieser Möglichkeiten auch schon dann verboten,
bevor das ganze Blatt gefüllt ist.
CU Rollo
Christopher Creutzig
> P.S.: die Diskussion, ob man nun soudoku, sudoku oder suudoku
> schreiben soll, kann man natürlich umschiffen, indem man
> gleich 数獨verwendet.
Nur finde ich nirgends so oder sou als Aussprache für 数. Die erste
Variante fällt m.E. flach. (Aber danke für den Verweis auf 獨 bzw. 独,
jetzt kenne ich endlich auch das Kanji für Deutschland … :-))
--
if all this stuff was simple, we'd
probably be doing something else. -- Daniel Lichtblau, s.m.symbolic
Rupert
> Eher "oder so": versuche Deine Anfragen geschickter zu stellen.
> Etwa so: ...
Solche Antworten auf vernünftig gestellte Fragen habe ich schon öfter
gelesen. Ich will dir hier nicht unterstellen, dass du es nicht gut
meinst. Aber nichtsdestotrotz finde ich solche allgemeinen Motivationen zur
Lüge falsch. Ebenso wie das generelle Misstrauen, dass jemand hier seine
Hausaufgaben gelöst haben möchte. Jeder kann seine Aufgaben so
formulieren, dass es nicht so aussieht, als sei es eine Hausaufgabe. Da
fände ich es doch sogar besser, wenn diese Fragen ehrlich gestellt werden
können. Ich für meinen Teil sehe im übrigen auch gar nicht, warum ich
dafür nicht Lösungshilfen, möglicherweise sogar vollständige Lösungen
geben sollte, wenn ich die Muße dazu hätte. Denn ich glaube nicht, dass es
dem Lernen hinderlich ist.
Rupert
Rupert
> Kommt auf die Aufgabenstellung an: In ein leeres Sudoku-Blatt
> kann man auf 9^81 verschiedene Weisen die Ziffern 1..9
> eintragen. Das ist sicher zu viel zum durchrechnen. Andererseits
> sind extrem viele dieser Möglichkeiten auch schon dann verboten,
> bevor das ganze Blatt gefüllt ist.
die 81 Einträge, die als verschieden angenommen werden, beliebig permutiert
-> 81!
neun Neunerfelder beliebig permutiert
-> 9!*9!
Die spezielle Ziffernbenennung (Permutation) im gesamten Sudoku spielt
keine Rolle für die Struktur
-> 9!
Permutation kompletter Zeilen/Spalten innerhalb dreier horizontal/vertikal
nebeneinander/übereinander angeordneter Blöcke ändert nichts:
--> 9!/3!^6
Permutation ganzer Blockreihen/spalten ändert nichts:
--> 9!/3!^8
Und davon sind noch nicht alle echte Sudokus.
---
Rupert
Rupert
> http://www.wissenschaft-online.de/artikel/833038
Zitat von dort:
>> Dieses Sudoku mit nur 17 Vorgaben gibt ausreichend Anlass zum
>> Grübeln. Es ist eindeutig lösbar
und dann:
>> Aus urheberrechtlichen Gründen können wir Ihnen die Bilder leider nicht
>> online zeigen.
Kann wirklich jemand das Copyright auf ein spezielles
Sudoku beanspruchen? Das fände ich höchst selstsam, und wenn es das
komplizierteste bisher gefundene wäre. Ob er damit auch gleich das Recht
an allen strukturgleichen (zeilen- / spalten- / zeilenblock- /
spaltenblock- / ziffern-permutierten) Sudokus hat?
>
> Gruß
> CN
Gruß
Rupert
Christopher Creutzig
> können. Ich für meinen Teil sehe im übrigen auch gar nicht, warum ich
> dafür nicht Lösungshilfen, möglicherweise sogar vollständige Lösungen
> geben sollte, wenn ich die Muße dazu hätte. Denn ich glaube nicht, dass es
> dem Lernen hinderlich ist.
Es ist dem Lernen sicherlich nicht förderlich, wenn der Lehrer keine
Rückmeldung bekommt, mit welchen Aufgaben die Lernenden aktuell selbst
klarkommen. Bei einem guten Lehrer (und überschaubaren Gruppengrößen)
ist das sogar ausgesprochen hinderlich.
Roland Damm
Rupert schrub:
Und wo ist die Pointe dieser Rechnung? Ist das der Versuch, eine
kleinere Zahl als Abschätzung zu liefern, wie viele Sudokus es
geben könnte?
Es ging IMO darum, es mit dem Computer durzurechnen. Auch einen
verbotenen Schritt als Verboten zu erkennen, kostet den Computer
einen Rechenschritt (gut, kann man so allgemein nicht sagen,
aber ganz vereinfacht schon).
CU Rollo
Tino Raspari
erstellen sein kein Kunststück, wurde ich noch nicht eines besseren
belehrt..
Effektiv beginne ich einfach mein sudoku mit zufälligen zahlen auszufüllen
und achte dabei darauf, das die bedingungen des sudokus eingehalten werden.
leider kommt es dann recht häufig dazu, dass es keine mögliche zahl mehr
gibt. Da mir noch keine besserer Lösung eingefallen ist, fange ich dann
einfach von 0 wieder an, also resete quasi das ganze sudoku, und beginne
von vorn.
Um die absolute zufälligkeit zu garantieren beginne ich jedesmal damit, ein
zufälliges 9er kästchen zu füllen.
Gibt es eine zusätzliche bedingung, die ich beachten muss, oder die ich
ausnutzen kann, um zu bestimmen, wie weit ich zurückgehen muss?
Mfg Tino Raspari
--
-=Computer tun nicht, was sie sollen, sie tun das, was man ihnen sagt.=-
Christopher Creutzig
> Effektiv beginne ich einfach mein sudoku mit zufälligen zahlen auszufüllen
> und achte dabei darauf, das die bedingungen des sudokus eingehalten werden.
> leider kommt es dann recht häufig dazu, dass es keine mögliche zahl mehr
> gibt. Da mir noch keine besserer Lösung eingefallen ist, fange ich dann
> einfach von 0 wieder an, also resete quasi das ganze sudoku, und beginne
> von vorn.
Such einmal nach dem Stichwort „Backtracking“. Ist sowieso ein nicht zu
unterschätzendes Werkzeug im Kasten des Programmierers.
> Gibt es eine zusätzliche bedingung, die ich beachten muss, oder die ich
> ausnutzen kann, um zu bestimmen, wie weit ich zurückgehen muss?
So kurz wie möglich, jeweils einen Schritt.
Roland Damm
Tino Raspari schrub:
> Als ich in meinem Eröffnungspost noch behauptete ein
> ausgefülltest sudoku zu erstellen sein kein Kunststück, wurde
> ich noch nicht eines besseren belehrt..
Wenn du das als Vorgabe so behauptest, dann lässt man das hier
halt gelten...
> Gibt es eine zusätzliche bedingung, die ich beachten muss, oder
> die ich ausnutzen kann, um zu bestimmen, wie weit ich
> zurückgehen muss?
Aus einem Computer-Fachlexikon:
Rekursion: (siehe Rekursion)
*g*
In pseudocode (sonst wäre die Implementation zu einfach:-):
Funktion FülleFeld(Spielfeld)
{
Prüfe ob Spielfeld erlaubt ist
wenn nicht: return.
Prüfe ob Spielfeld komplett gefüllt ist
wenn ja: Lösung gefunden, Programmende.
nXm= zufällig ausgewähltes noch leeres Feld
for i = 1 to 9
Kopiere Spielfeld nach SpielfeldNeu
schreibe in Feld nXm in SpielfeldNeu die Ziffer i
rufe FülleFeld(SpielfeldNeu) auf
endfor
}
Programmstart: Rufe FülleFeld mit einem leeren Spielfeld auf
Spielfeld ist eine Datenstruktur, die das teilgefüllte Feld
beinhaltet. Z.B. einen Array 9*9 mit int-Zahlen drin, 0 steht
dann für leeres Feld.
Dieses Verfahren geht jeweils nur so weit zurück, wie nötig,
zumindest versucht es erst mal, nur wenig zurück zu gehen und
probiert sich systematisch durch. Diverse Optimierungen sind
natürlich möglich (z.B. dumpf alle 9 Ziffern durchgehen ist
verbesserbar). Aber ich denke, das wird auch so schon flott
genug laufen.
CU Rollo
Christian Gollwitzer
> Roland Damm wrote:
>> Herbert Kleebauer schrub:
>>> echo
>>> ......
>> Was bietest du hier für einen Virus an? :-)
>
> Dann halt der Sourcecode:
>
>
> @=$100
> bclr.w #10,sr
Äh, das sieht mir eher wie ein Disassembling als nach Sourcecode aus:)
Aus Spaß hab ich auchmal am Sonntag einen nicht-rekursiven Solver in
Tcl/Tk gebastelt. Die Idee ist eine Art Bucketsort, also Arrays namens
lines, columns, blocks, die enthalten, ob die jeweilige Ziffer schon
gesetzt ist. Die Funktion enum_digits zählt alle Möglichkeiten für ein
Kästchen auf.
Das Programm zeigt den Fortschritt graphisch an. Der Backtrackingsolver
wäre auch leicht zu implementieren, man würde da in den Baum einsteigen,
wo man die wenigsten Möglichkeiten hat.
=========================================
package require Tk
set N 9
set sN 3
proc setup_graphics {} {
font create huge -size 20
frame .board
for {set x 0} {$x<$::N} {incr x} {
for {set y 0} {$y<$::N} {incr y} {
label .board.l$x-$y -textvariable board($x,$y) -font huge
set ::board($x,$y) -
grid .board.l$x-$y -row $y -column $x
}
}
pack .board
frame .control
pack .control
button .control.solve1 -text "Weiter" -command {solve 1}
button .control.solven -text "Durchmarsch" -command {solve all}
label .control.status -textvariable status
pack .control.solve1 .control.solven .control.status -side left
}
proc read_board {name} {
set fd [open $name]
for {set y 0} {$y<$::N} {incr y} {
gets $fd line
set line [string map {" " ""} $line]
for {set x 0} {$x<$::N} {incr x} {
set digit [string range $line $x $x]
if {[digit $digit]} {
set_digit $x $y $digit
}
}
}
close $fd
}
proc set_digit {x y digit} {
set ::board($x,$y) $digit
incr ::lines($y,$digit)
incr ::columns($x,$digit)
set bx [expr {$x/$::sN}]
set by [expr {$y/$::sN}]
incr ::blocks($bx,$by,$digit)
incr ::unfilled -1
}
proc mark {x y color} {
.board.l$x-$y configure -background $color
}
proc setup_counter {} {
# Iteriere über Zeilen, Spalten und Blöcke
# und setze die Counter für die gesetzten Zahlen
for {set digit 1} {$digit<=$::N} {incr digit} {
for {set n 0} {$n<$::N} {incr n} {
set ::lines($n,$digit) 0
set ::columns($n,$digit) 0
}
for {set y 0} {$y<$::sN} {incr y} {
for {set x 0} {$x<$::sN} {incr x} {
set ::blocks($x,$y,$digit) 0
}
}
}
set ::unfilled [expr {$::N*$::N}]
}
proc enum_digits {x y} {
# Gib alle möglichen Zahlen für Position x,y aus
set nums {}
set bx [expr {$x/$::sN}]
set by [expr {$y/$::sN}]
for {set digit 1} {$digit<=$::N} {incr digit} {
if {!$::lines($y,$digit) && !$::columns($x,$digit) &&
!$::blocks($bx,$by,$digit)} {
lappend nums $digit
}
}
return $nums
}
proc digit {what} {
return [string match {[0-9]} $what]
}
proc solve {how} {
# nicht-rekursiver Solver
# sieht nach, ob es eine eindeutige Zahl gibt
# und füllt sie ein
set onesolved 0
for {set x 0} {$x<$::N} {incr x} {
for {set y 0} {$y<$::N} {incr y} {
if {![digit $::board($x,$y)]} {
set possible [enum_digits $x $y]
switch [llength $possible] {
0 {
# No solution
set ::status "Widerspruch bei $x $y"
mark $x $y red
return 2
}
1 {
set_digit $x $y [lindex $possible 0]
set onesolved 1
if {$how=="1"} {
set ::status "Noch $::unfilled"
return 1
}
}
}
}
}
}
if {$::unfilled==0} {
set ::status "Fertig!"
return 0
}
if {$onesolved} {
set ::status "Noch $::unfilled"
} else {
set ::status "Keine eindeutige Lösung"
}
}
setup_graphics
setup_counter
read_board s1.board
=======================================
s1.board:
=======================
--2 81- --4
1-- -2- ---
-67 --- --1
-8- 1-2 --5
--1 --- 2-9
9-- -34 -8-
274 -51 9--
--- 4-- --2
5-3 -68 4--
=======================
Christian Gollwitzer
> Es ging IMO darum, es mit dem Computer durzurechnen. Auch einen
> verbotenen Schritt als Verboten zu erkennen, kostet den Computer
> einen Rechenschritt (gut, kann man so allgemein nicht sagen,
> aber ganz vereinfacht schon).
Nein, das stimmt so nicht. Ich hab auch darüber nachgedacht, es gibt
z.B. Algorithmen, die Permutationen direkt erzeugen (aufzählen). Also
nicht erst 9^81 Möglichkeiten durchprobieren und nachsehen, ob eine
Ziffer doppelt ist, sondern alle 9!*9! Möglichkeiten direkt berechnen.
Wenn man noch die Ziffernbenennung offen lässt, kommt man angeblich auf
9! Möglichkeiten, das sind 362880. (Allerdings habe ich diesen Schritt
jetzt nicht mehr verstanden)
Christian
Tino Raspari
Moin.
Hab das soweit ausprobiert, aber irgendwie läuft das noch nicht....
flott läuft es schon, jedoch liefert es nur 9en in der Ausgabe, was ja nicht
sinn der sache ist.
Ich füge hier ma den Text der Rekursiven Funktion ein, habs in c++
geschrieben:
---------------------------------------------------------------------------------------------
void fill(int localsudoku[3][3][3][3])
{
int fertig=0;
bool stimmtnoch=false;
for(int a=0;a<3;a++)
for(int b=0;b<3;b++)
for(int c=0;c<3;c++)
for(int d=0;d<3;d++)
{
if(localsudoku[a][b][c][d]==0){fertig+=1;stimmtnoch=true;}
else
{
if((
testobzeile(localsudoku[a][b][c][d],a,b,c,d)&&
testobspalte(localsudoku[a][b][c][d],a,b,c,d)&&
testobkasten(localsudoku[a][b][c][d],a,b,c,d))) stimmtnoch=true;
}
}
if(!stimmtnoch)return;
if(fertig==0&&stimmtnoch){return;}
int
kastenzeile=(rand()%3),kastenspalte=(rand()%3),zeile=(rand()%3),spalte=(rand()%3);
for(int i=1;i<10;i++)
{
for(int a=0;a<3;a++)
for(int b=0;b<3;b++)
for(int c=0;c<3;c++)
for(int d=0;d<3;d++)
{sudokuneu[a][b][c][d]=localsudoku[a][b][c][d];}
sudokuneu[kastenzeile][kastenspalte][zeile][spalte]=i;
fill(sudokuneu);
}
}
-----------------------------------------------------------------------------------------------------
zur erklärung: sudokuneu ist global deklariert. die funktionen "testob..."
liefern true falls die zahl nicht noch einmal in der gleichen
zeile/spalte/kasten vorkommt. diese funktionen übernehmen immer die zahl
auf die getestet werden soll und die kompletten koordinaten.
mein sudoku ist in nem vierdimensionalem array gespeichert. die ersten
beiden koods stehen dafür, welcher kasten betrachtet wird und die 2. beiden
koods für die jeweilige zahl im kasten.
Hoffe, irgendjemand findet meinen Fehler....
mfg Tonio Raspari
Tino Raspari
Moin.
---------------------------------------------------------------------------------------------
int
kastenzeile=(rand()%3),kastenspalte=(rand()%3),zeile=(rand()%3),spalte=(rand()%3);
}
-----------------------------------------------------------------------------------------------------
mfg Tino Raspari
Christian Kortes
Ich hab auch Code :D
Beispielaufruf:
./sudoku .................................................................................
Input:
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
Solution:
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2
--------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
static void sudoku_print(unsigned char a[9][9])
{
int i, j;
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if (j != 0)
printf(" ");
printf("%d", a[i][j]);
}
printf("\n");
}
}
static int is_consistent(unsigned char a[9][9], int v, int i, int j)
{
int k, l, bi, bj;
for (k = 0; k < 9; k++)
if (a[k][j] == v || a[i][k] == v)
return 0;
bi = 3 * (i / 3);
bj = 3 * (j / 3);
for (k = 0; k < 3; k++)
for (l = 0; l < 3; l++)
if (a[bi + k][bj + l] == v)
return 0;
return 1;
}
static int sudoku_solve(unsigned char a[9][9])
{
int i, j, v;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
if (a[i][j] == 0)
goto found;
/* a[i][j] != 0 for all i,j */
return 0;
found:
for (v = 1; v <= 9; v++)
if (is_consistent(a, v, i, j)) {
a[i][j] = v;
if (sudoku_solve(a) == 0)
return 0;
a[i][j] = 0;
}
return 1;
}
int main(int argc, char *argv[])
{
int i = 0, j = 0;
unsigned char a[9][9];
char *s;
if (argc != 2) {
fprintf(stderr, "%s: usage: %s STRING\n", argv[0], argv[0]);
exit(EXIT_FAILURE);
}
s = argv[1];
if (strlen(s) != 81) {
fprintf(stderr, "%s: invalid string length (should be 81)\n",
argv[0]);
exit(EXIT_FAILURE);
}
while (*s) {
if (isdigit(*s))
a[i][j] = *s - '0';
else
a[i][j] = 0;
if (++j == 9) {
i++;
j = 0;
}
s++;
}
printf("Input:\n");
sudoku_print(a);
if (sudoku_solve(a) == 0) {
printf("Solution:\n");
sudoku_print(a);
exit(EXIT_SUCCESS);
} else {
printf("No solution found.\n");
exit(EXIT_FAILURE);
}
}
Christian Gollwitzer
Ich habs nicht durchgearbeitet, aber das hier sieht verdächtig aus:
> void fill(int localsudoku[3][3][3][3])
> {
> int fertig=0;
> bool stimmtnoch=false;
> for(int a=0;a<3;a++)
> for(int b=0;b<3;b++)
> for(int c=0;c<3;c++)
> for(int d=0;d<3;d++)
> {
> if(localsudoku[a][b][c][d]==0){fertig+=1;stimmtnoch=true;}
> else
> {
> if((
> testobzeile(localsudoku[a][b][c][d],a,b,c,d)&&
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Die Funktion "testobzeile" bekommt hier nicht localsudoku, sondern nur
einen Integer übergeben??? Die Signatur müsste doch sowas sein wie
bool testobzeile(int brett[3][3][3][3], int x, int y, int z, int w);
> testobspalte(localsudoku[a][b][c][d],a,b,c,d)&&
> testobkasten(localsudoku[a][b][c][d],a,b,c,d)))
... dito
Tino Raspari
> Die Funktion "testobzeile" bekommt hier nicht localsudoku, sondern nur
> einen Integer übergeben??? Die Signatur müsste doch sowas sein wie...
Das liegt daran, dass diese Funktion noch aus einer älteren Funktion stammt.
Sie bestimmt ob die eingegebene Zahl (1. Argument) schon einmal in der
zeile vorkommt. Dafür übernimmt die Funktion die jeweilige zahl von den
koordinaten, und die koordinaten an sich.
ICh werde nochmal neue Funktionen schreiben, aber ich glaube nicht, dass die
Test-funktionen das Problem sind
Bastian Erdnuess
> Moin.
> Hab das soweit ausprobiert, aber irgendwie läuft das noch nicht....
> flott läuft es schon, jedoch liefert es nur 9en in der Ausgabe, was ja nicht
> sinn der sache ist.
> Ich füge hier ma den Text der Rekursiven Funktion ein, habs in c++
> geschrieben:
>
> ------------------------------------------------------------------------------
>
Das ist ja furchbar hässlich! Da muss man sich ja erst mal durch die
ganen Klammerebenen durchkämpfen um zu wissen, was in welcher
Reihenfolge ausgeführt wird. :-(
> void fill(int localsudoku[3][3][3][3])
> {
> int fertig=0;
> bool stimmtnoch=false;
> for(int a=0;a<3;a++)
> for(int b=0;b<3;b++)
> for(int c=0;c<3;c++)
> for(int d=0;d<3;d++)
> {
> if(localsudoku[a][b][c][d]==0){fertig+=1;stimmtnoch=true;}
> else
> {
> if((
> testobzeile(localsudoku[a][b][c][d],a,b,c,d)&&
> testobspalte(localsudoku[a][b][c][d],a,b,c,d)&&
> testobkasten(localsudoku[a][b][c][d],a,b,c,d)))
> stimmtnoch=true;
> }
> }
> if(!stimmtnoch)return;
> if(fertig==0&&stimmtnoch){return;}
Also hier wird dann irgendwann festgestellt, dass du ein vollständig
stimmiges Sudoku gefunden hast, und dann ... (*)
>
> int
> kastenzeile=
> (rand()%3),kastenspalte=(rand()%3),zeile=(rand()%3),spalte=(rand()%3);
[Heißt das, wenn du irgendwann mal eine passende Zahl in z. B.
[1][2][0][1] gefunden hast, überscheibst du die später zufällig
vielleicht einfach wieder und du änderst das ganze Sudoku noch zig mal,
bevor du die letzte fehlende Zahl irgendwann mal erwischst? -- Na Gut]
>
> for(int i=1;i<10;i++)
> {
> for(int a=0;a<3;a++)
> for(int b=0;b<3;b++)
> for(int c=0;c<3;c++)
> for(int d=0;d<3;d++)
> {sudokuneu[a][b][c][d]=localsudoku[a][b][c][d];}
> sudokuneu[kastenzeile][kastenspalte][zeile][spalte]=i;
> fill(sudokuneu);
(*) ... landest du wieder hier und fängst an, die schönen Einträge
systematisch wieder zu überschreiben. Oder?
> }
>
> }
>
> ------------------------------------------------------------------------------
>
> zur erklärung: sudokuneu ist global deklariert. die funktionen "testob..."
> liefern true falls die zahl nicht noch einmal in der gleichen
> zeile/spalte/kasten vorkommt. diese funktionen übernehmen immer die zahl
> auf die getestet werden soll und die kompletten koordinaten.
> mein sudoku ist in nem vierdimensionalem array gespeichert. die ersten
> beiden koods stehen dafür, welcher kasten betrachtet wird und die 2. beiden
> koods für die jeweilige zahl im kasten.
>
> Hoffe, irgendjemand findet meinen Fehler....
Irgendwie glaub ich musst du dir dein Abbruchbedingung (das A und O bei
Rekursionen) nochmal genau durch den Kopf gehen lassen.
Bastian
PS: Das nächste Mal den Code bitte schön formatiert! Wenn die Zeilen zu
lang werden, dann halt z. B. so:
------------------------------------------------------------------------
> int fertig = 0;
> bool stimmtnoch = false;
> for(int a=0; a<3; a++)
> for(int b=0; b<3; b++)
> for(int c=0; c<3; c++)
> for(int d=0; d<3; d++)
> {
// <== <== <== <== <== <== <== <== <== <== <== <== <== <== <== <== <==
> if (localsudoku[a][b][c][d]==0)
{
fertig += 1;
stimmtnoch = true;
}
> else
> {
> if (testobzeile(localsudoku[a][b][c][d],a,b,c,d) &&
> testobspalte(localsudoku[a][b][c][d],a,b,c,d) &&
> testobkasten(localsudoku[a][b][c][d],a,b,c,d) )
{
> stimmtnoch=true;
}
> }
// <== <== <== <== <== <== <== <== <== <== <== <== <== <== <== <== <==
> } // end for
> if (!stimmtnoch) return;
------------------------------------------------------------------------
Dann kann man das Ganze nämlich wenigstens ansatzweise noch "lesen".
(Man tut sich übrigens selten einen Gefallen damit, Klammerebenen ({})
bei for-Schleifen oder if-Blöcken zu sparen!)
Christian Gollwitzer
>
>> Die Funktion "testobzeile" bekommt hier nicht localsudoku, sondern nur
>> einen Integer übergeben??? Die Signatur müsste doch sowas sein wie...
>
> Das liegt daran, dass diese Funktion noch aus einer älteren Funktion stammt.
> Sie bestimmt ob die eingegebene Zahl (1. Argument) schon einmal in der
> zeile vorkommt. Dafür übernimmt die Funktion die jeweilige zahl von den
> koordinaten, und die koordinaten an sich.
Aber wie kann sie das im aktuellen Kontext, sprich im Brett
"localsudoku", wenn sie nicht das ganze Brett bekommt? Du musst ja
testen, ob die Ziffer im aktuellen Brett in der Rekursion erlaubt ist?
> ICh werde nochmal neue Funktionen schreiben, aber ich glaube nicht, dass die
> Test-funktionen das Problem sind
Viel Spaß,
Christian
Bastian Erdnuess
> Tino Raspari schrieb:
> >
> >> Die Funktion "testobzeile" bekommt hier nicht localsudoku, sondern nur
> >> einen Integer übergeben??? Die Signatur müsste doch sowas sein wie...
> >
> > Das liegt daran, dass diese Funktion noch aus einer älteren Funktion stammt.
> > Sie bestimmt ob die eingegebene Zahl (1. Argument) schon einmal in der
> > zeile vorkommt. Dafür übernimmt die Funktion die jeweilige zahl von den
> > koordinaten, und die koordinaten an sich.
>
> Aber wie kann sie das im aktuellen Kontext, sprich im Brett
> "localsudoku", wenn sie nicht das ganze Brett bekommt? Du musst ja
> testen, ob die Ziffer im aktuellen Brett in der Rekursion erlaubt ist?
Globale Variablen: Tino Raspari schrieb:
> zur erklärung: sudokuneu ist global deklariert. die funktionen "testob..."
Das seh ich dann noch einen Fehler (oder zumindest eine Sinnlosigkeit):
fill() wird mit der globalen Variable sudokuneu aufgerufen, bekommt
dabei aber nur die Adresse von sudokuneu und speichert diese in
localsudoku. Anschließend (nach dem Test) wird localsudoku "punktweise"
in sudokuneu kopiert, was aber keinen Unterschied macht, da sudokuneu
und localsudoku ohnehin übereinstimmen (gleicher Bereich im Speicher).
@Timo: Vermutlich bringt das dein ganzes Programm durcheinander.
> > ICh werde nochmal neue Funktionen schreiben, aber ich glaube nicht, dass die
> > Test-funktionen das Problem sind
>
> Viel Spaß,
>
> Christian
Viel Glück!
Bastian
Roland Damm
Christian Kortes schrub:
> Ich hab auch Code :D
>
>
> Beispielaufruf:
> ./sudoku
> .................................................................................
> Input: 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> Solution:
> 1 2 3 4 5 6 7 8 9
> 4 5 6 7 8 9 1 2 3
> 7 8 9 1 2 3 4 5 6
> 2 1 4 3 6 5 8 9 7
> 3 6 5 8 9 7 2 1 4
> 8 9 7 2 1 4 3 6 5
> 5 3 1 6 4 2 9 7 8
> 6 4 2 9 7 8 5 3 1
> 9 7 8 5 3 1 6 4 2
>
> --------------
> ....
Sehr schön, dann hab ich irgendwo einen Fehler drin. Ich hab's
auch mal kurz einzuhacken versucht (und dabei noch auf die
Schnelle auf den Check der 3*3-Felder verzichtet) und mein
Programm es lief ewig.
Also liegt es doch an mir.
CU Rollo
Christian Gollwitzer
> Christian Gollwitzer <Christian....@uni-bayreuth.de> wrote:
>
>> Tino Raspari schrieb:
>>>> Die Funktion "testobzeile" bekommt hier nicht localsudoku, sondern nur
>>>> einen Integer übergeben??? Die Signatur müsste doch sowas sein wie...
>>> Das liegt daran, dass diese Funktion noch aus einer älteren Funktion stammt.
>>> Sie bestimmt ob die eingegebene Zahl (1. Argument) schon einmal in der
>>> zeile vorkommt. Dafür übernimmt die Funktion die jeweilige zahl von den
>>> koordinaten, und die koordinaten an sich.
>> Aber wie kann sie das im aktuellen Kontext, sprich im Brett
>> "localsudoku", wenn sie nicht das ganze Brett bekommt? Du musst ja
>> testen, ob die Ziffer im aktuellen Brett in der Rekursion erlaubt ist?
>
> Globale Variablen: Tino Raspari schrieb:
>
Das ist aber schlecht, wie soll beim backtracking ´denn das alte Brett
wiederhergestellt werden, wenn ein Zug nicht erfolgreich war? Das Brett
muss jeweils lokal sein. Alternativ reicht es natürlich, den getesteten
Zug wieder zu löschen.
Außerdem ist kein Backtracking implementiert, also die passende
Abbruchbedingung fehlt. Die Funktion muss eher so aussehen:
global brett
bool fill() {
gefunden=false
for a,b,c,d
if brett(a,b,c,d)==0 {
gefunden=true
break
}
if (!gefunden) {
// Brett schon voll, also erfolgreich
output(brett) // Ausgeben
return true;
}
// Teste Ziffern 1-9
ging=false
for i=1..9
brett(a,b,c,d)=i
if (gueltig(brett)) {
bool geht=fill()
if (!geht) brett(a,b,c,d)=0
// wieder resetten
else { ging=true; break; }
// ohne break: Alle Lösungen
}
}
return ging;
// dann false, wenn keine Ziffer ging
}
Dann werden im lokalen Kontext nur die Testziffer und die Koordinaten
gespeichert. Alternativ dazu kann man im lokalen Kontext natürlich auch
das Brett abspeichern, so dass es beim backtracking zurückgesezt wird.
Christian
Tino Raspari
Rekursion arbeitende Prog meinerseits... Hab es vorher noch nie gebraucht^^
Vielleicht hätte ich vorher nen paar einfache Rekursive Programme schreiben
sollen, um es erstma zu verstehen, aber ich werde heute einmal das komplete
Programm neu schreiben, -->formatieren(^^) und dann vielleicht noch mal
nachhaken falls mir irgendwas völlig unlogisch ist.
Tino Raspari
will einfach nich....
--------------------------------------------------------------------------
#include <iostream>
using namespace std;
int sudokustimmt[9][9]; //zeile/spalte
bool testobzeile(int zeile, int sudokulocal[9][9])
{
bool stimmt=true;
for(int spalte=0;spalte<9;spalte++)
{
for(int spalte2=0;spalte2<9;spalte2++)
{
if(spalte==spalte2)goto zeile_hier;
if(sudokulocal[zeile][spalte]==sudokulocal[zeile
[spalte2]&&sudokulocal[zeile][spalte]!=0)stimmt=false;
zeile_hier:;
}
}
return stimmt;
}
bool testobspalte(int spalte, int sudokulocal[9][9])
{
bool stimmt=true;
for(int zeile=0;zeile<9;zeile++)
{
for(int zeile2=0;zeile2<9;zeile2++)
{
if(zeile==zeile2)goto spalte_hier;
if(sudokulocal[zeile][spalte]==sudokulocal[zeile2
[spalte]&&sudokulocal[zeile][spalte]!=0)stimmt=false;
spalte_hier:;
}
}
return stimmt;
}
bool testobkasten(int kasten, int sudokulocal[9][9])
{
bool stimmt=true;
switch(kasten)
{
case 1:
{
for(int a=0;a<3;a++)
{for(int b=0;b<3;b++)
{for(int x=0;x<3;x++)
{for(int y=0;y<3;y++)
{
if(a==x&&b==y)goto kasten_hier1;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier1:;
}}}}
break;
}
case 2:
{
for(int a=0;a<3;a++)
{for(int b=3;b<6;b++)
{for(int x=0;x<3;x++)
{for(int y=3;y<6;y++)
{
if(a==x&&b==y)goto kasten_hier2;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier2:;
}}}}
break;
}
case 3:
{
for(int a=0;a<3;a++)
{for(int b=6;b<9;b++)
{for(int x=0;x<3;x++)
{for(int y=6;y<9;y++)
{
if(a==x&&b==y)goto kasten_hier3;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier3:;
}}}}
break;
}
case 4:
{
for(int a=3;a<6;a++)
{for(int b=0;b<3;b++)
{for(int x=3;x<6;x++)
{for(int y=0;y<3;y++)
{
if(a==x&&b==y)goto kasten_hier4;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier4:;
}}}}
break;
}
case 5:
{
for(int a=3;a<6;a++)
{for(int b=3;b<6;b++)
{for(int x=3;x<6;x++)
{for(int y=3;y<6;y++)
{
if(a==x&&b==y)goto kasten_hier5;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier5:;
}}}}
break;
}
case 6:
{
for(int a=3;a<6;a++)
{for(int b=6;b<9;b++)
{for(int x=3;x<6;x++)
{for(int y=6;y<9;y++)
{
if(a==x&&b==y)goto kasten_hier6;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier6:;
}}}}
break;
}
case 7:
{
for(int a=6;a<9;a++)
{for(int b=0;b<3;b++)
{for(int x=6;x<9;x++)
{for(int y=0;y<3;y++)
{
if(a==x&&b==y)goto kasten_hier7;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier7:;
}}}}
break;
}
case 8:
{
for(int a=6;a<9;a++)
{for(int b=3;b<6;b++)
{for(int x=6;x<9;x++)
{for(int y=3;y<6;y++)
{
if(a==x&&b==y)goto kasten_hier8;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier8:;
}}}}
break;
}
case 9:
{
for(int a=6;a<9;a++)
{for(int b=6;b<9;b++)
{for(int x=6;x<9;x++)
{for(int y=6;y<9;y++)
{
if(a==x&&b==y)goto kasten_hier9;
if(sudokulocal[a][b]==sudokulocal[x][y]&&sudokulocal[a
[b]!=0)stimmt=false;
kasten_hier9:;
}}}}
break;
}
}
return stimmt;
}
bool testsudoku(int sudokulocal[9][9])
{
bool stimmt=true;
int counter=0;
for(int a=0;a<9;a++)
{
for(int b=0;b<9;b++)
{
if(sudokulocal[a][b]==0)counter++;
}
}
if (counter==0)goto p2;
for(int zeile=0;zeile<9;zeile++){ if
(!testobzeile(zeile,sudokulocal))stimmt=false; }
for(int spalte=0;spalte<9;spalte++){ if
(!testobspalte(spalte,sudokulocal))stimmt=false; }
for(int kasten=1;kasten<10;kasten++){ if
(!testobkasten(kasten,sudokulocal))stimmt=false; }
p2:
return stimmt;
}
int fill(int sudokulocal[9][9])
{
if(!testsudoku(sudokulocal))return 0;
else
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
sudokustimmt[i][j]==sudokulocal[i][j];
}
}
}
int counter=0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{if(sudokustimmt[i][j]==0)counter++;}
}
if(counter==0)return 0;
p1:
int x=(rand()%9),y=(rand()%9);
if(sudokulocal[x][y]!=0)
{
sudokulocal[x][y]=(rand()%9)+1;
fill(sudokulocal);
}
else
{goto p1;}
}
int main()
{
for(int a=0;a<9;a++)
{for(int b=0;b<9;b++)
sudokustimmt[a][b]=0;}
fill(sudokustimmt);
cout<<"fertig"<<endl;
for(int zeile=0;zeile<9;zeile++)
{
for(int spalte=0;spalte<9;spalte++)
{cout<<sudokustimmt[zeile][spalte]<<" ";}
cout<<endl;
}
return 0;
}
---------------------------------------------------------------------------
ich frage mich langsam echt ob ich irgendwas grundlegend falsch mache....
wenn jemandem etwas auffällt wäre ich zutiefst dankbar^^
mfg T-No.1
Bastian Erdnuess
> Ok, habs nu nochma komplett neu und eigentlich idiotensicher gemacht aber es
> will einfach nich....
Optisch sieht es schon einmal viel besser aus!
> --------------------------------------------------------------------------
> #include <iostream>
> using namespace std;
> int sudokustimmt[9][9]; //zeile/spalte
> [...]
> bool testsudoku(int sudokulocal[9][9])
> [...]
Ich nehm einfach mal an, der Test-Teil wird schon stimmen.
> int fill(int sudokulocal[9][9])
fill bekommt eine Adresse übergeben, an der ein 2-dimensionales
9x9-Array mit Integerwerten steht! Siehe auch:
<http://de.wikipedia.org/wiki/Referenzparameter>
fill wird an 2 Stelle im Code aufgerufen. An (*fill_main*) und
(*fill_fill*).
In (*fill_main*) wird an fill die Adresse von sudokustimmt übergeben.
sudokulocal stimmt also im ersten Aufruf mit sudokustimmt überein!
(*Fehler*)
In (*fill_fill*) wird die gleiche Adresse an fill wieder weitergegeben,
die es im Aufruf zuvor schon bekommen hat. Damit stimmt sudokulocal
immer mit sudokustimmt überein. (*Fehler*)
> {
>
> if(!testsudoku(sudokulocal))return 0;
Ist das sudoku falsch, beendest du den Rekursionsaufruf und springs eine
Ebene zurück. Du landest dann (*hier*), (*oder_hier*) wenn du dich
bereits wieder in der obersten Rekursionsebene befindest.
> else
> {
> for(int i=0;i<9;i++)
> {
> for(int j=0;j<9;j++)
> {
> sudokustimmt[i][j]==sudokulocal[i][j];
Hier (willst du?) kopierst du das im Argument übergebene Array
sudokulocal in das globale Array sudokustimmt. Beide Arrays zeigen aber
auf den selben Bereich im Speicher. Daher ist die Kopie nutzlos.
Abgesehen davon vergleichst du aber sogar nur den Inhalt ('==' vs. '=')
und wirfst das Ergebnis des Vergleichs weg. Hier sollte der Compiler
eigentlich warnen. Evtl. die Warnstufe erhöhen (z. B. -Wall als
Komandozeilenparameter bei gcc).
> }
> }
> }
> int counter=0;
> for(int i=0;i<9;i++)
> {
> for(int j=0;j<9;j++)
> {if(sudokustimmt[i][j]==0)counter++;}
> }
> if(counter==0)return 0;
Wenn du ein richtiges Sudoku gefunden hast, machst du genau das gleiche,
wie wenn das Sudoku falsch war und landest wieder (*hier*)
(*oder_hier*). (*Fehler*)
> p1:
> int x=(rand()%9),y=(rand()%9);
> if(sudokulocal[x][y]!=0)
> {
> sudokulocal[x][y]=(rand()%9)+1;
> fill(sudokulocal);
(*fill_fill*) und (*hier*)
Bist du nun einmal hier gelandet, kommst du auch direkt zum Ende von
fill und landest gleich wieder hier, bis du irgendwann bei (*oder_hier*)
landest.
In diesem Fall beendet das Programm auch, wenn ein Sudoku nicht mehr
stimmt. Du musst also einen Unterschied in der Behandlung der beiden
Fälle "sudoku stimmt nicht" und "sudoku vollständig" vorsehen!
> }
> else
> {goto p1;}
> }
> int main()
> {
> for(int a=0;a<9;a++)
> {for(int b=0;b<9;b++)
> sudokustimmt[a][b]=0;}
> fill(sudokustimmt);
(*fill_main*) und (*oder_hier*)
> cout<<"fertig"<<endl;
> for(int zeile=0;zeile<9;zeile++)
> {
> for(int spalte=0;spalte<9;spalte++)
> {cout<<sudokustimmt[zeile][spalte]<<" ";}
> cout<<endl;
> }
> return 0;
> }
> ---------------------------------------------------------------------------
>
> ich frage mich langsam echt ob ich irgendwas grundlegend falsch mache....
> wenn jemandem etwas auffällt wäre ich zutiefst dankbar^^
Ich empfehle dir dringend globale Variablen und gotos zu vermeinden. Das
sind durchaus sinnvolle und mächtige Konzepte, aber wirklich nur, wenn
man genau weiß, was man macht!
1. Scheinbar ist dir nicht ganz klar, wie Parameter in C(++) übergeben
werden. Arrays werden grundsätzlich nur per Referenz übergeben. Änderst
du daher das Array in einer Funktion, gilt diese Änderung auch außerhalb
der Funktion weiter. (Anders bei "reinen" Typen, wie int oder char).
2. Du musst dir bei der Abbruchbedingung genau überlegen, wie du
unterscheidest, ob ein Sudoku vollständig gelöst oder widersprüchlich
ist. Dann musst du dir überlegen, wie du in beiden Fällen weiter
vorgehst.
Wenn du willst, dass sich sudokustimmt und sudokulocal so verhalten, wie
wie du sie in deinem Code verwendest, dann erreichst du das
folgendermaßen:
int main()
{
int sudokustimmt[9][9];
...
fill (sudokustimmt);
...
}
int fill (int sudokustimmt[9][9])
{
int sudokulocal[9][9];
// kopiere sudokustimmt nach sudokulocal
...
}
Die Abbruchbedingung muss in Etwa die folgende Gestalt haben:
// ändere sudokulocal bis eins von folgendem Eintritt:
// (1) wenns stimmt,
// kopiere es nach sudokustimmt
// wenns vollstaendig ist
return 'gutes_ergebnis';
// wenn nicht vollstaendig
ergebnis = fill(sudokustimmt);
// wenn 'gutes_ergebnis'
// oberer rekursionsebene sagen:
return 'gutes_ergebnis';
// wenn 'schlechtes_ergebnis'
// wieder weiter ändern
// (2) wenn keine korrekte Änderung mehr möglich
return 'schlechtes_ergebnis';
Dabei fällt mir gerade auf: Du kannst die Änderungen nicht rein dem
Zufall überlassen, da du sonst nicht mitkriegst, wenn du in einer
Situation angelangst, in der du zwar noch gültige Änderungen am Sudoku
vornehmen kannst, aber in der keine Änderung mehr zu einer gültigen
Lösung des Sudokus führen kann.
ändere sudokulocal also am sinnvollsten doch so implementieren, dass an
einer zufälligen Stelle alle Zahlen von 1 bis 9 hochgezählt werden. Bist
du dann durch und keine Zahl ist gültig, ist das Sudoku soweit schon
nicht mehr lösbar.
Bastian
PS: Der von mir oben angegebene Weg mit den 'sudokulocal' ist nicht
optimal. Er benötigt viel Speicher. Es gibt auch eine einfache
Möglichkeit darauf zu verzichten, wenn man sich einfach merkt, was für
Veränderungen man vorgenommen hat und diese im Misserfoglsfall einfach
wieder rückgängig macht.
Du kannst dir auch mal <http://mitpress.mit.edu/sicp/> angucken. Da wird
zwar in einer etwas eigenartigen Sprache (Scheme -- LISP-Dialekt)
programmiert, aber ein Hauptaugenmerk liegt auf rekursiver
Programmierung.
Roland Damm
Tino Raspari schrub:
> Ok, habs nu nochma komplett neu und eigentlich idiotensicher
> gemacht aber es will einfach nich....
[x] Du willst den längsten Sudokusolver aller Zeiten schreiben
:-)
Auf die Rekursion wurde ja schon eingegangen, nur noch ein Tip
meinerseits bezüglich:
> bool testobkasten(int kasten, int sudokulocal[9][9])
> {
> bool stimmt=true;
> switch(kasten)
> {
> case 1:
> {
> for(int a=0;a<3;a++)
> {for(int b=0;b<3;b++)
> {for(int x=0;x<3;x++)
> {for(int y=0;y<3;y++)
> {
> if(a==x&&b==y)goto kasten_hier1;
> if(sudokulocal[a][b]==sudokulocal[x
[y]&&sudokulocal[a
> [b]!=0)stimmt=false;
> kasten_hier1:;
> }}}}
> break;
> }
> case 2:
> ............
So wie du die Kasten-Nummer verwendest, geht der Kasten über x
und y einfach über die Wertebereiche:
x: (kasten % 3) * 3 bis (kasten % 3) *3 + 2
y: (kasten/3) *3 bis (kasten/3) *3 + 2
Achtung, überprüfen, dass die Division durch 3 auch wirklich als
Ganzzahloperation ausgeführt wird (in C würde sie, C++ kenne ich
nicht so). Ach ja, die Kastenzählung läuft natürlich von 0 bis
8.
Hast du diese Kastengrenzen einmal berechnet, brauchst du keine
Fallunterschiedung mehr.
2. Hinweis: Du vergleichst den Inhalt jedes Feldes mit jedem
anderen. Das sind 9*9 Vergleiche.
Besser: Lege einen Array (nennen wir ihn a[10] an mit 10
Elementen für die Ziffern 0 (Feld ist leer) bis 9. Der Array
besteht aus int, am Anfang alle Null setzen. Jetzt gehst du die
9 Felder nur einmal durch und zählst für jedes Feld mit dem
Inhalt ziffer a[ziffer] um eins hoch.
Jetzt kontrollierst du, ob irgendein a[i] > 1 ist (mit Ausname
von a[0], weil das hat die Leerfelder gezählt, die dürfen ja
mehrfach vorkommen.
Bei den 9*9 Vergleichen mag das noch nicht so ins Gewicht fallen,
aber wenn du erst mal 256*256 Vergleiche machen müsstest, dann
müsstest du schon auf die Rechenzeit schauen.
Das sähe dann so aus:
bool testobkasten(int kasten, int sudokulocal[9][9])
{
int a[10] = {0,0,0,0,0,0,0,0,0,0};
int x1 = (kasten%3)*3;
int x2 = (kasten%3)*3+2;
int y1 = (kasten/3)*3;
int y2 = (kasten/3)*3+2;
for (y=y1; y<=y2; y++)
{
for(x=x1; x<=x2; x++)
{
// Wenn überhaupt, liegt hier ein Trick: Man indiziere
// einen Array mit dem Inhalt eines anderen Arrays:
a[sudokulocal[x][y]]++;
}
}
for (int i=1; i<10; i++)
{
if (a[i] > 1)
{
// Jetzt mach das was passiert,
// wenn das Sudoku nicht stimmt :
return FALSE;
}
}
return TRUE;
}
Ist allerdings ungetestet.
Für Zeilen und Spalten geht es genauso, nur dass sich dann die x
und y-Schleifen erheblich vereinfachen (man braucht je nur eine)
und weil man die Grenzen nicht so kompliziert ausrechnen muss.
Frohes Gelingen!
CU Rollo
Tino Raspari
habe nu eigentlich alles berücksichtigt, aber wenn ich ihn viele
verschiedene Sudokus erstellen lassen will macht er immer das selbe.
wenn ich das PRogramm zu 2 unterschiedlichen zeitpunkten aufrufe gibt er mir
verschiedene aus, in einer for schleife, immer die gleichen....
es ist echt zum Mäuse melken... ;-)
----------------------------------------------------------------------
#include<iostream>
#include<time.h>
#include<fstream>
using namespace std;
int sudo[9][9];
time_t Zeitstempel;
bool sudotest(int zahl,int x,int y)
{
bool res=true; // Ergebnissspeicher
int i,j; // Zählvariablen
// Testen der Zeile / Spalte
for (i=0;i<9;i++)
{
if (sudo[i][y]==zahl) res = false;
if (sudo[x][i]==zahl) res = false;
}
// Testen des Blocks
for (i=0;i<3;i++)
for (j=0;j<3;j++)
if (sudo[x/3*3+i][y/3*3+j]==zahl) res = false;
return res;
}
void sudoterm()
{
for (int i=0;i<9;i++)
for(int j=0;j<0;j++)
sudo[i][j] = 0;
}
void sudofill(int zahl,int x,int y)
{
// auf Abbruchbedingung testen
bool abbruch=true;
for (int i=0;i<9;i++)
for(int j=0;j<9;j++) if (sudo[i][j]==0) abbruch=false;
if (!abbruch)
{
// testen der Kompatibilität der Zahl
if (sudotest(zahl,x,y)) sudo[x][y]=zahl;
// generieren der Zufallskoordinaten
tm *nun;
time_t Zeitstempel2;
Zeitstempel2 = time(0);
nun = localtime(&Zeitstempel2);
int zeit1=(int)(nun->tm_sec);
x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
//Zufallszahl
zahl=(rand()+zeit1)%9+1;
// Selbstaufruf
sudofill(zahl,x,y);
}
}
void sudocall()
{
for (int i=0;i<9;i++)
{
for (int j=0;j<9;j++) cout<<sudo[j][i]<<" ";
cout<<endl;
}
}
int main()
{
ofstream OF;
OF.open("Sudokus.txt");
for(int i=0;i<100;i++)
{
time_t Zeitstempel;
tm *nun;
Zeitstempel = time(0);
nun = localtime(&Zeitstempel);
int zeit1=(int)(nun->tm_sec);
int x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
int zahl=(rand()+zeit1)%9+1;
sudoterm();
sudofill(zahl,x,y);
sudocall();
for(int j=0;j<9;j++)
{
for(int k=0;k<9;k++)
{OF<<sudo[j][k];}
OF<<endl;
}
OF<<endl;OF<<endl<<"--------------------------------------------------------------------------"<<endl;
}
OF.close();
return 0;
}
------------------------------------------------------------------------
das ist völlig seltsam, langsam zweifle ich an meiner fähigkeit das zu
verstehen wenn ich es lang genug am wickel hab ...
mfg Tino Raspari
Christian Gollwitzer
> Roland Damm schrieb:
>> Es ging IMO darum, es mit dem Computer durzurechnen. Auch einen
>> verbotenen Schritt als Verboten zu erkennen, kostet den Computer
>> einen Rechenschritt (gut, kann man so allgemein nicht sagen,
>> aber ganz vereinfacht schon).
>
> Nein, das stimmt so nicht. Ich hab auch darüber nachgedacht, es gibt
> z.B. Algorithmen, die Permutationen direkt erzeugen (aufzählen). Also
> nicht erst 9^81 Möglichkeiten durchprobieren und nachsehen, ob eine
> Ziffer doppelt ist, sondern alle 9!*9! Möglichkeiten direkt berechnen.
Hab mal kurz gegoogelt, hier hat jemand alle Sudokus aufgezählt, um die
Anzahl zu berechnen:
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf
Es geht also direkt, und es gibt ca. 6.7*10^21 verschiedene Sudokus
(wenn man keinerlei Äquivalenzklassen berücksichtigt).
Christian
Roland Damm
Tino Raspari schrub:
> So...
> habe nu eigentlich alles berücksichtigt, aber wenn ich ihn
> viele verschiedene Sudokus erstellen lassen will macht er immer
> das selbe. wenn ich das PRogramm zu 2 unterschiedlichen
> zeitpunkten aufrufe gibt er mir verschiedene aus, in einer for
> schleife, immer die gleichen....
>
> es ist echt zum Mäuse melken... ;-)
Ohne den Rest angesehen zu haben: Das klingt so, als wie ob den
den Zufallszahlengenerator mit der Zeit initialisierst (ja,
soweit habe ich doch nachgesehen) und dabei nur die Sekunden der
Zeit auswertest.
Ach so, du initialisierst den Zufallszahlengenerator eher
garnicht...
Also am Programmstart einmal srand() oder wie die Funktion heißt
mit der Zeit meinetwegen in Sekunden aufrufen, und dann _nicht_
mehr. Die ganze Rechnerei mit der Zeit kannst du dir dann auch
sparen. Verschiedene Sudokus würde dein Programm nur erzeugen,
wenn zwischen der Erzeugung ein Sekundenwechsel passiert.
CU Rollo
Roland Damm
Tino Raspari schrub:
> ...
Hätte da noch Nachträge....:
> ----------------------------------------------------------------------
> #include<iostream>
> #include<time.h>
> #include<fstream>
> using namespace std;
> int sudo[9][9];
> time_t Zeitstempel;
> bool sudotest(int zahl,int x,int y)
> {
> bool res=true; // Ergebnissspeicher
> int i,j; // Zählvariablen
>
> // Testen der Zeile / Spalte
> for (i=0;i<9;i++)
> {
> if (sudo[i][y]==zahl) res = false;
> if (sudo[x][i]==zahl) res = false;
> }
>
> // Testen des Blocks
> for (i=0;i<3;i++)
> for (j=0;j<3;j++)
> if (sudo[x/3*3+i][y/3*3+j]==zahl) res = false;
Auf die Gefahr hin, dass ich wie ein Meckerer wirke:
Du machst in dieser Schleife 3*3 mal die Rechnung x/3*3 und
y/3*3. Wieso? Das Ergebnis ändert sich doch nicht. Zum glück
kann das ein guter Compiler wegrationalisieren, aber zumindest
nicht langsamer wäre es, das Ergebnis dieser Rechnung vorher
einmal zu berechnen und dann in der Schleife nur zu verwenden.
Aber zumindest falsch ist das nicht, nur eventuell langsamer.
>
> return res;
> }
>
> void sudoterm()
> {
> for (int i=0;i<9;i++)
> for(int j=0;j<0;j++)
> sudo[i][j] = 0;
> }
>
> void sudofill(int zahl,int x,int y)
> {
> // auf Abbruchbedingung testen
> bool abbruch=true;
> for (int i=0;i<9;i++)
> for(int j=0;j<9;j++) if (sudo[i][j]==0) abbruch=false;
>
> if (!abbruch)
> {
> // testen der Kompatibilität der Zahl
> if (sudotest(zahl,x,y)) sudo[x][y]=zahl;
> // generieren der Zufallskoordinaten
> tm *nun;
> time_t Zeitstempel2;
> Zeitstempel2 = time(0);
> nun = localtime(&Zeitstempel2);
> int zeit1=(int)(nun->tm_sec);
> x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
> //Zufallszahl
> zahl=(rand()+zeit1)%9+1;
Wie schon gesagt, diese ganze Rechnerei mit der Zeit kannst du
dir sparen. rand() liefert bei jedem Aufruf ein anderes
Ergebnis, egal ob du jedesmal eine Konstante dazurechnest (und
die Zeit in Sekunden ist eine Konstante, weil so langsam ist das
Programm nicht) oder nicht.
> // Selbstaufruf
> sudofill(zahl,x,y);
Sehe ich das richtig? zahl, x, y sind ausgewürfelt? Was passiert,
wenn der Zufallsgenerator zufälligerweise jedesmal die zahl 1
liefert? Und 1 geht nicht. Hier solltest du systematisch für die
Variable zahl alle Ziffern (0..9) durchprobieren. Entweder ist
eine davon möglich, oder das Sudoku war sowieso schon unlösbar
und auch als solches erkannt. die zahl auswürfeln nutzt dir
nichts.
> }
> }
>
> void sudocall()
> {
> for (int i=0;i<9;i++)
> {
> for (int j=0;j<9;j++) cout<<sudo[j][i]<<" ";
> cout<<endl;
> }
> }
>
> int main()
> {
> ofstream OF;
> OF.open("Sudokus.txt");
> for(int i=0;i<100;i++)
> {
> time_t Zeitstempel;
> tm *nun;
> Zeitstempel = time(0);
> nun = localtime(&Zeitstempel);
> int zeit1=(int)(nun->tm_sec);
> int x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
> int zahl=(rand()+zeit1)%9+1;
Wie gesagt, diese Rechnerei mit der Zeit ist überflüssig. Statt
dessen:
> int main()
> {
> ofstream OF;
> OF.open("Sudokus.txt");
> for(int i=0;i<100;i++)
> {
> time_t Zeitstempel;
> tm *nun;
> Zeitstempel = time(0);
> nun = localtime(&Zeitstempel);
> int zeit1=(int)(nun->tm_sec);
> int x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
> int zahl=(rand()+zeit1)%9+1;
Wie gesagt, diese Rechnerei mit der Zeit ist überflüssig. Statt
dessen:
> int main()
> {
> ofstream OF;
> OF.open("Sudokus.txt");
> for(int i=0;i<100;i++)
> {
> time_t Zeitstempel;
> tm *nun;
> Zeitstempel = time(0);
> nun = localtime(&Zeitstempel);
> int zeit1=(int)(nun->tm_sec);
> int x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
> int zahl=(rand()+zeit1)%9+1;
Wie gesagt, diese Rechnerei mit der Zeit ist überflüssig. Statt
dessen:
> int main()
> {
> ofstream OF;
> OF.open("Sudokus.txt");
srand(time(0)); // mehr Zugriff auf time() braucht es im ganzen
// Programm nicht.
> for(int i=0;i<100;i++)
> {
> int x=(rand()%9),y=(rand()%9);
> int zahl=rand()%9+1;
> sudoterm();
> sudofill(zahl,x,y);
> sudocall();
> for(int j=0;j<9;j++)
> {
> for(int k=0;k<9;k++)
> {OF<<sudo[j][k];}
> OF<<endl;
> }
>
OF<<endl;OF<<endl<<"--------------------------------------------------------------------------"<<endl;
> }
>
Ist auch viel kürzer...:-)
CU Rollo
Tino Raspari
Ich danke dir erst mal für deine Kritik hinsichtlich des restlichen
Programmcodes^^ , doch dieser Punkt ist einer der gut durchdachten.
Das Programm untersucht an dieser Stelle das vorhandene Sudoku auf schon im
gleichen Block eingetragene Zahlen, die der einzutragenden Zahl(zahl)
gleichen.
C++ liefert dadurch, dass Dividend und Divisor einen ganzzahligen
Wertebereich haben, auch ein ganzzahliges Ergebnis. Dies eignet sich
hervorragend für die Ermittlung der jeweiligen Blocknummern, die für diesen
Vergleich erforderlich sind.
x 0 1 2 3 4 5 6 7 8 // Zeile
x/3*3+i 0 0 0 1 1 1 2 2 2 // Blocknummern
Ich würfele die Zahlen aus, da ich maximalen Zufall für die Generierung des
Sudokus erreichen möchte.(Es wird eine zufällig generierte Zahl an einen
zufällig generierten Platz im Array übergeben und nur, wenn sie an dieser
Stelle passt eingetragen, womit das Sudoku zu keinem Zeitpunkt unmöglich
ist.(if (suodkutest()) schreibe Zahl) .
Aus meiner Sicht ist diese Rechnnung nicht überflüssig, denn Zufallsfunktion
scheint, wie von dir beiläufig erwähnt wurde, gleiche Werte zu liefern...
(Dies ist nicht das erste Programm nach dessen Compilierung ich diesen
Verdacht hatte.)
Aus diesem Grund wird also der Bereich der Zufallszahl immer von der Zeit
abhängig gemacht. Inzwischen arbeitet es so dass ich wie von dir erwähnt
den Zufallsgenerator mit srand( (unsigned)time(NULL) ); initialisiere.
Ich frage mich jedoch ob ich ihn nicht lieber vor jedem sudoku neu
initialisieren sollte jeweils dann ja mit einer anderen zeit?! Das wäre
dann ein neuer Seed pro Sudoku, oder arbeitet srand() völlig anders als
dass ich es mir vorstelle?
>
>> int main()
>> {
>> ofstream OF;
>> OF.open("Sudokus.txt");
>
> srand(time(0)); // mehr Zugriff auf time() braucht es im ganzen
> // Programm nicht.
>
>> for(int i=0;i<100;i++)
>> {
>> int x=(rand()%9),y=(rand()%9);
>> int zahl=rand()%9+1;
>> sudoterm();
>> sudofill(zahl,x,y);
>> sudocall();
>> for(int j=0;j<9;j++)
>> {
>> for(int k=0;k<9;k++)
>> {OF<<sudo[j][k];}
>> OF<<endl;
>> }
>>
>
OF<<endl;OF<<endl<<"--------------------------------------------------------------------------"<<endl;
>> }
>>
>
> Ist auch viel kürzer...:-)
>
> CU Rollo
Also wie gesagt, ich danke dir für deine Kritik, denn konstruktive Kritik
ist bei mir immer gern gesehen^^.
Weiterhin muss ich sagen, dass das Programm ursprünglich verschieden Sudokus
lieferte, wenn man es neu kompilierte. Weiterhin trat ein
Speicherzugriffsfehler auf, den ich mir nicht erklären kann.
Er compiliert 1a, und liefert dann (inzwischen) nach dem ausführen immer
einen solchen "Speicherzugriffsfehler".
Früher war das nur manchmal der Fall^^ (?!)
Nun denn!
Roland Damm
Tino Raspari schrub:
>>> // Testen des Blocks
>>> for (i=0;i<3;i++)
>>> for (j=0;j<3;j++)
>>> if (sudo[x/3*3+i][y/3*3+j]==zahl) res = false;
>>
>> Auf die Gefahr hin, dass ich wie ein Meckerer wirke:
>>
>> Du machst in dieser Schleife 3*3 mal die Rechnung x/3*3 und
>> y/3*3. Wieso? Das Ergebnis ändert sich doch nicht. Zum glück
>> kann das ein guter Compiler wegrationalisieren, aber zumindest
>> nicht langsamer wäre es, das Ergebnis dieser Rechnung vorher
>> einmal zu berechnen und dann in der Schleife nur zu verwenden.
>> Aber zumindest falsch ist das nicht, nur eventuell langsamer.
>
> Ich danke dir erst mal für deine Kritik hinsichtlich des
> restlichen Programmcodes^^ , doch dieser Punkt ist einer der
> gut durchdachten.
>
> Das Programm untersucht an dieser Stelle das vorhandene Sudoku
> auf schon im gleichen Block eingetragene Zahlen, die der
> einzutragenden Zahl(zahl) gleichen.
>
> C++ liefert dadurch, dass Dividend und Divisor einen
> ganzzahligen Wertebereich haben, auch ein ganzzahliges
> Ergebnis. Dies eignet sich hervorragend für die Ermittlung der
> jeweiligen Blocknummern, die für diesen Vergleich erforderlich
> sind.
Ja ja, das was du da rechnest, ist ja genau richtig. Meine eher
als Randbemerkung ist halt, dass du bei jedem Schleifendurchlauf
immer wieder neu x/3*3 ausrechnen lässt, obwohl sich x innerhalb
der i/j-Schleife nie ändert. Du führst immer wieder die selbe
Rechnung mit immer wieder dem selben Ergebnis aus. Schneller ist
es, diese Rechnung einmal am Anfang vor der Schleife zu machen
und in der Schleife nurnoch das +i durchzuführen. Aber wie
gesagt, kann gut sein, dass der Compiler das merkt und
wegrationalisiert.
Es geht nur um Geschwindigkeit, nicht um die Richtigkeit.
>> Sehe ich das richtig? zahl, x, y sind ausgewürfelt? Was
>> passiert, wenn der Zufallsgenerator zufälligerweise jedesmal
>> die zahl 1 liefert? Und 1 geht nicht. Hier solltest du
>> systematisch für die Variable zahl alle Ziffern (0..9)
>> durchprobieren. Entweder ist eine davon möglich, oder das
>> Sudoku war sowieso schon unlösbar und auch als solches
>> erkannt. die zahl auswürfeln nutzt dir nichts.
>
> Ich würfele die Zahlen aus, da ich maximalen Zufall für die
> Generierung des Sudokus erreichen möchte.(Es wird eine zufällig
> generierte Zahl an einen zufällig generierten Platz im Array
> übergeben und nur, wenn sie an dieser Stelle passt eingetragen,
> womit das Sudoku zu keinem Zeitpunkt unmöglich ist.(if
> (suodkutest()) schreibe Zahl) .
Die Zufälligkeit wird nicht dadurch gesteigert, dass du die
einzutragende Zahl zufällig auswählst. Es reicht IMO hin, dass
du das Feld auf der eine Zahl einzutragen ist, zufällig
auswählst. Mathematisch begründen kann ich das jetzt nicht, ich
meine das nur so:-)
Das Problem ist: Angenommen du hast ein noch lösbares Sudoku,
wählst jetzt Feld x/y aus und würfelst zufällig eine Zahl i aus,
die auf dieses Feld geschrieben werden soll (b.z.w. getestet
werden soll, ob man sie ohne Regelverstoß dahin schreiben
könnte). Angenommen der Test scheitert, diese Zahl darf dort
nicht hingeschrieben werden. Was jetzt? Du würfelst ein neues
Feld und eine neue Zahl aus. Problem: Was währe, wenn der
Zufallsgenerator exakt die gleichen Zahlen wieder ausspucken
würde, und wieder und wieder? Weil es Zufallszahlen sind, ist
das möglich.
Würdest du hingegen das Feld einmal auswürfeln und dann testen,
welche Zahl dort hin passt (alle 9 Möglichkeiten in einer
Schleife durchgezählt), dann würdest du die mindestens eine
erlaubte Zahl garantiert irgendwann (nach spätestens 9
Versuchen) treffen. Da du aber auswürfelst, kann es passieren,
dass du die eine zulässige Zahl auch nach 100000 Versuchen noch
nicht getroffen hast - unwahrscheinlich, aber möglich.
>> Wie gesagt, diese Rechnerei mit der Zeit ist überflüssig.
>> Statt dessen:
> Aus meiner Sicht ist diese Rechnnung nicht überflüssig, denn
> Zufallsfunktion scheint, wie von dir beiläufig erwähnt wurde,
> gleiche Werte zu liefern... (Dies ist nicht das erste Programm
> nach dessen Compilierung ich diesen Verdacht hatte.)
Das sagt auch die manpage, das ist gewollt. Ist auch gut so, denn
wenn du mit Zufallszahlen rechnest, dann ist es unpraktisch,
wenn ein Fehler im Programm unkontrolliert mal auftritt und mal
nicht. Deswegen liefert die rand()-Funktion immer die gleiche
Zahlenfolge.
Willst du bei jedem Programmlauf eine andere Zahlenfolge haben,
dann nimmst du srand(). srand() initialisiert den
Zufallszahlengenerator mit einem Startwert aus dem die gesamte
daraus resultierende Zahlenfolge klar errechnet werden kann.
Es besteht aber in keinem Fall ein Zusammenhang zwischen einer
Zufallszahl und der darauf folgenden. Deswegen gibt es keinen
Grund, den Zufallszahlengenerator zwischen zwei Aufrufen neu zu
mischen oder eine sich ändernde Konstante draufzurechnen.
Nur wird der Generator beim Programmstart normalerweise immer mit
der selben Zahl (vermutlich 0) initialisiert. Deswegen muss man
ihn, um nicht immer die selben Ergebnisse zu bekommen, am Anfang
mit einer Zufallszahl aus anderer Quelle initialisieren, dazu
kann die Zeit dienen (zufällig ist zwar nicht die Zeit, sondern
der Zeitpunkt des Programmstarts).
Noch anders gesagt:
rand() ist in etwa so definierbar:
int rand()
{
static int oldrand=0;
.....
// Berechne newrand als Funktion von oldrand
oldrand = newrand;
return newrand;
}
also rand() errechnet aus der letzten ausgewählten Zahl die neue
Zahl. Diese Rechnung ist exakt nachvollziehbar, liefert wenn
oldrand das selbe war auch das selbe Ergebnis.
srand() dient dazu, den Wert von oldrand zu setzen.
CU Rollo
Tino Raspari
Aber fällt dir an dem Programm irgendetwas auf, was den
Speicherzugriffsfehler erklären könnte? dass ist zurzeit das dringlichste
Problem, weil es verhindert, dass das Programm läuft^^
Hoffe iwer sieht noch was -.-
Bastian Erdnuess
> void sudofill(int zahl,int x,int y)
> {
static counter = 0;
counter++;
cout << "sudokufill zum "
<< counter
<< ". mal aufgerufen."
<< endl;
> // auf Abbruchbedingung testen
> bool abbruch=true;
> for (int i=0;i<9;i++)
> for(int j=0;j<9;j++) if (sudo[i][j]==0) abbruch=false;
>
> if (!abbruch)
> {
> // testen der Kompatibilität der Zahl
> if (sudotest(zahl,x,y)) sudo[x][y]=zahl;
> // generieren der Zufallskoordinaten
> tm *nun;
> time_t Zeitstempel2;
> Zeitstempel2 = time(0);
> nun = localtime(&Zeitstempel2);
> int zeit1=(int)(nun->tm_sec);
> x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
> //Zufallszahl
> zahl=(rand()+zeit1)%9+1;
> // Selbstaufruf
> sudofill(zahl,x,y);
> }
> }
Schreib mal den obigen Code mit rein. Danach sollte beim Programmstart
das Programm anfangen zu zählen, wie oft sudokufill rekursiv aufgerufen
wird. Irgendwo beim x-tausendsten Aufruf wird es dann abstürzen, weil
irgendwo nicht mehr genug Speicher vorhanden ist. (Falls es nicht so
ist, hab ich gerade keine Idee, woran der Speicherzugriffsfehler liegt.
Vielleicht machst du auch irgendwas mit nem Zeiger falsch.)
Entweder du stellst dann mit irgendwelchen Parametern beim compilieren
ein, dass du mehr Speicher für irgendwas (ist das Heap oder sowas?)
brauchst, oder du rationalisierst deinen Code ein wenig. (Wenn du es
richtig machst, sind höchstens ~1600 Aufrufe notwendig!)
Im Prinzip ist das nämlich ziemlich dämlich, was du da machst: Du wählst
rein zufällig irgend ein Feld aus und schreibst da irgendeine passende
Zahl rein. Aber das ist zum einen ziemlich unnütz, wenn in dem Feld
schon eine passende Zahl drin stand und zum anderen dauert es eine
Ewigkeit, bis du endlich alle Felder erwischt hast (und je weniger
unbeschriebene Felder übrigbleiben, desto unwarscheinlicher ist es, dass
auch noch eine passende Zahl erwischt wird, wenn du das so ein Feld
schon einmal erwischt. Bis du aber zum nächsten mal zu dem gleichen Feld
kommst, hast du das ganze Sudoku schon x-mal geändert. Warum?)
Bastian
PS: C ist ansich keine besonders gute Programmiersprache um Rekursionen
zu programmieren. Oft wir davon abgeraten. Man lernt es aber dennoch, da
man mit Rekursionen ziemlich effektiv arbeiten kann. Allerdings wird
jedesmal bei einem Funktionsaufruf in C ein Speicherrahmen
bereitgestellt um lokale Variablen und die übergebenen Parameter
abzuspeichern. Bereits nach ein paartausend Aufrufen läuft dann im
Normalfall bereits irgendet etwas über.
PPS: Beachte auch Rolands Kommentare! So wie es Roland sagt, geht es mit
dem Zufallsgenerator richtig (einmal srand am Anfang vom Programm, dann
nur noch rand und nix mehr mit time). Auch ist es besser, nicht alles
zufällig zu machen. Such einfach ein Feld, guck ob schon was drin steht
und wenn nicht, dann probier alle möglichen Zahlen auf dem Feld durch,
bis du eine passende gefunden hast (ob du in zufälliger Reihenfolge
testest oder nach System ist erstmal unwichtig). Passt keine Zahl, ist
das Sudoku soweit schon falsch und du musst 'backtracken'. Vielleicht
liest du dir mal was zu Backtracking durch, das ist hier nämlich
wichtig! (In dem letzten Beispiel von mir ist das gerade der Teil mit
'schlechtem_ergebnis'. Den hab ich da nicht zum Spaß reingeschrieben.)
Stephan Lukits
> PS: C ist ansich keine besonders gute Programmiersprache um Rekursionen
Welche Programmiersprach ist denn eine gute Programmiersprache um
Rekursionen zu programmieren.
Wenn ich z.B. in Scheme definiere:
(define (fac n)
(if (=n 0)
1
(* n (fac (- n 1))))
Dann läuft das auch relativ schnell über. Möchte man den linear (mit
der Rekursinstiefe) wachsenden Speicherverbrauch nicht haben, dann
muss man noch eine zweite Variable mitschleifen, die das
Zwischenergebnis enthält. Eine Funktion wird dann zwar immernoch
durch einen Aufruf von sich selbst berechnet, man spricht hierbei aber
oft auch von einem iterativen Prozess:
(define (fac-iter n)
(define (fac n f)
(if (= n 0)
f
(fac (- n 1) (* n f))))
(fac n 1))
Und analoges lässt sich selbstverständlich auch mit C programmieren.
Gruß
Stephan
Roland Damm
Tino Raspari schrub:
Also, wo du nachgefragt hast, woher der Segfault kommt...
Ich hab mir das jetzt noch mal genauer angesehen und bin auf
einige Fehler gestoßen. Ich hab's modifiziert, jetzt läuft das
Programm vermutlich richtig, nur dass innerhalb vieler Minuten
mein Rechner keine Lösung findet. Einen konkreten Grund für den
Segfault habe ich übrigens nicht gefunden...
Also zum Code:
> #include<iostream>
> #include<time.h>
> #include<fstream>
> using namespace std;
> int sudo[9][9];
> time_t Zeitstempel;
Das mit Time bezüglich rand() hatte ich schon erklärt, darauf
gehe ich jetzt nicht mehr ein. Unten gibt's 'nen Link auf die
Arbeitsversion, so wie ich das Programm geändert habe, da ist
das auch geändert.
> bool sudotest(int zahl,int x,int y)
> {
> bool res=true; // Ergebnissspeicher
> int i,j; // Zählvariablen
>
> // Testen der Zeile / Spalte
> for (i=0;i<9;i++)
> {
> if (sudo[i][y]==zahl) res = false;
> if (sudo[x][i]==zahl) res = false;
> }
>
> // Testen des Blocks
> for (i=0;i<3;i++)
> for (j=0;j<3;j++)
> if (sudo[x/3*3+i][y/3*3+j]==zahl) res = false;
>
> return res;
> }
Hier schon mal das erste große Problem: Du testest, ob man die
Zahl hier reinschreiben dürfte, testest dabei aber weder hier
noch sonst irgendwo, ob das Feld überhaupt leer ist. Du
überschreibst also laufen Felder, die schon besetzt sind. Das
könnte man vielleicht ja sogar so machen, nur ist die Erkennung,
ob eine Lösung gefunden wurde einfach die, nachzusehen, ob alle
Felder beschrieben sind. Die Regeln werden beim Test auf fertige
Lösung genau genommen nicht mehr kontrolliert.
>
> void sudoterm()
> {
> for (int i=0;i<9;i++)
> for(int j=0;j<0;j++)
> sudo[i][j] = 0;
> }
>
> void sudofill(int zahl,int x,int y)
> {
> // auf Abbruchbedingung testen
> bool abbruch=true;
> for (int i=0;i<9;i++)
> for(int j=0;j<9;j++) if (sudo[i][j]==0) abbruch=false;
Das hier ist der Test, ob das Sudoku komplett gefüllt ist. Wie
ich inzwischen festgestellt habe, ist die Sache doch
zeitkritischer, als ich dachte. Kommt mir zwar auch komisch vor,
aber wer weiß.
Ein Tip, wie man sowas schneller machen kann, also nicht 81
Felder auf ihren Inhalt überprüfen muss:
void rekursion(int Daten, int Tiefe)
{
....
if (Tiefe == 81)
{
cout << "Lösung gefunden";
}
......
rekursion(Daten, Tiefe+1);
.....
}
Start der Sache:
rekursion(0,0);
Du reichst so die Tiefe der Rekursion immer von einer Ebene der
Rekursion zur nächsten weiter. Jeweils um 1 erhöht. Sollte diese
Zahl mal 81 werden, dann muss das heißen, dass 81 Zahlen
eingetragen sind und das das Blatt somit voll ist. Diese Methode
ist viel einfacher und schneller, also bei jedem Rechenschritt
wieder neu das komplette Spielfeld zu überprüfen.
In meiner Programmversion habe ich das noch nicht eingebaut.
>
> if (!abbruch)
> {
> // testen der Kompatibilität der Zahl
> if (sudotest(zahl,x,y)) sudo[x][y]=zahl;
Wie oben gesagt: Es fehlt der Test, ob das Feld überhaupt leer
war.
Aber noch was viel schlimmeres bahnt sich hier an (noch mal selbe
Zeile):
> if (sudotest(zahl,x,y)) sudo[x][y]=zahl;
^^^^^^^^^^^^^^^
schreibt die Zahl in das Spielfeld. Wo ist die korrespondierende
Zeile, die diese Zahl - falls sie falsch war - wieder aus dem
Spiel entfernt? Gibt es nicht.
> // generieren der Zufallskoordinaten
> tm *nun;
> time_t Zeitstempel2;
> Zeitstempel2 = time(0);
> nun = localtime(&Zeitstempel2);
> int zeit1=(int)(nun->tm_sec);
> x=((rand()+zeit1)%9),y=((rand()+zeit1)%9);
> //Zufallszahl
> zahl=(rand()+zeit1)%9+1;
> // Selbstaufruf
> sudofill(zahl,x,y);
Dabei ergibt sich ein Problem, welches das Programm zwar nicht
funktionslos macht, aber extrem langsam:
Es wird jedesmal ein Feld ausgewürfelt und eine Zahl, die da
eingetragen werden soll. Wie groß ist die Wahrscheinlichkeit bei
einem Sudoku mit z.B. nur noch 3 freien Feldern, dass ein
zulässiger Vorschlag ausgewürfelt wird? Dazu muss eines der 3
von 81 Feldern ausgelost werden und obendrein noch die eine von
9 Ziffern, die auf diesem Feld noch erlaubt ist. Für das letzte
freie Feld lässt sich die Sache einfach ausrechnen: 1:81 für das
richtige noch leere Feld, 1:9 für die richtige Ziffer -> Die
Chance, dass der Zufallsgenerator hier die eine erlaubte Lösung
findet ist 1:729. Da rechnet das Programm eine Menge für nichts
herum. Ich hab zumindest die Auswahl der Ziffer systematisch
machen lassen, siehe meine modifizierte Programmversion unten.
Nun mein Vorschlag:
http://www.schunternet.de/~roland/test/sud3.cpp
Ich hab da noch eine Spielerei eingebaut, die einmal pro Sekunde
den aktuellen Zwiswchenstand des Spielfeldes ausgibt. Dieser
Zwischenstand ist sicher kein lösbares Sudoku, aber man sieht
daran ein bischen, wie sich die Rekursion durchfrisst - und auch
keine Lösung in akzeptabler Zeit findet.
Ach ja, jetzt habe ich Kommentare vergessen:
Zeile 95:
Wenn alle Versuche, das Sudoku weiter zu lösen, fehl schlugen,
dann wird das Feld mit der Eintragung wieder gelöscht und auf
leer gesetzt.
Schau es dir mal an, aber wie gesagt, so wirklich funktionieren
tut es auch noch nicht, da es keine Lösung in akzeptabler Zeit
findet.
Man müsste als nächstes mal den Abbruch-Test frisieren, also das
oben gesagte mit dem Durchreichen der Rekursionstiefe durch die
Rekursionsebenen.
Und man sollte anstatt das Feld für den nächsten Test
auszuwürfeln, besser systematisch vorgehen. Aber das dürfte auch
noch nicht der Bringer sein (das macht man so: man würfelt eine
Zahl n 0 bis 80 aus. Dann zählt man das Spielfeld durch und
nimmt das n-te leere Feld, kommt man beim Zählen über 81, fängt
man wieder vorne an. Auf diese Weise erwischt man ein zufälliges
Feld, aber dennoch garantiert ein freies Feld).
CU Rollo
Bastian Erdnuess
Das Analogon in C wäre:
-----------------------------------------
long double fac(unsigned long n, long double f)
{
if (n == 0) return f;
return fac(n-1, f*n);
}
------------------------------------------
Bis fac(100000,1) geht das noch gut, aber bei fac(110000,1) gibt es ein
'Segmentation fault'. (MacOSX Intel C2D, gcc4, ohne zusätzliche
Parameter).
Scheme hab ich leider nicht hier, da kann ich das nicht testen aber es
müsste deutlich weiter kommen (theoretisch bis der Speicher voll ist -
evtl. gleitpunkt rechnen, da so große Integer langsam sind), weil es
irgendwas macht, das sich "Proper Tail Recursion" (oder so) nennt und
dafür sorgt, das bei den rekursiven Selbstaufrufen nicht jedesmal ein
neuer Speicherrahmen angelegt wird.
In C wäre besser:
-------------------------------------------
long double factorial(unsigned long n)
{
long double f = 1.0;
for (; n != 0; n--) f *= n;
return f;
}
--------------------------------------------
Das Programm läuft dann bis 4 Mrd (habs nicht so lange laufen lassen
sondern vorher irgendwann abgebrochen, das zu lange dauert) ganz durch
(auch wenn es wie das andere bereits ab 1800 'inf' als Ergebnis
ausgibt).
Bastian
Christian Kortes
> Das Analogon in C wäre:
>
> -----------------------------------------
>
> long double fac(unsigned long n, long double f)
> {
> if (n == 0) return f;
> return fac(n-1, f*n);
> }
>
> ------------------------------------------
>
> Bis fac(100000,1) geht das noch gut, aber bei fac(110000,1) gibt es ein
> 'Segmentation fault'. (MacOSX Intel C2D, gcc4, ohne zusätzliche
> Parameter).
Mit Optimierung (-O) erkennt er hier die Endrekursion (GCC: (GNU) 4.0.3
(Ubuntu 4.0.3-1ubuntu5)).
Marc Olschok
> Marc Olschok wrote:
>
> > P.S.: die Diskussion, ob man nun soudoku, sudoku oder suudoku
> > schreiben soll, kann man natürlich umschiffen, indem man
> > gleich 数獨verwendet.
>
> Nur finde ich nirgends so oder sou als Aussprache für 数. Die erste
> Variante fällt m.E. flach. (Aber danke für den Verweis auf 獨 bzw. 独,
> jetzt kenne ich endlich auch das Kanji für Deutschland … :-))
Ich habe mich auch gerade gewundert wieso das zweite Kanji gar nicht so
aussieht, wie ich es gelernt habe(n sollte).
Die gebräuchlichere (und einfachere/modernere) Form ist wohl 独 ,
also insgesamt 数独 .
Für Deutschland würde ich aber eher 独逸 oder 独乙 empfehlen, falls
es mit der Aussprache korrespondieren soll.
Marc
Christopher Creutzig
> Für Deutschland würde ich aber eher 独逸 oder 独乙 empfehlen, falls
> es mit der Aussprache korrespondieren soll.
Auch wenn wir jetzt in dsm nur noch OT sind: Wenn mich nicht alles
tuauscht, haben die Kanji, die Ländern zugeordnet werden, so gut wie nie
etwas mit Aussprache zu tun. Auch wenn amerikanisches Englisch durchaus
mal べいご genannt wird, vermute ich darin eher eine moderne Anlehnung
an die Verwendung des 米 für die USA (mit phonetischer Anlehnung an 英
語, klar). Auch Dinge wie 西 für Spanien oder 葡 für Portugal sind nicht
wirklich phonetisch. Und laut kanjidic steht 独 halt neben „alleine“ und
„spontan“ auch für „Deutschland“. Ich vermute, dass es in dieser
Bedeutung ganz normal ドイツ ausgesprochen wird, aber vielleicht kann
uns da jemand in d.s.k.j erhellen.
--
if all this stuff was simple, we'd
probably be doing something else. -- Daniel Lichtblau, s.m.symbolic
Tino Raspari
meine Rekursion läuft immer noch nich so wie ich das gern hätte...
es will einfach nich funktionieren, und mir will wirklich nichts einfallen,
was daran schuld sein sollte....
der Qt der rekursiven Funktion:
--------------------------------------------------------------------
int sudofill(int zahl,int x,int y)
{
// auf Abbruchbedingung testen
bool abbruch=false;
if(!sudotest(zahl,x,y))
abbruch=true;
if(abbruch)
{return 0;}
else sudo[x][y]=zahl;
hier: //testen ob leer
x=rand()%9;
y=rand()%9;
if(sudo[x][y]!=0)goto hier;
int a;
for(int i=1;i<=9;i++)
{ //rec aufruf mit 1
a=sudofill(i,x,y);
if(!a) //hier hängts, wenn man das weg lässt kommen aber nullen mit
raus..
sudo[x][y]=0;
}
bool keineNullen=false;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{if(sudo[i][j]==0)keineNullen=false;goto nenull;}
if(keineNullen)return 1;
nenull:;
Josef Chmel
> Langsam verzweifle ich...
> meine Rekursion läuft immer noch nich so wie ich das gern hätte...
> es will einfach nich funktionieren, und mir will wirklich nichts einfallen,
> was daran schuld sein sollte....
>
> der Qt der rekursiven Funktion:
>
> --------------------------------------------------------------------
> int sudofill(int zahl,int x,int y)
> {
> // auf Abbruchbedingung testen
> bool abbruch=false;
> if(!sudotest(zahl,x,y))
> abbruch=true;
> if(abbruch)
> {return 0;}
> else sudo[x][y]=zahl;
>
> hier: //testen ob leer
> x=rand()%9;
> y=rand()%9;
> if(sudo[x][y]!=0)goto hier;
Falls oben das letzte Feld sudo[x][y] gefuellt wird, gibt das "goto
hier" eine
Endlosschleife.
>
> int a;
> for(int i=1;i<=9;i++)
> { //rec aufruf mit 1
> a=sudofill(i,x,y);
> if(!a) //hier hängts, wenn man das weg lässt kommen aber nullen mit
> raus..
> sudo[x][y]=0;
> }
>
> bool keineNullen=false;
> for(int i=0;i<9;i++)
> for(int j=0;j<9;j++)
> {if(sudo[i][j]==0)keineNullen=false;goto nenull;}
> if(keineNullen)return 1;
> nenull:;}
>
> --
> -=Computer tun nicht, was sie sollen, sie tun das, was man ihnen sagt.=-
Die boolesche Variable "keineNullen" wird nie auf true gesetzt.
Genaugenommen
wird sofort mit "goto nenull" zum Ende gesprungen und danach nicht
einmal
ein Rueckgabewert zuerueckgegeben.
Den Rest des Codes habe ich mir jetzt nicht mehr so genau angeschaut.
Viel Spass noch.
Gruss Josef