Hilfe bei Sudoku-Löser
-
Hallo! Wie der Titel schon sagt bastel ich gerade für die FH an der ich studier nen Sudoku-Löser! Leider habe ich damit noch ein paar Probleme...
Hfftl kann mir jemand von euch helfen?
Schonmal danke im Vorraus!/*-------------------------------- Der Header --------------------------------*/ #ifndef SUDOKU_H #define SUDOKU_H int const n = 9; typedef int field[n][n]; void FillGaps( field f); bool FindGaps (int &i, int &j, field f); bool CheckIfAnyZero(field f); bool CheckRow (int const value, int const j, field f); bool CheckColumn (int const value, int const i, field f); bool CheckBox (int const i, int const j, int const value, field f); void PrintSudoku (field f); #endif /*-------------------------------- Der Testtreiber (Beispiel 1 und 2 sind hier atm noch gleich) --------------------------------*/ // Testtreiber #include "sudoku.h" #include <iostream> using namespace std; int main() { field F1 = { // Angabe Beispiel 1 {7, 0, 0, 0, 0, 0, 0, 0, 8}, {4, 0, 0, 0, 0, 7, 0, 6, 0}, {1, 0, 0, 0, 5, 2, 7, 0, 0}, {0, 7, 0, 5, 0, 8, 0, 9, 4}, {0, 0, 9, 0, 0, 0, 6, 0, 0}, {6, 5, 0, 7, 0, 9, 0, 8, 0}, {0, 0, 7, 8, 3, 0, 0, 0, 2}, {0, 2, 0, 9, 0, 0, 0, 0, 6}, {5, 0, 0, 0, 0, 0, 0, 0, 9} }; field F2 = { // Angabe Beispiel 2 {7, 0, 0, 0, 0, 0, 0, 0, 8}, {4, 0, 0, 0, 0, 7, 0, 6, 0}, {1, 0, 0, 0, 5, 2, 7, 0, 0}, {0, 7, 0, 5, 0, 8, 0, 9, 4}, {0, 0, 9, 0, 0, 0, 6, 0, 0}, {6, 5, 0, 7, 0, 9, 0, 8, 0}, {0, 0, 7, 8, 3, 0, 0, 0, 2}, {0, 2, 0, 9, 0, 0, 0, 0, 6}, {5, 0, 0, 0, 0, 0, 0, 0, 9} }; field F3 = { {3, 9, 0, 0, 0, 0, 2, 0, 0}, // Angabe Beispiel 3 {2, 5, 8, 3, 9, 6, 0, 0, 4}, {0, 0, 0, 0, 0, 5, 9, 0, 0}, {8, 2, 0, 0, 0, 3, 7, 0, 1}, {9, 0, 6, 1, 7, 0, 8, 0, 2}, {0, 1, 0, 0, 5, 0, 0, 3, 0}, {0, 0, 2, 0, 0, 9, 0, 0, 0}, {4, 0, 1, 5, 0, 0, 0, 9, 0}, {6, 9, 0, 0, 0, 1, 0, 0, 8} }; int end = 0; FillGaps (F1); FillGaps (F2); FillGaps (F3); PrintSudoku(F1); cout << endl; PrintSudoku(F2); cout << endl; PrintSudoku(F3); cin >> end; return 0; } /*-------------------------------- Das Modul --------------------------------*/ /* Lösungsidee: Das Lösungsprogramm sucht zunächst das erste freie Feld (0) und probiert dann nacheinander alle Ziffern beginnend mit der Eins aus (value). Wenn eine Ziffer gefunden wurde, die die Spielregeln nicht verletzt, wird diese eingesetzt und der Algorithmus mit dem nächsten freien Feld wiederholt. Wenn es kein freies Feld mehr gibt, dann ist das Rätsel gelöst. Falls jedoch keine der Ziffern 1 bis 9 in das Feld passt geht das Programm ein Feld weiter und wiederholt das Ganze mit der nächsten Lücke. */ #include "sudoku.h" #include <iostream> using namespace std; /*-------------------------------- Funktion 1: FillGaps --------------------------------*/ void FillGaps ( field f) { int j = 0; // Zeile int i = 0; // Spalte int counter = 0; // Zähl wieviele values möglich int TMP = 0; // Merkt sich den value kurz while (CheckIfAnyZero(f) ) { while ( FindGaps(i, j, f) ){ counter = 0; TMP = 0; for ( int value = 1 ; value < 10; value++ ) { if ( CheckRow (value, j, f) && CheckColumn (value, i, f) && CheckBox (i, j, value, f) ) { TMP = value; counter++; } } if ( counter < 2) { f[j][i] = TMP; } i++; // damit FindGaps ein Feld weiter geht } } } /*-------------------------------- Funktion 2: FindGaps --------------------------------*/ bool FindGaps (int &i, int &j, field f) { // sucht nach freien Stellen im Sudoku, geht dabei das ganze 9 * 9 Sudoku durch, bis es eine Lücke findet //--------------------------------- for ( j; j < 9; j++) { for ( i ; i < 9; i++) { if ( f [j][i] == 0 ) { return true; } } } return false; } /*-------------------------------- Hilfs - Funktion: CheckIfAnyZero --------------------------------*/ bool CheckIfAnyZero(field f) { int row = 0; int column = 0; for ( row; row < 9; row++) { for ( column ; column < 9; column++) { if ( f [row][column] == 0 ) { return true; } } } return false; } /*-------------------------------- Funktion 3: CheckRow --------------------------------*/ bool CheckRow (int const value, int const j, field f) { // Vergleicht den einzusetzenden Value-Wert mit allen anderen Zahlen der Zeile int column = 0; for(column; column < 9; column++) { if ( value == f [j][column] ) { return false; } // wenn value bereits irgendwo in der Reihe einmal vorkommt return false! } return true; // wenn value nirgends in der Reihe vorkommt return true! } /*-------------------------------- Funktion 4: CheckColumn --------------------------------*/ bool CheckColumn (int const value, int const i, field f) { int row = 0; for(row; row < 9; row++) { if ( value == f [row][i] ) { return false; } // wenn value bereits irgendwo in der Reihe einmal vorkommt return false! } return true; // wenn value nirgends in der Spalte vorkommt return true! } /*-------------------------------- Funktion 5: CheckBox --------------------------------*/ bool CheckBox (int const i, int const j, int const value, field f) { if (j < 3) { switch(i) { case 0: // Case: Linkes Unterquadrat case 1: case 2: for (int row = 0; row < 3; row++) { for (int column = 0; column < 3; column++) { if (f [row][column] == value) { return false; } } } return true; // falls Zahl nicht im linken Unterquadrat vorkommt,return true break; case 3: // Case: Mittleres Unterquadrat case 4: case 5: for (int row = 0; row < 3; row++) { for (int column = 3; column < 6; column++) { if (f [row][column] == value) { return false; } } } return true; // falls Zahl nicht im mittleren Unterquadrat vorkommt,return true break; case 6: // Case: Rechtes Unterquadrat case 7: case 8: for (int row = 0; row < 3; row++) { for (int column = 6; column < 9; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im rechten Unterquadrat vorkommt, return true break; } return true; } //----------------------------------------------------------------------------------------------------- else if (j > 2 && j < 6) { switch(i) { case 0: // Case: Linkes Unterquadrat case 1: case 2: for (int row = 3; row < 6; row++) { for (int column = 0; column < 3; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im linken Unterquadrat vorkommt, return true break; case 3: // Case: Mittleres Unterquadrat case 4: case 5: for (int row = 3; row < 6; row++) { for (int column = 3; column < 6; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im mittleren Unterquadrat vorkommt, return true break; case 6: // Case: Rechtes Unterquadrat case 7: case 8: for (int row = 3; row < 6; row++) { for (int column = 6; column < 9; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im rechten Unterquadrat vorkommt, return true break; } return true; } //----------------------------------------------------------------------------------------------------- else { switch(i) { case 0: // Case: Linkes Unterquadrat case 1: case 2: for (int row = 6; row < 9; row++) { for (int column = 0; column < 3; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im linken Unterquadrat vorkommt, return true break; case 3: // Case: Mittleres Unterquadrat case 4: case 5: for (int row = 6; row < 9; row++) { for (int column = 3; column < 6; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im mittleren Unterquadrat vorkommt, return true break; case 6: // Case: Rechtes Unterquadrat case 7: case 8: for (int row = 6; row < 9; row++) { for (int column = 6; column < 9; column++) { if (f [row][column] == value) { return false; } } } return true; // falls die Zahl noch nicht im rechten Unterquadrat vorkommt, return true break; } return true; } } /*-------------------------------- Funktion 6: Ausgabe --------------------------------*/ void PrintSudoku (field f) { int writeRow = 0; int writeColumn = 0; // Ausgabe des gelösten Feldes cout << "------------------------------------" << endl; for (writeRow; writeRow < 9; writeRow++) { cout << " "; for (writeColumn; writeColumn < 9; writeColumn++) { cout << f[writeRow][writeColumn] << " | "; } writeColumn = 0; cout <<endl; cout << "------------------------------------" << endl; } }
-
Momentan hängt das Ding in der Endlosschleife, weil nix eingesetzt wird, woran kann das liegen?
-
Ohne mir den ganzen Müll jetzt durchgelesen zu haben:
Du musst mit Backtracking arbeiten. Deine Lösungsidee wird nicht funktionieren.
-
Müsste man das nicht über Brute Force lösen? Also ich hab mich früher auch schonmal an sowas probiert und hatte da 81 ineinander verschachtelte for() Schleifen.
-
Also ich hab mich früher auch schonmal an sowas probiert und hatte da 81 ineinander verschachtelte for() Schleifen.
Und du hattest während dieser Aktion nicht mal wenigstens kurzzeitig das Gefühl, dass es auch einfacher gehen müsste?
Rekursion.BTW ist es nicht so, dass typische Sudokus, die in Zeitungen usw. veröffentlicht werden, nie Backtracking erfordern?
-
Hab ich auch mal gemacht, hier eine Bruteforce-Methode:
//Eigentum von Thuruk :-) #include<iostream> using namespace std; #include<fstream> #include<string> #ifdef _WIN32 #include<Windows.h> #endif #ifdef _WIN32 void opb_clear(){ HANDLE stdo = GetStdHandle(STD_OUTPUT_HANDLE); CONSOLE_SCREEN_BUFFER_INFO csbi; COORD coordScreen={0,0}; DWORD cCharsWritten; DWORD dwConSize; GetConsoleScreenBufferInfo(stdo, &csbi); dwConSize=csbi.dwSize.X*csbi.dwSize.Y; FillConsoleOutputCharacter(stdo, TEXT(' '), dwConSize, coordScreen, &cCharsWritten); GetConsoleScreenBufferInfo(stdo, &csbi); FillConsoleOutputAttribute(stdo, csbi.wAttributes, dwConSize, coordScreen, &cCharsWritten); SetConsoleCursorPosition(stdo, coordScreen); } #endif class feld{ public: short fe[81]; short len; public: feld(string filename, bool &success, short laenge=81){ len=laenge; char ziffer; ifstream datei; datei.open(filename.c_str()); if(datei.is_open()){ for(short i=0;i<len;++i){ if(datei.eof()){ len=i; if(i!=9) success=false; break; } datei >> ziffer; fe[i]=ziffer-'0'; } datei.close(); } else success=false; } friend ostream &operator<<(ostream &out, feld &sudoku); bool ue(void); feld loesung(long &nv, bool &success, bool watch=false); }; ostream &operator<<(ostream &out, feld &sudoku){ short a; if(sudoku.len==81) a=9; if(sudoku.len==9) a=3; if(sudoku.len!=9&&sudoku.len!=81) return out; for(short i=0;i<sudoku.len;i+=a){ for(short j=i;j<a+i;++j){ out << sudoku.fe[j]; if(sudoku.len==81&&(j+1)%3==0&&j!=9+i-1) out << ' '; } out << '\n'; if(sudoku.len==81&&(i+9)%27==0&&i!=72) out << '\n'; } return out; } inline bool feld::ue(){ if(len==9){ for(short i=0; i<9; ++i) for(short j=0; j<9; ++j) if(fe[i]==fe[j]&&i!=j&&fe[i]!=0) return false; return true; } if(len==81){ for(short a=0; a<9; ++a){ for(short i=9*a; i<9*a+9; ++i) for(short j=9*a; j<9+9*a; ++j) if(fe[i]==fe[j]&&i!=j&&fe[i]!=0) return false; for(short i=a; i<81; i+=9) for(short j=a; j<81; j+=9) if(fe[i]==fe[j]&&i!=j&&fe[i]!=0) return false; } for(short i=0; i<3; ++i) for(short j=i; j<21+i; j+=9) for(short k=0; k<3; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=3; i<6; ++i) for(short j=i; j<21+i; j+=9) for(short k=3; k<6; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=6; i<9; ++i) for(short j=i; j<21+i; j+=9) for(short k=6; k<9; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=27; i<30; ++i) for(short j=i; j<21+i; j+=9) for(short k=27; k<30; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=30; i<33; ++i) for(short j=i; j<21+i; j+=9) for(short k=30; k<33; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=33; i<36; ++i) for(short j=i; j<21+i; j+=9) for(short k=33; k<36; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=54; i<57; ++i) for(short j=i; j<21+i; j+=9) for(short k=54; k<57; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=57; i<60; ++i) for(short j=i; j<21+i; j+=9) for(short k=57; k<60; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; for(short i=60; i<63; ++i) for(short j=i; j<21+i; j+=9) for(short k=60; k<63; ++k) for(short m=k; m<21+k; m+=9) if(fe[m]==fe[j]&&m!=j&&fe[m]!=0) return false; return true; } return false; } inline void reset(short *ver){ for(short i=1; i<10; ++i)ver[i]=0; } feld feld::loesung(long &nv, bool &success, bool watch){ short ver[81][10]; short s=0, i=0, j=0; for(i; i<81; ++i){ reset(ver[i]); if(fe[i]==0){ ver[s][0]=i; ++s; } } for( i = 0 ; i < s ; ){ if(i<0){ success=false; break; } for(j=1; ; ++j) { if(j==10){ fe[ver[i][0]]=0; reset(ver[i]); i-=1; break; } if(ver[i][j]==0) { fe[ver[i][0]]=j; ver[i][j]=1; nv+=1; if(watch){ #ifdef _WIN32 opb_clear(); #else cout << "\033[2J\033[1;1H"; #endif cout << "Versuch " << nv << ":\n" << *this << "-----------\n"; } if(ue()==true) { ++i; break; } } } } return *this; } void hm_laden(bool watch){ string filename; bool success=true; short wahl_gr=0, wahl_sp=0, gr=0; long nv=0; ofstream datei; cout << "Dateiname:\n"; cin >> filename; while(wahl_gr!=1&&wahl_gr!=2){ cout << "Groesse?\n1. Automatisch erkennen\n2. 9 Felder\n"; cin >> wahl_gr; switch(wahl_gr){ case 1: gr=81; break; case 2: gr=9; break; default: cout << "Ungueltige Eingabe\n"; break; } } feld laden(filename, success, gr); if(success==true){ cout << "Das vorhandene Sudoku:\n" << laden; feld geloest=laden.loesung(nv, success, watch); if(success==true){ cout << "Sudoku in " << nv << " Versuchen geloest. Die Loesung:\n" << geloest; while(wahl_sp!=1&&wahl_sp!=2){ cout << "Diese kann in einer Datei gespeichert werden.\n1. Ja\n2. Nein\n"; cin >> wahl_sp; switch(wahl_sp){ case 1: cout << "Dateiname:\n"; cin >> filename; datei.open(filename.c_str()); if(datei.is_open()){ datei << geloest; cout << "Gespeichert.\n"; } else cout << "Dateifehler.\n"; break; case 2: break; default: cout << "Ungueltige Eingabe.\n"; } } } else cout << "Das Sudoku konnte nicht geloest werden.\n"; } else cout << "Dateifehler.\n"; } int main(){ short wahl=0; cout << "Willkommen zum Sudoku-Loeser\n"; while(wahl!=3){ cout << "Hauptmenue\n1. Sudoku aus Datei laden\n2. Zuschauen (langsam!)\n3. Beenden\n"; cin >> wahl; switch(wahl){ case 1: hm_laden(false); break; case 2: hm_laden(true); break; case 3: break; default: cout << "Ungueltige Eingabe.\n"; break; } } return 0; }'opb_clear()' ist nicht so schön gelöst, aber wollte es auch mal auf nem Windows-Rechner testen. Wurde unter Linux programmiert.
-
Bashar schrieb:
Also ich hab mich früher auch schonmal an sowas probiert und hatte da 81 ineinander verschachtelte for() Schleifen.
Und du hattest während dieser Aktion nicht mal wenigstens kurzzeitig das Gefühl, dass es auch einfacher gehen müsste?
Rekursion.Nee, bin ich damals nicht drauf gekommen. Ehrlich gesagt weiß ich auch jetzt nicht, wie ich es mit Rekursion hätte lösen können. Kannst du da etwas konkreter werden?
-
seux schrieb:
Nee, bin ich damals nicht drauf gekommen. Ehrlich gesagt weiß ich auch jetzt nicht, wie ich es mit Rekursion hätte lösen können. Kannst du da etwas konkreter werden?
Ich hab es mal rekursiv in C# gemacht.
private bool solveSudoku(int fieldCol, int fieldRow, int cellCol, int cellRow) { if (!Sudoku.getCell(fieldCol, fieldRow, cellCol, cellRow).Final) { for (int i = minValue; i <= maxValue; i++) { Sudoku.setCell(fieldCol, fieldRow, cellCol, cellRow, i); if (!Sudoku.isValid()) continue; if (Sudoku.isComplete()) return true; int nFieldCol = fieldCol; int nFieldRow = fieldRow; int nCellCol = cellCol; int nCellRow = cellRow; bool finish = false; calculateNextCell(ref nFieldCol, ref nFieldRow, ref nCellCol, ref nCellRow, ref finish); if (finish) return true; if (solveSudoku(nFieldCol, nFieldRow, nCellCol, nCellRow) == true) return true; } Sudoku.delCell(fieldCol, fieldRow, cellCol, cellRow); return false; } else { int nFieldCol = fieldCol; int nFieldRow = fieldRow; int nCellCol = cellCol; int nCellRow = cellRow; bool finish = false; calculateNextCell(ref nFieldCol, ref nFieldRow, ref nCellCol, ref nCellRow, ref finish); if (finish) return true; if (solveSudoku(nFieldCol, nFieldRow, nCellCol, nCellRow) == true) return true; return false; } } private void calculateNextCell(ref int nFieldCol, ref int nFieldRow, ref int nCellCol, ref int nCellRow, ref bool finish) { nCellCol++; if (nCellCol >= cellCols) { nCellCol = 0; nCellRow++; } if (nCellRow >= cellRows) { nCellRow = 0; nFieldCol++; } if (nFieldCol >= fieldCols) { nFieldCol = 0; nFieldRow++; } if (nFieldRow >= fieldRows) { finish = true; } }Aufgerufen durch
bool result = solveSudoku(0, 0, 0, 0);Klasse SudokuField
public class SudokuField { private Field[][] _fields; private int _rows; private int _cols; private int _fieldRows; private int _fieldCols; public SudokuField(int col, int row) { _rows = row; _cols = col; _fieldRows = 3; _fieldCols = 3; _fields = new Field[_cols][]; for (int i = 0; i < _cols; i++) { _fields[i] = new Field[_rows]; for (int j = 0; j < _rows; j++) { _fields[i][j] = new Field(_fieldCols, _fieldRows); } } } public Field getField(int col, int row) { return _fields[col][row]; } public Field getField(int index) { return getField(index % _cols, (int)(index / _cols)); } public void delCell(int fieldCol, int fieldRow, int cellCol, int cellRow) { _fields[fieldCol][fieldRow].delCell(cellCol, cellRow); } public void delCell(int col, int row) { int selectedFieldCol = (int)(col / _fieldCols); int selectedFieldRow = (int)(row / _fieldRows); int selectedCellCol = col % _fieldCols; int selectedCellRow = row % _fieldRows; delCell(selectedFieldCol, selectedFieldRow, selectedCellCol, selectedCellRow); } public void delCell(int index) { delCell(index % _cols, (int)(index / _cols)); } public Cell getCell(int fieldCol, int fieldRow, int cellCol, int cellRow) { return _fields[fieldCol][fieldRow].getCell(cellCol, cellRow); } public Cell getCell(int col, int row) { int selectedFieldCol = (int)(col / _fieldCols); int selectedFieldRow = (int)(row / _fieldRows); int selectedCellCol = col % _fieldCols; int selectedCellRow = row % _fieldRows; return getCell(selectedFieldCol, selectedFieldRow, selectedCellCol, selectedCellRow); } public Cell getCell(int index) { return getCell(index % _cols, (int)(index / _cols)); } public void setCell(int index, int value) { setCell(index % _cols, (int)(index / _cols), value); } public void setCell(int col, int row, int value) { int selectedFieldCol = (int)(col / _fieldCols); int selectedFieldRow = (int)(row / _fieldRows); int selectedCellCol = col % _fieldCols; int selectedCellRow = row % _fieldRows; setCell(selectedFieldCol, selectedFieldRow, selectedCellCol, selectedCellRow, value); } public void setCell(int fieldCol, int fieldRow, int cellCol, int cellRow, int value) { setCell(fieldCol, fieldRow, cellCol, cellRow, value, false); } public void setCell(int index, Cell value) { setCell(index % _cols, (int)(index / _cols), value); } public void setCell(int col, int row, Cell value) { int selectedFieldCol = (int)(col / _fieldCols); int selectedFieldRow = (int)(row / _fieldRows); int selectedCellCol = col % _fieldCols; int selectedCellRow = row % _fieldRows; setCell(selectedFieldCol, selectedFieldRow, selectedCellCol, selectedCellRow, value); } public void setCell(int fieldCol, int fieldRow, int cellCol, int cellRow, Cell value) { setCell(fieldCol, fieldRow, cellCol, cellRow, value); } public void setCell(int index, int value, bool final) { setCell(index % _cols, (int)(index / _cols), value, final); } public void setCell(int col, int row, int value, bool final) { int selectedFieldCol = (int)(col / _fieldCols); int selectedFieldRow = (int)(row / _fieldRows); int selectedCellCol = col % _fieldCols; int selectedCellRow = row % _fieldRows; setCell(selectedFieldCol, selectedFieldRow, selectedCellCol, selectedCellRow, value, final); } public void setCell(int fieldCol, int fieldRow, int cellCol, int cellRow, int value, bool final) { _fields[fieldCol][fieldRow].setCell(cellCol, cellRow, value, final); } public bool isValidCell(int col, int row) { return isValidCell(col, row, Direction.Both); } public bool isValidCell(int index) { return isValidCell(index, Direction.Both); } public bool isValidCell(int col, int row, Direction dir) { switch(dir) { case Direction.Horizontal: return isValidHorizontal(col); case Direction.Vertical: return isValidVertical(row); case Direction.Both: if (!isValidHorizontal(col)) return false; return isValidVertical(row); default: return false; } } public bool isValidCell(int index, Direction dir) { return isValidCell(index % _cols, (int)(index / _cols), dir); } private bool isValidHorizontal(int col) { bool[] check = new bool[_fieldCols * _cols]; for (int i = 0; i < check.Length; i++) { check[i] = false; } for (int i = 0; i < check.Length; i++) { if (getCell(col, i).Valid) { int currentValue = getCell(col, i).Value - 1; if (check[currentValue] == true) return false; else check[currentValue] = true; } } return true; } private bool isValidVertical(int row) { bool[] check = new bool[_fieldRows * _rows]; for (int i = 0; i < check.Length; i++) { check[i] = false; } for (int i = 0; i < check.Length; i++) { if (getCell(i, row).Valid) { int currentValue = getCell(i, row).Value - 1; if (check[currentValue] == true) return false; else check[currentValue] = true; } } return true; } public bool isValid() { for (int i = 0; i < _fieldCols; i++) { for (int j = 0; j < _fieldRows; j++) { if (!_fields[i][j].isValid()) return false; } } for (int i = 0; i < _cols * _fieldCols; i++) { for (int j = 0; j < _rows * _fieldRows; j++) { if (!isValidCell(i, j)) return false; } } return true; } public bool isComplete() { for (int i = 0; i < _rows * _cols; i++) { if (!getField(i).isComplete()) return false; } return true; } } public class Field { private Cell[][] _cells; private int _fieldRows; private int _fieldCols; public Field(int col, int row) { _fieldCols = col; _fieldRows = row; _cells = new Cell[_fieldCols][]; for (int i = 0; i < _fieldCols; i++) { _cells[i] = new Cell[_fieldRows]; for (int j = 0; j < _fieldRows; j++) { _cells[i][j] = new Cell(); } } } public Cell getCell(int col, int row) { return _cells[col][row]; } public Cell getCell(int index) { return getCell(index % _fieldCols, (int)(index / _fieldCols)); } public void delCell(int col, int row) { _cells[col][row].Value = -1; } public void delCell(int index) { delCell(index % _fieldCols, (int)(index / _fieldCols)); } public void setCell(int col, int row, int value) { setCell(col, row, value, false); } public void setCell(int index, int value) { setCell(index % _fieldCols, (int)(index / _fieldCols), value); } public void setCell(int col, int row, Cell value) { _cells[col][row] = value; } public void setCell(int index, Cell value) { setCell(index % _fieldCols, (int)(index / _fieldCols), value); } public void setCell(int col, int row, int value, bool final) { _cells[col][row].Value = (sbyte)value; _cells[col][row].Final = final; } public void setCell(int index, int value, bool final) { setCell(index % _fieldCols, (int)(index / _fieldCols), value, final); } public bool isValid() { bool[] check = new bool[_fieldCols * _fieldRows]; for (int i = 0; i < check.Length; i++) { check[i] = false; } for (int i = 0; i < check.Length; i++) { if (getCell(i).Valid) { int currentValue = getCell(i).Value - 1; if (check[currentValue] == true) return false; else check[currentValue] = true; } } return true; } public bool isComplete() { for(int i = 0; i < _fieldCols * _fieldRows; i++) { if(!getCell(i).Valid) return false; } return true; } } public class Cell { private sbyte _value; private bool _final; private bool _valid; public sbyte Value { get { return _value; } set { if (Final) throw new AccessViolationException(); _value = value; _valid = (value == -1) ? false : true; } } public bool Final { get { return _final; } set { _final = value; } } public bool Valid { get { return _valid; } } public Cell() { _value = -1; _final = false; _valid = false; } } public enum Direction : byte { Both, Horizontal, Vertical }
-
wasfüreinescheiße schrieb:
Ohne mir den ganzen Müll jetzt durchgelesen zu haben:
Du musst mit Backtracking arbeiten. Deine Lösungsidee wird nicht funktionieren.Man muss nicht mit Backtracking arbeiten. Einfachere Methoden sind z.B. das Speichern aller möglichen Positionen einer Zahl innerhalb einer Zeile/Spalte/Zelle und das entsprechende Verändern der anderen Einträge, falls nur noch eine Möglichkeit übrigbleibt. (also afaik die normale Lösungsstrategie von Menschen)...
Backtracking kann natürlich trotzdem manchmal erforderlich sein.Ich hab auch mal einen Sudokusolver in C++ geschrieben (dessen Code-Vorbildlichkeit allerdings fraglich ist), er ist allerdings ein bisschen zu lange zum Posten (mit Input-Parsing + Aufruf ca. 600 Zeilen). Auf meinem Laptop braucht er ca. 1.8 ms zum Lösen eines (schweren) Sudokus.
@Bashar: In Zeitungen vielleicht selten, aber es gibt durchaus Sudokus, die nur mit Brute-Force lösbar sind (jedenfalls nicht mit einer mir bekannten anwendbaren Lösungsstrategie).
-
wxSkip schrieb:
@Bashar: In Zeitungen vielleicht selten, aber es gibt durchaus Sudokus, die nur mit Brute-Force lösbar sind (jedenfalls nicht mit einer mir bekannten anwendbaren Lösungsstrategie).
Sowas hab ich auch schon in Zeitungen gesehen. "Wenn hier eine 5 stünde, dann könnte hier nur eine 3 stehen, dann bliebe für die 4 nur hier und hier, wenn sie hier stünde, dann.. sonst..." <<< Selbst sowas hilft bei manchen nicht mehr weiter.
-
Mit dem Backtracking habe ich noch Schwierigkeiten. ist das so gedacht, dass ich, wenn ein leeres Feld mehr als eine Lösung hat (ergo noch nicht eindeutig befüllbar ist)zum letzten von mir eingesetzten Wert zurückkehre, diesen um eins reduziere und dann das Programm ab dieser Stelle weiter laufen soll?
Also so:
void FillGaps ( field f) { int j = 0; // Zeile int i = 0; // Spalte int counter = 0; // Zähl wieviele values möglich int TMP = 0; // Merkt sich den value kurz int i_TMP = 0; // Merkt sich i kurz int j_TMP = 0; // Merkt sich j kurz while (CheckIfAnyZero(f) ) { while ( FindGaps(i, j, f) ){ // FindGaps ist true, wenn eine Lücke gefunden wurde, i und j sind Übergangsparameter für die Stelle der Lücke counter = 0; TMP = 0; for ( int value = 1 ; value < 10; value++ ) { if ( CheckRow (value, j, f) && CheckColumn (value, i, f) && CheckBox (i, j, value, f) ) { TMP = value; counter++; // Zählt an dieser Stelle wieviele Werte die Lücke füllen könnten } } if ( counter < 2) { // eine Zahl darf nur eingesetzt werden, wenn sie die einzige mögliche Zahl ist f[j][i] = TMP; i_TMP = i; j_TMP = j; } else { // da keine Zahl eingesetzt werden konnte, geht das Programm einen Schritt zurück / Backtracking i = i_TMP; j = j_TMP; f[j][i]--; } i++; // damit FindGaps ein Feld weiter geht } } }Tut mir Leid falls die Fragen dumm sein sollten, ich bin noch eher ein Anfänger
LG