sudoku programm
-
hallo, habe vor kurzem mit c++ angefangen und jezt ein sudoku-programm geschrieben. es kann bisher die standard-rätsel aus zeitungen lösen, bei schweren sudokus scheitert es aber (kann bisher auch nur mit den einfachsten techniken zahlen ausschließen). Jetzt wollte ich für schwierige sudokus gezieltes raten einbauen (backtracking) aber irgendwie wird das ganze sehr unübersichtlich, was vermutlich an dem design des programms liegt. wie könnte man das verbessern? 2 sachen die ich selbst denke:
-kein globales array (wie übergibt man arrays funktionen?)
-allgemein das hantieren mit arrays in der "kandidatenliste", kann man sowas machen wie ein array von containern?hier mal das programm ohne die grafik+eingabe des sudokus (das eingebene sudoku wird in einem array feld[9][9] gespeichert, hat den wert 0 wenn feld frei
#include <iostream> #include <string> #include <windows.h> #include <vector> #include <SFML/Graphics.hpp> #include <sstream> #include <ctime> int kaestchen[9][9][9]; int feld[9][9]={}; using namespace std; void generierearray(void) { int i,ii,j; for (i=0;i<=8;i++) { for (ii=0;ii<=8;ii++) { if(feld[i][ii]!=0) { kaestchen[i][ii][0]=feld[i][ii]; for(j=1;j<=8;j++) {kaestchen[i][ii][j]=0;} } if(feld[i][ii]==0) { for(j=0;j<=8;j++) {kaestchen[i][ii][j]=(j+1);} } } } } void loeschekandidatenzahl(int kandidatenzahl,int xcoord, int ycoord) { int count; for(count=0;count<=8;count++) { if(kaestchen[xcoord][ycoord][count]==kandidatenzahl){kaestchen[xcoord][ycoord][count]=0;} } } int isfixed(int xcoord, int ycoord) { int j; int count=0; for(j=0;j<=8;j++) { if(kaestchen[xcoord][ycoord][j]!=0) count++; } if (count==1){return 1;} if (count!=1){return 0;} } int getfixedvalue(int xcoord, int ycoord) { int j; for(j=0;j<=8;j++) { if(kaestchen[xcoord][ycoord][j]!=0) return kaestchen[xcoord][ycoord][j]; } } void pruefeloeschen(int kandidatenzahl,int xcoord,int ycoord) { // prüfe in der zeile!!-------------------------- int j; for(j=0;j<=8;j++) { if(isfixed(j,ycoord)==1 && j!=xcoord) { if(getfixedvalue(j,ycoord)==kandidatenzahl) {loeschekandidatenzahl(kandidatenzahl,xcoord,ycoord);} } } //ende pruefezeile------------------------------ //prüfe spalte-------------------- for(j=0;j<=8;j++) { if(isfixed(xcoord,j)==1 && j!=ycoord) { if(getfixedvalue(xcoord,j)==kandidatenzahl) {loeschekandidatenzahl(kandidatenzahl,xcoord,ycoord);} } } // ende spalte prüfen //pruefe kaestchen int x,y; for(x=3*(xcoord/3);x<=3*(xcoord/3)+2;x++) { for(y=3*(ycoord/3);y<=3*(ycoord/3)+2;y++) //3*(xcoord/3) und 3*(ycoord/3) sind geschickt so gewählt dass es eine mastercoord { if(isfixed(x,y)==1 && x!=xcoord && y!=ycoord) { // für jedes große kästchen gibt, dann von dort 3 nach unten mit jeweils 2 schleifen if (getfixedvalue(x,y)==kandidatenzahl) //das deckt dann grad die 9 kastchen in einem großen ab {loeschekandidatenzahl(kandidatenzahl,xcoord,ycoord);} } } } } void kandidatenliste(void) { int i,ii,j; for (ii=0;ii<=8;ii++) { for (i=0;i<=8;i++) { //falls noch keine fixe zahl da ist muss jeder kandidat angeschaut werden if(isfixed(i,ii)==0) // noch keine fixe zahl drin { for(j=0;j<=8;j++) { //3 verschachtelte for schleifen, gehe für jedes feld jeden kandidat in der liste durch if(kaestchen[i][ii][j]!=0){pruefeloeschen(kaestchen[i][ii][j],i,ii);} } //falls das kaestchen jetzt nach den loeschen als fixed zu behandeln ist muss die kandidatenliste neu durchgegeangen werden if(isfixed(i,ii)==1){kandidatenliste();} } //for schleifen ueber die xcoord, ycoord schliessen } } //funktion zuende } int checkknownnumbers(void) { int i,ii; int number=0; for(i=0;i<=8;i++) { for(ii=0;ii<=8;ii++) { if(isfixed(i,ii)==1){number++;} } } return number; } void ausschliessen(void) { int i,ii,j,tempx,tempy,hilf; int g; int counter=checkknownnumbers(); //zeilenausschliessen------------------------------------------------------------------- for (ii=0;ii<=8;ii++ )//gehe durch alle zeilen { for(hilf=1;hilf<=9;hilf++) //gehe durch alle mögl zahlen in einer zeile { int countt=0; for(i=0;i<=8;i++) //gehe durch alle kandidaten in einer zeile (hier kann man sich vmtl ein for sparen, aber allg...) { for(j=0;j<=8;j++) { if(kaestchen[i][ii][j]==hilf){countt++;tempx=i;tempy=ii;} //erhoeht den zahler und speichert position } // des letzten auftretens einer zahl in tempx,tempy } // wenn in einer zeile eine zahl genau einmal vorkommt if(countt==1) { kaestchen[tempx][tempy][0]=hilf; for(g=1;g<=8;g++){kaestchen[tempx][tempy][g]=0;} kandidatenliste(); } }//ende schleife ueber alle zahlen }//ende schleife ueber alle zeilen //ende zeilenausschliessen----------------------------------------------- //-------Spaltenausschliessen------------------------------------- for (i=0;i<=8;i++ )//gehe durch alle spalten { for(hilf=1;hilf<=9;hilf++) //gehe durch alle mögl zahlen in einer zeile { int countt=0; for(ii=0;ii<=8;ii++) //gehe durch alle kandidaten in einer spalte (hier kann man sich vmtl ein for sparen, aber allg...) { for(j=0;j<=8;j++) { if(kaestchen[i][ii][j]==hilf){countt++;tempx=i;tempy=ii;} //erhoeht den zahler und speichert position } // des letzten auftretens einer zahl in tempx,tempy } // wenn in einer spalte eine zahl genau einmal vorkommt if(countt==1) { kaestchen[tempx][tempy][0]=hilf; for(g=1;g<=8;g++){kaestchen[tempx][tempy][g]=0;} kandidatenliste(); } }//ende schleife ueber alle zahlen }//ende schleife ueber alle spalten //-ende spaltenausschliessen----------------------- //kästchenausschliessen-------------------------------------------------------------- int gx,gy; for (gx=0;gx<=6;gx=gx+3 )//gehe durch alle kästchen { for(gy=0;gy<=6;gy=gy+3) { for(hilf=1;hilf<=9;hilf++) //gehe durch alle mögl zahlen in einer zeile { int countt=0; for(i=0;i<=2;i++) //gehe durch alle kandidaten in einem kästchen (hier kann man sich vmtl ein for sparen, aber allg...) { for(ii=0;ii<=2;ii++) { for(j=0;j<=8;j++) { if(kaestchen[gx+i][gy+ii][j]==hilf){countt++;tempx=gx+i;tempy=gy+ii;} //erhoeht den zahler und speichert position } // des letzten auftretens einer zahl in tempx,tempy } } // wenn in einer zeile eine zahl genau einmal vorkommt if(countt==1) { kaestchen[tempx][tempy][0]=hilf; for(g=1;g<=8;g++){kaestchen[tempx][tempy][g]=0;} kandidatenliste(); } }//ende schleife ueber alle zahlen }//ende schleife ueber alle ycoord gy }//ende schleife ueber alle xcoord gx //ende kästchenausschliessen--------------------------------------------------------- if(checkknownnumbers()>counter){ausschliessen();} //falls jetzt mehr zahlen bekannt sind muss wieder ausschliessen angewandt werden! } int _tmain(int argc, _TCHAR* argv[]) { // berechnungsteil, falls das einlesen beendet if (eingelesen==1) { generierearray(); kandidatenliste(); ausschliessen(); //falls in einem kästchen /reihe/spalte ein kandidat genau einmal vorkommt muss er dort stehen //jedes mal wenn eine zahl festgelegt werden kann muss die kandidatenliste aktualisiert werden und mit dem ausschließen von // vorne angefangen werden } return 0; }
-
Hallo,
also in C++ Array an Funktionen zu übergeben geht wie folgt:
#include <iostream> // gibt den array aus void printArray(int * intArr, int size){ for(int i = 0 i<size;i++){ std::cout << intArr[i] << std::endl; } } int main(){ int test[2]; test[0]=20; test[1]=30; int ArraySize= sizeof(test) / sizeof(test[0]) printArray(test,ArraySize); return 0; }würde dir eher Vectoren empfehlen:
#include <vector> int main(){ std::vector<int> intVec; std::vector<std::vector<int> > testVec; // ein Vector der einen Vector von Zahlen enthält ;) return 0; }
-
ArraysAreBad schrieb:
also in C++ Array an Funktionen zu übergeben geht wie folgt:
Das geht zwar so, aber das wäre, wie man es in C macht. In C++ machen wir das in diesem Stil:
template<typename iterator> void foo(iterator anfang, iterator ende);Und schon ist es völlig egal, welche Art von Container hinter den Iteratoren steht. Die Funktion funktioniert mit Arrays, std::array, vector, unordered_map, eigenen Containern, egal was. Und das ohne Nachteile.
-
Hallo dwtoni,
es ist gar nicht notwendig, Arrays zu übergeben. Packe das gesamte Feld einfach eine Klasse, und die kannst Du dann als Parameter überall hin übergeben.
Auch ist es nicht notwendig, ein zweidimensionales Array zu wählen - ein 1-dimensionales reicht auch. Das einzige Problem wären dann die Zugriffe auf eine Zeile, Spalte oder ein Quadrat, aber das lässt sich alles mit ein paar kleinen Helferlein lösen.Ich habe das vor Jahren mal realisiert. Den Code habe ich auch wieder gefunden:
#include <iostream> #include <utility> // std::pair<> #include <vector> #include <sstream> class Field // das 9x9-Sudoku-Feld { public: bool check( const int* pos, int zahl ) const; // liefert 'true', falls die Zahl 'zahl' an die Position 'pos' gesetzt werden kann bool solve(); // setzt alle fehlenden Zahlen (wenn möglich) // -- Field IO friend std::istream& operator>>( std::istream& in, Field& f ) { int* dst = f.data_; for( char c; dst != f.data_+ sizeof(f.data_)/sizeof(*f.data_) && in >> c; ++dst ) *dst = int(c - '0'); return in; } friend std::ostream& operator<<( std::ostream& out, const Field& f ) { for( const int* p = f.data_; p != f.data_+sizeof(f.data_)/sizeof(*f.data_); ++p ) { out << *p; const int i = p-f.data_+1; if( i%27 == 0 ) out << "\n"; if( i%9 == 0 ) out << "\n"; else if( i%3 == 0 ) out << " "; } return out; } private: // -- Helferlein, für den Zugriff in 'check' const int* operator[]( int lineIdx ) const { return data_+(9*lineIdx); } std::pair< int, int > coordinaten( const int* pos ) const { const int i = pos - data_; return std::make_pair( i/9, i%9 ); // Zeile, Spalte } int data_[9*9]; // DAS Feld }; bool Field::check( const int* pos, int zahl ) const { const std::pair< int, int > coord = coordinaten( pos ); // Zeile prüfen for( int i=0; i<9; ++i ) if( (*this)[coord.first][i] == zahl ) return false; // Zahl bereits in der Zeile vorhanden // Spalte prüfen for( int i=0; i<9; ++i ) if( (*this)[i][coord.second] == zahl ) return false; // Zahl bereits in der Spalte vorhanden // 3x3-Quadrat prüfen int line0 = 3*(coord.first/3); int column0 = 3*(coord.second/3); for( int i=0; i<3; ++i ) for( int j=0; j<3; ++j ) if( (*this)[line0+i][column0+j] == zahl ) return false; return true; } // -- der Backtracking-Algorithmus template< typename I > bool backtrack( Field& field, I cur, I last ) { for( int zahl = 1; zahl <= 9; ++zahl ) { if( !field.check( *cur, zahl ) ) // ist das Setzen von 'zahl' hier möglich continue; // nein, dann zur nächsten Zahl **cur = zahl; // .. ok, dann setze sie I next = cur; if( ++next == last || backtrack( field, next, last ) ) return true; // Lösung gefunden **cur = 0; // keine Lösung, dann 'back track' } return false; } bool Field::solve() { std::vector< int* > candidates; for( int* p = data_; p != data_+sizeof(data_)/sizeof(*data_); ++p ) if( *p == 0 ) // freies Feld candidates.push_back( p ); return backtrack( *this, candidates.begin(), candidates.end() ); } int main() { using namespace std; istringstream sudoku( "700 000 508" "000 000 006" "100 009 000" "000 501 400" "000 004 209" "040 300 000" "000 600 003" "008 070 100" "006 805 000"); Field f; if( sudoku >> f && f.solve() ) cout << "geloest:\n" << f << endl; return 0; }das ist in keiner Weise zeitoptimal - gilt insbesondere für das Iterieren über Zeilen und Spalten, aber ich glaube, dass der Code so verständlicher ist.
Gruß
Werner
-
hallo zusammen vielen dank für die vorschläge. habe es mittlerweile hinbekommen den backtracking algorithmus mit dem ursprüngl design zum laufen zu bekommen. ich denke aber darüber nach das programm nochmal mit einer klasse zu schreiben um etwas dazuzulernen!
