Re: Sudoku
Zitat:
Mein Ansatz wäre: 1. Fange an mit einem leeren Brett (Spielnummer = 0, Faktor = 1) 2. Zähle die Anzahl der möglichen Züge (Anzahl) 3. Wähle einen dieser Züge per Zufall und setze die Zahl (Spielnummer = Spielnummer + Faktor * Zug, Faktor = Faktor * Anzahl) 4. Vereinfache die erhaltene Stellung rein logisch (Verfahren je nach gewähltem Schwierigkeitsgrad) 5. Wenn es noch freie Felder gibt, dann fahre fort mit (2) 6. Fertig. Das nach (3) erhaltene Brett ist ein Rätsel mit genau einer Lösung, die vollkommen logisch ermittelt werden kann (hat man ja gerade in (4) getan). Je nach Schwierigkeitsgrad kann man bei (4) unterschiedlich komplizierte Verfahren einsetzen (Hidden pairs / Pointing pairs / etc.). Will man ein Spiel aus der Nummer wiederherstellen, dann nimmt man bei (3) einfach keine Zufallszahl sondern (Zug = Spielnummer mod Anzahl, Spielnummer = Spielnummer div Anzahl). Hatte allerdings noch nicht die Zeit, dass mal in der Realität auszuprobieren. |
Re: Sudoku
@Flocke:
das ist mein bisheriger Ansatz und setzt eben auch voraus das man alle bekannten Tricks implementiert hat. Schaut man sich aber alle diese Tricks an so kann man sie in wenige Gruppen einteilen. Die meisten schwierigen Tricks basieren aber immer auf der kombinatorischen Analyse, sprich Entscheidungsketten und deren Beweis per Kontradiktion. Algorithmisch heist das das man per Program einen Entscheidungsbaum benutzt der lange Ketten bildet die sich in den meisten Fällen gegenseitig ausschließen. Das Trial & Error Verfahren ist im Grunde so ein Ding, halt rekursiv und nur auf ein Teilproblem beschränkt. Klar per Trial & Error kann jeder selbst mit der simpelsten Lösung, so wie igel457, selbst mit einem ziemlich schlechtem Source das Problem lösen, heutige Computer sind eben leistungsstark. Um aber für den Menschen anspruchsvolle Games zu erzeugen muß der Computer auf logisch lösbaren Kombinationen aufbauen. Schade das ich keine Zeit habe. Und bisher wüsste ich auch nicht mit welchen Datenstrukturen so ein Entscheidungsbaum aufzubauen wäre. Es gibt aber zb. bei der Entwicklung mit FPGA per VHDL Synthesetools die per mathematischen Verfahren riesige Matrizen von boolschen Formeln auf ein Minimum reduzieren können. Das entstehende Resultat aus logischen Verknüpfungen repräsentiert dann den Source des VHDLs und wird in die FPGA Hardware gepresst. Auf grund meiner Erfahrungen muß ich sagen das diese Sythesetools super Arbeit leisten und oft hochkomplexe boolsche Formeln auf unerwartete Weise reduzieren. Eventuell müsste man sich mal in diese Richtung orientieren. Gruß Hagen |
Re: Sudoku
Liste der Anhänge anzeigen (Anzahl: 1)
Nachdem das Thema Sudoku, so scheint es, in aller Munde ist, möchte ich Euch auch meine Version nicht vorenthalten. Sicherlich nicht perfekt aber ....
|
Re: Sudoku
//Edit
Bitte löschen, sollte eine PN werden |
Re: Sudoku
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo, ich habe mich selbst auch einmal an einem Sudoku-Programm versucht
Allerdings habe ich Probleme bei der Überprüfung ob eine Zufallszahl in dem Quadrat schon vorkommt.. Vielleicht könnt ihr mir ja helfen.. MFG Edit: Ich habe einen Kommentar an die Stelle gesetzt wo ich hilfe brauche^^ EDIT 2: KEINER eine Idee? :coder2: |
Re: Sudoku
@NicNacMan:
Folgendes Problem bei deinem Progrämmchen. Die internationalen Sudoku-Standards (jaja, gibt es nicht, aber ich kenne sie so, deswegen muss das ja stimmen, oder? ;)) sehen vor, dass die Diagonalen ebenfalls die übliche Vorschrift (jede Zahl von 1-9 genau einmal enthalten) erfüllen müssen. Oder liege ich da falsch? Zumindest die Rätsel, die ich kenne, waren so aufgebaut. Ansonsten :thumb: . Kann mir vielleicht jemand auch ein Programm mit Quellcode geben, das genau das Gegenteil macht, also nicht das Rätsel löst, sondern eins erstellt, das lösbar ist? Vielen Dank schonmal für eure vielen Antworten... ;) |
Re: Sudoku
Hallo JJAnke88, herzlich Willkommen!
Da in dieser Rubrik ein Programm vorgestellt wird, wäre es gut, wenn du Fragen zur eigenen Umsetzung in einer entsprechenden Delphi-Sparte posten würdest (Multimedia). Das Programm aus dem ersten Beitrag ist übrigens Open-Source, evtl. kannst du dort schon eine mögliche Umsetzung für dein Problem finden. |
Re: Sudoku
@JJAnke88
Ich habe dir die paar Zeilen geschrieben die dir gefehlt haben. Ich habe mir dann deinen restlichen Source noch schnell angeschaut, und bim beim Überprüfen des Quadrates auf Richtigkeit nicht drausgekomen, und habe mir das mal angeschaut. jedefalls enthielt der HilfArray nicht die von dir benötigten Informationen, deshalb habe ich das auch noch umgeschrieben.(Nebenbei noch den Quelltext an dem ich arbeiten usste umformatiert, ich hoffe du kannst ihn so nicht schlechter lesen :wink:, ne echt, an dem musst du arbeiten, das sieht ja schrecklich aus). So müsste die Funktion(pruf) funktionieren.(Ich habe nur die Funktion für die Quadranten angeschaut und umgeschrieben. Ich denke der Rest funktioniert.) Zudem wäre eine Fehlermeldung hilfreich, die Sagt an welcher Stelle der Fehler liegt. Allerdings musst du dich nun mit einem neuen Problem herumschlagen: Es werden nicht Alle Felder ausgefüllt wenn ich auf NewGame drücke, die hälfte der Felder bleibt leer.
Delphi-Quellcode:
Und Bitte halte in Zukunft deinen Quelltext Ordentlicher. Dazu gehört ordentlich Einrücken, und die Begins(Ja, ich weiss, die kann man in bestimmten Fällen weglassen, ist ja ne supersache, aber nicht ÜBERALL WOS NUR GEHT. Das macht den Code sehr schwer Nachvollziehbar wenn überall die end's Fehlen bei for-schleifen.)function CHECK(XKORD,YKORD,AZAHL: BYTE): BOOLEAN; var qx,qy,temp,i,i2: BYTE; begin CHECK := TRUE; {REIHE} for I:=1 to 9 do begin if I <> XKORD then begin if Sudoku[I,Ykord] = AZAHL then begin CHECK := FALSE; Exit; end; end; end; {SPALTE} for I:= 1 to 9 do begin if I <> Ykord then begin if Sudoku[Xkord,i] = AZAHL then begin CHECK := FALSE; EXIT; end; end; end; {QUADRAT} qx:=(xKord-1) div 3 +1; qy:=(yKord-1) div 3 +1; for i:= 1 to 3 do begin for i2:= 1 to 3 do begin if Sudoku[(qx-1)*3+i,(qy-1)*3+i2]=AZahl then begin check:=false; exit; end; end; end; end; /////////////////////////////////////////////////////////////// procedure tform1.pruf; var i,j,x,y,z: BYTE; rechts,unten,xkord,ykord: BYTE; hilfe : ARRAY[1..9] OF BYTE; n,m : BYTE; begin // Initalisierung dzahl := FALSE; xkord := 1; ykord := 1; z:= 0; //REIHE for y:= 1 to 9 do begin for i:=1 to 9 do begin for j:=1 to 9 do begin if j<>i then begin if Zahl[i,y]=Zahl[j,y] then begin dzahl := true; doppelt; exit; end; end; end; end; end; //SPALTE for x:= 1 to 9 do begin for i:= 1 to 9 do begin for j:= 1 to 9 do begin if i<> j then begin if Zahl[x,i] = Zahl[x,j] then begin dzahl := true; doppelt; exit; end; end; end; end; end; //Quadrate for rechts := 1 to 3 do begin for unten := 1 to 3 do begin for x:= 1 to 3 do begin for y:= 1 to 3 do begin case rechts of 1 : xkord := x; 2 : xkord := x+3; 3 : xkord := x+6; end; case unten of 1 : ykord := y; 2 : ykord := y+3; 3 : ykord := y+6; end; for m:= 1 to 3 do begin for n:= 1 to 3 do begin if (m<>x)OR (n<>y) then begin if Zahl[xKord,yKord]=Zahl[(rechts-1)*3+m,(unten-1)*3+n] then begin dzahl := true; doppelt; exit; end; end; end; end; end; end; end; end; if dzahl = false then showmessage('Ihre Lösung ist richtig'); end; Das nächste: hast du den Code eigentlich blind eingetippt? Ohne einmal auf den Monitor zu schauen? Sonst wäre dir sicher aufgefallen, dass du CAPSLOCK eingeschaltet hattes. Der Compiler macht sich daraus zwar keinen Unterschied, aber das menschliche Auge schon. Es ist sehr viel angegnehmer wenn man lowercase(ich meine jetzt hier vor allem Sachen wie end for begin, halt alle reserved words) schreibt. @Filestricker Schau dir mal meine Unit an die ich in diesem Forum gepostet habe(class TSudoku). Damit kannst du im Prinzip Sudokus erzeugen. Vorgehensweise: Du setzt zu Begin per Zufall ein paar werte so, dass Sie die "Sudoku Regeln" nicht verletzen. Dann rufst du die Backtracking Methode auf. Anschliessend Entfernst du zufällig mehrere Felder so, dass es per Heuristik-Algorithmus noch lösbar ist. Dann hast ud ein "gültiges" Sudoku mit nur einer Lösung. Ich werde allerdings diese Funktion in nächster Zeit noch hinzufügen, sodass man die Lösungsfunktionen nicht "zweckentfremden"muss. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 15:50 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz