3. Sudoku algorithmus

Sudoku algorithmus

  • B

    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

    0
  • ?

    wäre ein nichtprobierender sudokulöser ein beweis für N=NP?

    0
  • N

    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.

    0
  • J

    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.

    0
  • G

    Auch wenn die Lösung eindeutig ist?

    0
  • J

    Ja, auch dann kann es eine solche Situation geben.

    0
  • G

    Kennst Du ein solches Sudoku und könntest es bitte posten?

    0
  • J

    Ne, ich kenne keines. Aber http://arbeitsblaetter.stangl-taller.at/GEDAECHTNIS/Sudoku.shtml sagt, das auch.

    0
  • ?

    Es ist doch wie es Hanar sagt: Die Zahl mag eine andere sein, aber das Spiel lebt vom Muster.

    0
  • ?

    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

    0
  • M

    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?

    0
  • G

    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

    0
  • E

    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 ...

    0
  • ?

    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

    0
  • E

    Schwere Sudokus sind so aufgebaut, dass du verausdenken musst:
    „Wenn ich hier eine 5 mache, muss ich dort eine 3 machen, dann muss die 3 dort hin, und das geht nicht -> keine 5 einsetzen, sondern die andere Möglichkeit“

    Genau das kannst du am PC nur doch probieren simulieren. Ich würde es so versuchen, dass der sichere Algrithmus solange arbeiten darf, bis er nicht mehr weiter weiß, dann wird probiert (Backtracing).

    0
  • P

    glinux schrieb:

    Ü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.

    Entschuldige, aber das hört sich nicht nach einer optimalen Lösung an... Ich habe einen Sudoku-Solver in Python (interpretiert) geschrieben und der löst auf meinem Athlon 3000+ JEDES Feld, das ich bisher probiert habe in unter 3 Sekunden. Und ich habe auch ein KOMPLETT leeres Feld probiert ^^ ne ungünstigere Belegung geht ja wohl nicht mehr.

    Vorgegangen wird nach dem logischen Ausschlussprinzip und wenn man damit nicht mehr weiter kommt, wird Backtracking hinzugenommen.

    Bei Interesse kann ich den Code mal posten, ich hab das Ganze auch in C++, da allerdings ohne GUI

    An dem Generator für Sudokus arbeite ich gerade noch, der ist allerdings etwas langsamer, d.h. es kann bis zu 10 Sekunden dauern 😮 🙄

    Felix

    0
  • ?

    Hallo zusammen,

    das Grundprinzip zum Lösen ist recht einfach.
    Du speicherst dir für jede Zelle, die möglichen Zahlen.
    Du initialiesierst jede Zell mit allen Zahlen.
    Jetzt fängst du an die vorgegebenen Zahlen einzutragen.
    Wenn du eine Zahl einträgst, löschst du diese Zahl in deinem Quadrat,
    Zeile und Spalte für die übrigen Felder, zudem marikierst du dir dieses
    Feld als gelöst. Wenn du jetzt alle vorgegebenen Zahlen eingetragen hast.
    Läufst du das Spielfeld durch und sucht, ob in einer Zelle (die nicht als
    gelöst markiert ist) nur noch ein Wert möglich ist oder diese Zahl in allen
    anderen Zellen der Zeile / Spalte / Quadrat ausgeschlossen ist. Irgendwas wirst
    du in der Regel finden. Die kannst du dann wie am Anfang eintragen.
    Irgendwann wirst du möglicherweise den Fall haben, dass du irgendwann mit
    diesen Mitteln nicht weiterkommst. Wenn du so weit bist, kannst du dann ja
    mal wieder schreiben.

    Dann mußt du etwa so etwas weiter eingrenzen:
    Bsp.: (2,3,4,5) , (2,3,4,5), (1,4,5), (4,5) , (1,5)
    Das kannst du auf (2,3) (2,3), (1,4,5), (4,5), (1,5) reduzieren

    Da mußt du für alle Teilmengen von Zahlen, alle Felder suchen, in denen sie
    vorhanden sind. Falls die Anzahl der gefundenen Felder gleich der Größe der Menge ist, kannst du die restlichen Zahlen in den Feldern löschen.
    (Natürlich wieder für alle Zeilen Spalten, Quadrate)
    Im Prinzip ist das ne Veralgemeinerung der oberen Verfahren.

    Ob du damit alle eindeutigen SuDokus lösen kannst, weiß ich nicht, aber
    ziemlich viele.

    Gruß,
    SuDokuSolver

    PS: Ich hoffe ich, ich hab nix vergessen 🙄

    0
  • ?

    Warum sollte man einen schlauen Algo schreiben, wenn man es mit probieren in wenigen ms hin bekommt?

    0
  • ?

    Bei einfachen

    0
  • G

    Toniiii schrieb:

    Warum sollte man einen schlauen Algo schreiben, wenn man es mit probieren in wenigen ms hin bekommt?

    So ein Algorithmus muss sich ja nicht immer auf das typische 9x9 Sudoku beziehen. Du kannst das Spielfeld fast beliebig vergrössern. Dann werden aus Millisekunden mal ganz schnell Sekunden oder Minuten.

    0
Anmelden zum Antworten