Sudoku algorithmus
-
Ihr werdet bestimmt über meine Frage lachen
aber es mir wirklich wichtig.
Ich versuche seit geraumer Zeit einen Algorithmus zu entwickeln der mir erlaubt ein Sudoku Rätsel ohne probier verfahren zu lösen. Mein Problem dabei ist nun folgendes...
Ich setze erst alle möglichen Zahlen ein, bis vom logischen überlegen her nur noch möglichkeiten übrig bleiben die man mit nur noch mit probieren raus bekommen kann. mein problem dabei, ich will kein random einsetzen müssen.
Ich möchte das ein Algo mir berechnet welche Zahl zu 100% in jedes einzelne Feld muss um das Sudoku zu lösen...Hat sich vielleicht einer von euch mit diesem oder einem ähnlichen Problem beschäftigt und könnte mir da einen kleinen Tip geben ohne mir gleich alles zu verraten, denn ich würde schon gerne selber alleine auf die idee kommen. Nur leider sind mir meine ansätze ausgegangen
Wäre euch sehr dankbar
Denfius
-
bekommen kann. mein problem dabei, ich will kein random einsetzen müssen.
Das wird wohl ohne nicht gehen, auch bei der Erstellung muss mit Random gearbeitet werden.
-
ich weiß ich hab ja ein Sudoku programm geschrieben das mir Spiele erstellt mit verschiedennen schwierigkeits graden und mir auch erlaubt felder auszudrucken. da arbeite sehr wohl mit random aber beim lösen will ich mal ganz davon weg im moment brauch er noch für ein sudoku feld mit nur wenig ausgefüllten feldern das man nicht einfach so lösen kann noch ca 4 - 9 sec aber das ist mir noch zu lange
wenn ich fertig bin stelle ich gerne meinen Code frei ist eine eigene Class und muss nur in jedes Program mit eingebunden werden.
Man muss nur ein Array übergeben z.B.int sudoku[9][9];mehr muss man nicht machen dann wird in dieses Array mit einem Sudoku feld gefüllt. Beim lösen wird das dann auch gemacht, einfach ein Array mit den Zahlen übergeben und dann werden die restlichen Zahlen dazugeschrieben
-
Dieser Thread wurde von Moderator/in Jansen aus dem Forum VCL/CLX (Borland C++ Builder) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Denfius schrieb:
ich weiß ich hab ja ein Sudoku programm geschrieben das mir Spiele erstellt mit verschiedennen schwierigkeits graden und mir auch erlaubt felder auszudrucken. da arbeite sehr wohl mit random aber beim lösen will ich mal ganz davon weg im moment brauch er noch für ein sudoku feld mit nur wenig ausgefüllten feldern das man nicht einfach so lösen kann noch ca 4 - 9 sec aber das ist mir noch zu lange
Du kannst auch mit so einer "Trial&Error"-Methode durchaus noch viel schneller werden. Mein Backtracking-Sudoku-Löser braucht typischerweise einige 10 Millisekunden, obwohl er im Prinzip auch nur probiert und nichts "berechnet".
-
also mein löser ist jetzt fertig auch wenn ich das nicht so gut finde
das problem ist jetzt nur mein thread läuft nicht weiter wird gestartet läuft einmal durch und hört dann wieder auf. ich bin total am verzweifeln Naja mein Thread sieht folgender maßen aus...
void __fastcall sudoku_loesen::Execute() { if(finish() == true) { FreeOnTerminate = true; } }und
bool __fastcall sudoku_loesen::finish() { set_array(); if(sudo_algo.Finish_SudokuField_Numbers(arr)) { for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++) { if( (F_main->sudoku_save[i][j] != arr[i][j]) && (F_main->sudoku_eigen[i][j] != arr[i][j]) ) { z = (i*9)+j; dynamic_cast<TEdit*>(F_main->Components[z+F_main->vorgabe])->Text = IntToStr(arr[i][j]); dynamic_cast<TEdit*>(F_main->Components[z+F_main->vorgabe])->Font->Color = clYellow; dynamic_cast<TEdit*>(F_main->Components[z+F_main->vorgabe])->ReadOnly = true; } } order = true; return true; }else{ return false; } }was mach ich bloß schon wieder falsch bis vor 5 stunden ging es noch
nix umgestellt nun will er einfach nicht mehr
-
Wie aktuell ist das Problem noch?
Ich habe auch ein Programm geschrieben um Sudokus zu lösen. Dabei findet der Algorithmus die Lösung nicht durch probieren; er löst das Sudoku geschickter.
Wenn es gewünscht wird, kann ich es schildern.
-
es gibt mehrer methoden und vorgehensweien bei der lösunung von sudokue... dise müsste man in nem Sudoku Löser einbinden und dann je nach situation zwischen den methoden wählen....
grüße
-
wäre ein nichtprobierender sudokulöser ein beweis für N=NP?
-
ngleich schrieb:
wäre ein nichtprobierender sudokulöser ein beweis für N=NP?
Äh... Nein?
Wir hatten schon einen Haufen Sudoku-Threads hier und ich verlinke immer wieder gerne hierauf: http://twoday.tuwien.ac.at/alias/stories/9649/
Letztes Mal habe ich auch ein paar andere aufschlussreiche Sachen gezeigt, aber die Forumssuche mag mich nicht, darum vorerst nur obenstehender Link.
-
Naja, selbst wenn man alle constraints für jedes Feld mitführt, so kann es doch Situationen geben, in denen für jedes Feld noch mehr als eine zahl in frage kommt. Dann hilft wohl nur probieren.
-
Auch wenn die Lösung eindeutig ist?
-
Ja, auch dann kann es eine solche Situation geben.
-
Kennst Du ein solches Sudoku und könntest es bitte posten?
-
Ne, ich kenne keines. Aber http://arbeitsblaetter.stangl-taller.at/GEDAECHTNIS/Sudoku.shtml sagt, das auch.
-
Es ist doch wie es Hanar sagt: Die Zahl mag eine andere sein, aber das Spiel lebt vom Muster.
-
hello
ich hab auch grad mal dran gebastelt ein sudoku lösungs ding zu schreiben,
klappt für alle leichten sudokus, jedoch müssen weitere lösungsmechanismen eingebracht werden die schwerere sudokus lösbar machen.
Der Mensch löst sudokus durch logisches abgrenzen.
Somit kann man noch sehr viele weitere lösungsfunktionen mit integrieren,
die das Programm noch nicht beinhaltet.
ich poste mal den code, ist in BC++Builder6://--------------------------------------------------------------------------- #include <vcl.h> #pragma hdrstop #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma link "CSPIN" #pragma resource "*.dfm" TForm1 *Form1; class sudoku{ public: sudoku(){} ~sudoku(){} void initialize() { line1[0] = Form1->CSpinEdit1->Value; line1[1] = Form1->CSpinEdit2->Value; line1[2] = Form1->CSpinEdit3->Value; line1[3] = Form1->CSpinEdit4->Value; line1[4] = Form1->CSpinEdit5->Value; line1[5] = Form1->CSpinEdit6->Value; line1[6] = Form1->CSpinEdit7->Value; line1[7] = Form1->CSpinEdit8->Value; line1[8] = Form1->CSpinEdit9->Value; line2[0] = Form1->CSpinEdit10->Value; line2[1] = Form1->CSpinEdit11->Value; line2[2] = Form1->CSpinEdit12->Value; line2[3] = Form1->CSpinEdit13->Value; line2[4] = Form1->CSpinEdit14->Value; line2[5] = Form1->CSpinEdit15->Value; line2[6] = Form1->CSpinEdit16->Value; line2[7] = Form1->CSpinEdit17->Value; line2[8] = Form1->CSpinEdit18->Value; line3[0] = Form1->CSpinEdit19->Value; line3[1] = Form1->CSpinEdit20->Value; line3[2] = Form1->CSpinEdit21->Value; line3[3] = Form1->CSpinEdit22->Value; line3[4] = Form1->CSpinEdit23->Value; line3[5] = Form1->CSpinEdit24->Value; line3[6] = Form1->CSpinEdit25->Value; line3[7] = Form1->CSpinEdit26->Value; line3[8] = Form1->CSpinEdit27->Value; line4[0] = Form1->CSpinEdit28->Value; line4[1] = Form1->CSpinEdit29->Value; line4[2] = Form1->CSpinEdit30->Value; line4[3] = Form1->CSpinEdit31->Value; line4[4] = Form1->CSpinEdit32->Value; line4[5] = Form1->CSpinEdit33->Value; line4[6] = Form1->CSpinEdit34->Value; line4[7] = Form1->CSpinEdit35->Value; line4[8] = Form1->CSpinEdit36->Value; line5[0] = Form1->CSpinEdit37->Value; line5[1] = Form1->CSpinEdit38->Value; line5[2] = Form1->CSpinEdit39->Value; line5[3] = Form1->CSpinEdit40->Value; line5[4] = Form1->CSpinEdit41->Value; line5[5] = Form1->CSpinEdit42->Value; line5[6] = Form1->CSpinEdit43->Value; line5[7] = Form1->CSpinEdit44->Value; line5[8] = Form1->CSpinEdit45->Value; line6[0] = Form1->CSpinEdit46->Value; line6[1] = Form1->CSpinEdit47->Value; line6[2] = Form1->CSpinEdit48->Value; line6[3] = Form1->CSpinEdit49->Value; line6[4] = Form1->CSpinEdit50->Value; line6[5] = Form1->CSpinEdit51->Value; line6[6] = Form1->CSpinEdit52->Value; line6[7] = Form1->CSpinEdit53->Value; line6[8] = Form1->CSpinEdit54->Value; line7[0] = Form1->CSpinEdit55->Value; line7[1] = Form1->CSpinEdit56->Value; line7[2] = Form1->CSpinEdit57->Value; line7[3] = Form1->CSpinEdit58->Value; line7[4] = Form1->CSpinEdit59->Value; line7[5] = Form1->CSpinEdit60->Value; line7[6] = Form1->CSpinEdit61->Value; line7[7] = Form1->CSpinEdit62->Value; line7[8] = Form1->CSpinEdit63->Value; line8[0] = Form1->CSpinEdit64->Value; line8[1] = Form1->CSpinEdit65->Value; line8[2] = Form1->CSpinEdit66->Value; line8[3] = Form1->CSpinEdit67->Value; line8[4] = Form1->CSpinEdit68->Value; line8[5] = Form1->CSpinEdit69->Value; line8[6] = Form1->CSpinEdit70->Value; line8[7] = Form1->CSpinEdit71->Value; line8[8] = Form1->CSpinEdit72->Value; line9[0] = Form1->CSpinEdit73->Value; line9[1] = Form1->CSpinEdit74->Value; line9[2] = Form1->CSpinEdit75->Value; line9[3] = Form1->CSpinEdit76->Value; line9[4] = Form1->CSpinEdit77->Value; line9[5] = Form1->CSpinEdit78->Value; line9[6] = Form1->CSpinEdit79->Value; line9[7] = Form1->CSpinEdit80->Value; line9[8] = Form1->CSpinEdit81->Value; emptyValuesCounter=81; for(int i=0;i<9;i++) { if(line1[i] == 0)emptyValuesCounter--; if(line2[i] == 0)emptyValuesCounter--; if(line3[i] == 0)emptyValuesCounter--; if(line4[i] == 0)emptyValuesCounter--; if(line5[i] == 0)emptyValuesCounter--; if(line6[i] == 0)emptyValuesCounter--; if(line7[i] == 0)emptyValuesCounter--; if(line8[i] == 0)emptyValuesCounter--; if(line9[i] == 0)emptyValuesCounter--; } // clears the vetctor to true clearResultVector(); // set changes = true changes=true; } // clears the vetctor to true void clearResultVector() { for(int i=0;i<9;i++) actualPossibleValues[i]=true; } // these three functions fill the possibilitie vector with results void checkLine(int lineNr) { switch (lineNr) { case 1: for(int i=0;i<9;i++) if(line1[i]!=0)actualPossibleValues[line1[i]-1]=false;break; case 2: for(int i=0;i<9;i++) if(line2[i]!=0)actualPossibleValues[line2[i]-1]=false;break; case 3: for(int i=0;i<9;i++) if(line3[i]!=0)actualPossibleValues[line3[i]-1]=false;break; case 4: for(int i=0;i<9;i++) if(line4[i]!=0)actualPossibleValues[line4[i]-1]=false;break; case 5: for(int i=0;i<9;i++) if(line5[i]!=0)actualPossibleValues[line5[i]-1]=false;break; case 6: for(int i=0;i<9;i++) if(line6[i]!=0)actualPossibleValues[line6[i]-1]=false;break; case 7: for(int i=0;i<9;i++) if(line7[i]!=0)actualPossibleValues[line7[i]-1]=false;break; case 8: for(int i=0;i<9;i++) if(line8[i]!=0)actualPossibleValues[line8[i]-1]=false;break; case 9: for(int i=0;i<9;i++) if(line9[i]!=0)actualPossibleValues[line9[i]-1]=false;break; } } void checkColumn(int columnNr) { if(line1[columnNr-1]!=0)actualPossibleValues[line1[columnNr-1]-1]=false; if(line2[columnNr-1]!=0)actualPossibleValues[line2[columnNr-1]-1]=false; if(line3[columnNr-1]!=0)actualPossibleValues[line3[columnNr-1]-1]=false; if(line4[columnNr-1]!=0)actualPossibleValues[line4[columnNr-1]-1]=false; if(line5[columnNr-1]!=0)actualPossibleValues[line5[columnNr-1]-1]=false; if(line6[columnNr-1]!=0)actualPossibleValues[line6[columnNr-1]-1]=false; if(line7[columnNr-1]!=0)actualPossibleValues[line7[columnNr-1]-1]=false; if(line8[columnNr-1]!=0)actualPossibleValues[line8[columnNr-1]-1]=false; if(line9[columnNr-1]!=0)actualPossibleValues[line9[columnNr-1]-1]=false; } void checkRect(int rectNr) { switch (rectNr) { case 1: for(int i=0;i<3;i++) { if(line1[i]!=0)actualPossibleValues[line1[i]-1]=false; if(line2[i]!=0)actualPossibleValues[line2[i]-1]=false; if(line3[i]!=0)actualPossibleValues[line3[i]-1]=false; } break; case 2: for(int i=3;i<6;i++) { if(line1[i]!=0)actualPossibleValues[line1[i]-1]=false; if(line2[i]!=0)actualPossibleValues[line2[i]-1]=false; if(line3[i]!=0)actualPossibleValues[line3[i]-1]=false; } break; case 3: for(int i=6;i<9;i++) { if(line1[i]!=0)actualPossibleValues[line1[i]-1]=false; if(line2[i]!=0)actualPossibleValues[line2[i]-1]=false; if(line3[i]!=0)actualPossibleValues[line3[i]-1]=false; } break; case 4: for(int i=0;i<3;i++) { if(line4[i]!=0)actualPossibleValues[line4[i]-1]=false; if(line5[i]!=0)actualPossibleValues[line5[i]-1]=false; if(line6[i]!=0)actualPossibleValues[line6[i]-1]=false; } break; case 5: for(int i=3;i<6;i++) { if(line4[i]!=0)actualPossibleValues[line4[i]-1]=false; if(line5[i]!=0)actualPossibleValues[line5[i]-1]=false; if(line6[i]!=0)actualPossibleValues[line6[i]-1]=false; } break; case 6: for(int i=6;i<9;i++) { if(line4[i]!=0)actualPossibleValues[line4[i]-1]=false; if(line5[i]!=0)actualPossibleValues[line5[i]-1]=false; if(line6[i]!=0)actualPossibleValues[line6[i]-1]=false; } break; case 7: for(int i=0;i<3;i++) { if(line7[i]!=0)actualPossibleValues[line7[i]-1]=false; if(line8[i]!=0)actualPossibleValues[line8[i]-1]=false; if(line9[i]!=0)actualPossibleValues[line9[i]-1]=false; } break; case 8: for(int i=3;i<6;i++) { if(line7[i]!=0)actualPossibleValues[line7[i]-1]=false; if(line8[i]!=0)actualPossibleValues[line8[i]-1]=false; if(line9[i]!=0)actualPossibleValues[line9[i]-1]=false; } break; case 9: for(int i=6;i<9;i++) { if(line7[i]!=0)actualPossibleValues[line7[i]-1]=false; if(line8[i]!=0)actualPossibleValues[line8[i]-1]=false; if(line9[i]!=0)actualPossibleValues[line9[i]-1]=false; } break; } } // shows in cspins void show() { Form1->CSpinEdit1->Value = line1[0]; Form1->CSpinEdit2->Value = line1[1]; Form1->CSpinEdit3->Value = line1[2]; Form1->CSpinEdit4->Value = line1[3]; Form1->CSpinEdit5->Value = line1[4]; Form1->CSpinEdit6->Value = line1[5]; Form1->CSpinEdit7->Value = line1[6]; Form1->CSpinEdit8->Value = line1[7]; Form1->CSpinEdit9->Value = line1[8]; Form1->CSpinEdit10->Value = line2[0]; Form1->CSpinEdit11->Value = line2[1]; Form1->CSpinEdit12->Value = line2[2]; Form1->CSpinEdit13->Value = line2[3]; Form1->CSpinEdit14->Value = line2[4]; Form1->CSpinEdit15->Value = line2[5]; Form1->CSpinEdit16->Value = line2[6]; Form1->CSpinEdit17->Value = line2[7]; Form1->CSpinEdit18->Value = line2[8]; Form1->CSpinEdit19->Value = line3[0]; Form1->CSpinEdit20->Value = line3[1]; Form1->CSpinEdit21->Value = line3[2]; Form1->CSpinEdit22->Value = line3[3]; Form1->CSpinEdit23->Value = line3[4]; Form1->CSpinEdit24->Value = line3[5]; Form1->CSpinEdit25->Value = line3[6]; Form1->CSpinEdit26->Value = line3[7]; Form1->CSpinEdit27->Value = line3[8]; Form1->CSpinEdit28->Value = line4[0]; Form1->CSpinEdit29->Value = line4[1]; Form1->CSpinEdit30->Value = line4[2]; Form1->CSpinEdit31->Value = line4[3]; Form1->CSpinEdit32->Value = line4[4]; Form1->CSpinEdit33->Value = line4[5]; Form1->CSpinEdit34->Value = line4[6]; Form1->CSpinEdit35->Value = line4[7]; Form1->CSpinEdit36->Value = line4[8]; Form1->CSpinEdit37->Value = line5[0]; Form1->CSpinEdit38->Value = line5[1]; Form1->CSpinEdit39->Value = line5[2]; Form1->CSpinEdit40->Value = line5[3]; Form1->CSpinEdit41->Value = line5[4]; Form1->CSpinEdit42->Value = line5[5]; Form1->CSpinEdit43->Value = line5[6]; Form1->CSpinEdit44->Value = line5[7]; Form1->CSpinEdit45->Value = line5[8]; Form1->CSpinEdit46->Value = line6[0]; Form1->CSpinEdit47->Value = line6[1]; Form1->CSpinEdit48->Value = line6[2]; Form1->CSpinEdit49->Value = line6[3]; Form1->CSpinEdit50->Value = line6[4]; Form1->CSpinEdit51->Value = line6[5]; Form1->CSpinEdit52->Value = line6[6]; Form1->CSpinEdit53->Value = line6[7]; Form1->CSpinEdit54->Value = line6[8]; Form1->CSpinEdit55->Value = line7[0]; Form1->CSpinEdit56->Value = line7[1]; Form1->CSpinEdit57->Value = line7[2]; Form1->CSpinEdit58->Value = line7[3]; Form1->CSpinEdit59->Value = line7[4]; Form1->CSpinEdit60->Value = line7[5]; Form1->CSpinEdit61->Value = line7[6]; Form1->CSpinEdit62->Value = line7[7]; Form1->CSpinEdit63->Value = line7[8]; Form1->CSpinEdit64->Value = line8[0]; Form1->CSpinEdit65->Value = line8[1]; Form1->CSpinEdit66->Value = line8[2]; Form1->CSpinEdit67->Value = line8[3]; Form1->CSpinEdit68->Value = line8[4]; Form1->CSpinEdit69->Value = line8[5]; Form1->CSpinEdit70->Value = line8[6]; Form1->CSpinEdit71->Value = line8[7]; Form1->CSpinEdit72->Value = line8[8]; Form1->CSpinEdit73->Value = line9[0]; Form1->CSpinEdit74->Value = line9[1]; Form1->CSpinEdit75->Value = line9[2]; Form1->CSpinEdit76->Value = line9[3]; Form1->CSpinEdit77->Value = line9[4]; Form1->CSpinEdit78->Value = line9[5]; Form1->CSpinEdit79->Value = line9[6]; Form1->CSpinEdit80->Value = line9[7]; Form1->CSpinEdit81->Value = line9[8]; } // returns number if possible else 0 int checkAll(int position) { // count from 0 to 80 clearResultVector(); checkLine((position/9.0)+1); checkColumn((position%9)+1); int rect1 = (position/9.0)+1; int rect2 = (position%9)+1; int rect3; if(rect1 <4) { if(rect2<4)rect3=1; else if(rect2<7)rect3=2; else if(rect2<10)rect3=3; } else if(rect1 <7) { if(rect2<4)rect3=4; else if(rect2<7)rect3=5; else if(rect2<10)rect3=6; } else if(rect1 <10) { if(rect2<4)rect3=7; else if(rect2<7)rect3=8; else if(rect2<10)rect3=9; } checkRect(rect3); // get result int result; bool ok=false; for(int i=0;i<9;i++) { if(actualPossibleValues[i]) { result = i+1; if(ok){result=0;break;} else ok=true; } } return result; } // checks all and kicks ass on the sudoku if possible void sudokize() { for(int i=0;i<81;i++) { int line = i/9.0; int column = i%9; line = ((int) line)+1; int check = checkAll(i); if(check != 0) { switch (line) { case 1:if(line1[column]==0)line1[column]= check;break; case 2:if(line2[column]==0)line2[column]= check;break; case 3:if(line3[column]==0)line3[column]= check;break; case 4:if(line4[column]==0)line4[column]= check;break; case 5:if(line5[column]==0)line5[column]= check;break; case 6:if(line6[column]==0)line6[column]= check;break; case 7:if(line7[column]==0)line7[column]= check;break; case 8:if(line8[column]==0)line8[column]= check;break; case 9:if(line9[column]==0)line9[column]= check;break; } } } show(); } private: // if changes in a round / if no changes => no results possible => break // failure bool changes; // includes the amount of 0 fields int emptyValuesCounter; // includes the possible results bool actualPossibleValues[9]; int line1[9]; int line2[9]; int line3[9]; int line4[9]; int line5[9]; int line6[9]; int line7[9]; int line8[9]; int line9[9]; int column1[9]; int column2[9]; int column3[9]; int column4[9]; int column5[9]; int column6[9]; int column7[9]; int column8[9]; int column9[9]; int rect1[9]; int rect2[9]; int rect3[9]; int rect4[9]; int rect5[9]; int rect6[9]; int rect7[9]; int rect8[9]; int rect9[9]; }; sudoku *sud = new sudoku(); //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- void __fastcall TForm1::Button1Click(TObject *Sender) { sud->initialize(); sud->sudokize(); } //---------------------------------------------------------------------------die initialisierung läuft über die CSPinEdit Objekte der Form
Durchnummeriert von links nach rechts und nach unten durch
-
Hab den Thread nicht gelesen, aber wenn ich den code da oben so sehe
(überfliege) drängt sich mir eine Frage auf.Hast du schonmal was von 2-Dimensionalen Arrays und for-Schleifen gehört?
-
Hallo Leute!
Ich bin Informatik Student und musste in meinem ersten Semester einen Sudoku Löser programmieren. Außerdem habe ich ein paar andere Lösungen gesehen. Daraus kann ich folgern, dass eine der schnellsten und kürzesten Lösungen die sog. Tiefensuche darstellt. Dabei wird aus der Sudoku Matrix ein Baum gebildet, in dem für jedes Eingabefeld alle Möglichen Zahlen in einer Baumstruktur berechnet werden. Wenn es nun (mindestens) ein Weg vom 1 Eingabefeld bis zum Letzten gibt (das ist die Tiefensuche), dann wurde eine Lösung gefunden, ansonsten wird der nächste Baumzweig ausprobiert usw. Damit können auch die mehrdeutigen Sudokus und mit jedem Schwierigkeitsgrad gelöst werden. Die Tiefensuche an sich ist am besten durch eine rekursive fkt. zu lösen. Dabei wird zwar teilweise recht viel Speicher verbraten, dafür passt der Algorithmus auf eine Seite und ist außerdem brutal schnell.
Übrigens funktionieren die meisten Online Löser auf diese weise. Bei eindeutigen Lösungen ist die Peformance im millisikunden bereich. Bei Matrizen mit meheren Lösungen und ungünstiger belegung kann der Code schon mal 30 Sekunden arbeiten. Dies kann bei den Online Lösern teilweise zur 100% Serverauslastung führen, wenn er dies nicht abfängt.
Dafür gibt es aber auch zahlreiche Verbesserungen, wie bspw. zuerst die Felder betrachten, bei denen die wenigsten Möglichkeiten existieren.Bei weiterem Interesse kann ich den Quellcode gerne posten. Aber da fehlt dann irgend wo die Motivation, oder?
mfg,
Alexej
-
hab da mal vor geraumer zeit in prolog was gemacht. löst einfache sudokus(rein durch logik, kein probieren)
aber nachdem ich dann festgstellt habe, dass es funktioniert, hab ich dann nicht weiter gemacht und weitere stratgien eingebaut ... motivationsverlust
n([1,2,3,4,5,6,7,8,9]). differenz_(X,[A|[]],B):-delete(X,A,B). differenz_(X,[_|_],X). diff_(X,[A1|[]],B):-differenz_(X,A1,B). diff_(X,[A1|A],B):-differenz_(X,A1,X1),diff_(X1,A,B). diff([A,B,C,D,E,F,G,H,I],[X1,X2,X3,X4,X5,X6,X7,X8,X9]):- diff_(A,[B,C,D,E,F,G,H,I],X1), diff_(B,[A,C,D,E,F,G,H,I],X2), diff_(C,[A,B,D,E,F,G,H,I],X3), diff_(D,[A,B,C,E,F,G,H,I],X4), diff_(E,[A,B,C,D,F,G,H,I],X5), diff_(F,[A,B,C,D,E,G,H,I],X6), diff_(G,[A,B,C,D,E,F,H,I],X7), diff_(H,[A,B,C,D,E,F,G,I],X8), diff_(I,[A,B,C,D,E,F,G,H],X9). %n(N),diff([[5],[3],[4],[6],N,[8],[9],[1],[2]],[A,B,C,D,E,F,G,H,I]). %n(N),diff([[5],[3],[4],[6],N,[8],[9],[1],[2]],[_,_,_,_,E,_,_,_,_]). %n(N),diff_all([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],[1],[4],[2],[3]],[[4],[2],[6],[8],[5],[3],[7],[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). sudoku_([[[A1|[]],[A2|[]],[A3|[]],[A4|[]],[A5|[]],[A6|[]],[A7|[]],[A8|[]],[A9|[]]], [[B1|[]],[B2|[]],[B3|[]],[B4|[]],[B5|[]],[B6|[]],[B7|[]],[B8|[]],[B9|[]]], [[C1|[]],[C2|[]],[C3|[]],[C4|[]],[C5|[]],[C6|[]],[C7|[]],[C8|[]],[C9|[]]], [[D1|[]],[D2|[]],[D3|[]],[D4|[]],[D5|[]],[D6|[]],[D7|[]],[D8|[]],[D9|[]]], [[E1|[]],[E2|[]],[E3|[]],[E4|[]],[E5|[]],[E6|[]],[E7|[]],[E8|[]],[E9|[]]], [[F1|[]],[F2|[]],[F3|[]],[F4|[]],[F5|[]],[F6|[]],[F7|[]],[F8|[]],[F9|[]]], [[G1|[]],[G2|[]],[G3|[]],[G4|[]],[G5|[]],[G6|[]],[G7|[]],[G8|[]],[G9|[]]], [[H1|[]],[H2|[]],[H3|[]],[H4|[]],[H5|[]],[H6|[]],[H7|[]],[H8|[]],[H9|[]]], [[I1|[]],[I2|[]],[I3|[]],[I4|[]],[I5|[]],[I6|[]],[I7|[]],[I8|[]],[I9|[]]]], [[A1,A2,A3,A4,A5,A6,A7,A8,A9], [B1,B2,B3,B4,B5,B6,B7,B8,B9], [C1,C2,C3,C4,C5,C6,C7,C8,C9], [D1,D2,D3,D4,D5,D6,D7,D8,D9], [E1,E2,E3,E4,E5,E6,E7,E8,E9], [F1,F2,F3,F4,F5,F6,F7,F8,F9], [G1,G2,G3,G4,G5,G6,G7,G8,G9], [H1,H2,H3,H4,H5,H6,H7,H8,H9], [I1,I2,I3,I4,I5,I6,I7,I8,I9]]). sudoku_([[A1,A2,A3,A4,A5,A6,A7,A8,A9], [B1,B2,B3,B4,B5,B6,B7,B8,B9], [C1,C2,C3,C4,C5,C6,C7,C8,C9], [D1,D2,D3,D4,D5,D6,D7,D8,D9], [E1,E2,E3,E4,E5,E6,E7,E8,E9], [F1,F2,F3,F4,F5,F6,F7,F8,F9], [G1,G2,G3,G4,G5,G6,G7,G8,G9], [H1,H2,H3,H4,H5,H6,H7,H8,H9], [I1,I2,I3,I4,I5,I6,I7,I8,I9]], [[ZA1,ZA2,ZA3,ZA4,ZA5,ZA6,ZA7,ZA8,ZA9], [ZB1,ZB2,ZB3,ZB4,ZB5,ZB6,ZB7,ZB8,ZB9], [ZC1,ZC2,ZC3,ZC4,ZC5,ZC6,ZC7,ZC8,ZC9], [ZD1,ZD2,ZD3,ZD4,ZD5,ZD6,ZD7,ZD8,ZD9], [ZE1,ZE2,ZE3,ZE4,ZE5,ZE6,ZE7,ZE8,ZE9], [ZF1,ZF2,ZF3,ZF4,ZF5,ZF6,ZF7,ZF8,ZF9], [ZG1,ZG2,ZG3,ZG4,ZG5,ZG6,ZG7,ZG8,ZG9], [ZH1,ZH2,ZH3,ZH4,ZH5,ZH6,ZH7,ZH8,ZH9], [ZI1,ZI2,ZI3,ZI4,ZI5,ZI6,ZI7,ZI8,ZI9]]):-write(go), %Zeilen diff([A1,A2,A3,A4,A5,A6,A7,A8,A9],[XA1,XA2,XA3,XA4,XA5,XA6,XA7,XA8,XA9]), diff([B1,B2,B3,B4,B5,B6,B7,B8,B9],[XB1,XB2,XB3,XB4,XB5,XB6,XB7,XB8,XB9]), diff([C1,C2,C3,C4,C5,C6,C7,C8,C9],[XC1,XC2,XC3,XC4,XC5,XC6,XC7,XC8,XC9]), diff([D1,D2,D3,D4,D5,D6,D7,D8,D9],[XD1,XD2,XD3,XD4,XD5,XD6,XD7,XD8,XD9]), diff([E1,E2,E3,E4,E5,E6,E7,E8,E9],[XE1,XE2,XE3,XE4,XE5,XE6,XE7,XE8,XE9]), diff([F1,F2,F3,F4,F5,F6,F7,F8,F9],[XF1,XF2,XF3,XF4,XF5,XF6,XF7,XF8,XF9]), diff([G1,G2,G3,G4,G5,G6,G7,G8,G9],[XG1,XG2,XG3,XG4,XG5,XG6,XG7,XG8,XG9]), diff([H1,H2,H3,H4,H5,H6,H7,H8,H9],[XH1,XH2,XH3,XH4,XH5,XH6,XH7,XH8,XH9]), diff([I1,I2,I3,I4,I5,I6,I7,I8,I9],[XI1,XI2,XI3,XI4,XI5,XI6,XI7,XI8,XI9]), %Spalten diff([XA1,XB1,XC1,XD1,XE1,XF1,XG1,XH1,XI1],[YA1,YB1,YC1,YD1,YE1,YF1,YG1,YH1,YI1]), diff([XA2,XB2,XC2,XD2,XE2,XF2,XG2,XH2,XI2],[YA2,YB2,YC2,YD2,YE2,YF2,YG2,YH2,YI2]), diff([XA3,XB3,XC3,XD3,XE3,XF3,XG3,XH3,XI3],[YA3,YB3,YC3,YD3,YE3,YF3,YG3,YH3,YI3]), diff([XA4,XB4,XC4,XD4,XE4,XF4,XG4,XH4,XI4],[YA4,YB4,YC4,YD4,YE4,YF4,YG4,YH4,YI4]), diff([XA5,XB5,XC5,XD5,XE5,XF5,XG5,XH5,XI5],[YA5,YB5,YC5,YD5,YE5,YF5,YG5,YH5,YI5]), diff([XA6,XB6,XC6,XD6,XE6,XF6,XG6,XH6,XI6],[YA6,YB6,YC6,YD6,YE6,YF6,YG6,YH6,YI6]), diff([XA7,XB7,XC7,XD7,XE7,XF7,XG7,XH7,XI7],[YA7,YB7,YC7,YD7,YE7,YF7,YG7,YH7,YI7]), diff([XA8,XB8,XC8,XD8,XE8,XF8,XG8,XH8,XI8],[YA8,YB8,YC8,YD8,YE8,YF8,YG8,YH8,YI8]), diff([XA9,XB9,XC9,XD9,XE9,XF9,XG9,XH9,XI9],[YA9,YB9,YC9,YD9,YE9,YF9,YG9,YH9,YI9]), %Quadrat diff([YA1,YB1,YC1,YA2,YB2,YC2,YA3,YB3,YC3],[UA1,UB1,UC1,UA2,UB2,UC2,UA3,UB3,UC3]), diff([YA4,YB4,YC4,YA5,YB5,YC5,YA6,YB6,YC6],[UA4,UB4,UC4,UA5,UB5,UC5,UA6,UB6,UC6]), diff([YA7,YB7,YC7,YA8,YB8,YC8,YA9,YB9,YC9],[UA7,UB7,UC7,UA8,UB8,UC8,UA9,UB9,UC9]), diff([YD1,YE1,YF1,YD2,YE2,YF2,YD3,YE3,YF3],[UD1,UE1,UF1,UD2,UE2,UF2,UD3,UE3,UF3]), diff([YD4,YE4,YF4,YD5,YE5,YF5,YD6,YE6,YF6],[UD4,UE4,UF4,UD5,UE5,UF5,UD6,UE6,UF6]), diff([YD7,YE7,YF7,YD8,YE8,YF8,YD9,YE9,YF9],[UD7,UE7,UF7,UD8,UE8,UF8,UD9,UE9,UF9]), diff([YG1,YH1,YI1,YG2,YH2,YI2,YG3,YH3,YI3],[UG1,UH1,UI1,UG2,UH2,UI2,UG3,UH3,UI3]), diff([YG4,YH4,YI4,YG5,YH5,YI5,YG6,YH6,YI6],[UG4,UH4,UI4,UG5,UH5,UI5,UG6,UH6,UI6]), diff([YG7,YH7,YI7,YG8,YH8,YI8,YG9,YH9,YI9],[UG7,UH7,UI7,UG8,UH8,UI8,UG9,UH9,UI9]), sudoku_([[UA1,UA2,UA3,UA4,UA5,UA6,UA7,UA8,UA9], [UB1,UB2,UB3,UB4,UB5,UB6,UB7,UB8,UB9], [UC1,UC2,UC3,UC4,UC5,UC6,UC7,UC8,UC9], [UD1,UD2,UD3,UD4,UD5,UD6,UD7,UD8,UD9], [UE1,UE2,UE3,UE4,UE5,UE6,UE7,UE8,UE9], [UF1,UF2,UF3,UF4,UF5,UF6,UF7,UF8,UF9], [UG1,UG2,UG3,UG4,UG5,UG6,UG7,UG8,UG9], [UH1,UH2,UH3,UH4,UH5,UH6,UH7,UH8,UH9], [UI1,UI2,UI3,UI4,UI5,UI6,UI7,UI8,UI9]], [[ZA1,ZA2,ZA3,ZA4,ZA5,ZA6,ZA7,ZA8,ZA9], [ZB1,ZB2,ZB3,ZB4,ZB5,ZB6,ZB7,ZB8,ZB9], [ZC1,ZC2,ZC3,ZC4,ZC5,ZC6,ZC7,ZC8,ZC9], [ZD1,ZD2,ZD3,ZD4,ZD5,ZD6,ZD7,ZD8,ZD9], [ZE1,ZE2,ZE3,ZE4,ZE5,ZE6,ZE7,ZE8,ZE9], [ZF1,ZF2,ZF3,ZF4,ZF5,ZF6,ZF7,ZF8,ZF9], [ZG1,ZG2,ZG3,ZG4,ZG5,ZG6,ZG7,ZG8,ZG9], [ZH1,ZH2,ZH3,ZH4,ZH5,ZH6,ZH7,ZH8,ZH9], [ZI1,ZI2,ZI3,ZI4,ZI5,ZI6,ZI7,ZI8,ZI9]]). %n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],[1],[4],[2],[3]],[[4],[2],[6],[8],[5],[3],[7],[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). %n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],[1],[4],[2],[3]],[[4],N,[6],[8],[5],[3],N,[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). %n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],[2],[3]],[[4],N,[6],[8],[5],N,N,[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). %n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],N,[3]],[[4],N,[6],[8],[5],N,N,N,[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). %n(N),sudoku_([[[5],[3],[4],[6],N,[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],N,[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],N,[3]],[[4],N,[6],[8],[5],N,N,N,[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],N,[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). %n(N),sudoku_([[[5],[3],[4],[6],N,[8],N,N,[2]],[[6],[7],N,[1],[9],N,[3],N,[8]],[[1],N,[8],[3],[4],N,[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],N,[3]],[[4],N,[6],[8],[5],N,N,N,[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],N,[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]). %n(N),sudoku_([[[5],[3],N,N,[7],N,N,N,N],[[6],N,N,[1],[9],[5],N,N,N],[N,[9],[8],N,N,N,N,[6],N],[[8],N,N,N,[6],N,N,N,[3]],[[4],N,N,[8],N,[3],N,N,[1]],[[7],N,N,N,[2],N,N,N,[6]],[N,[6],N,N,N,N,[2],[8],N],[N,N,N,[4],[1],[9],N,N,[5]],[N,N,N,N,[8],N,N,[7],[9]]],[A,B,C,D,E,F,G,H,I]).programmiert für swi-prolog
viel spaß damit
error
ps: die mit % auskommentierten aufrufe unten kann man zum testen nutzen ... sollten funktionieren(ohne garantie
EDIT: es könnte endlosrekursion auftreten( glaub ich ... ist ne weile her
, wenn es kein einfaches rätsel ist ... das ganze war nur zum rumspielen mit prolog gedacht ...
-
Hi Alexej,
mich würde der Code interessieren. Wäre Dir für posten dankbar, bzw. um anderen nicht den Spaß zu nehmen, gerne an uw(ät)dipbach.de - ist schone korrekt ohne e.Gruß,
Uwe