Sudoku-Rätsel lösen lassen
-
Um noch mal auf die Sudokugeschichte zurückzukommen...
Mit Hilfe dieses Videos www.youtube.com/watch?v=F8JYIUOn_L4&hd=1
bin ich zu dem Code gekommen:
#include <cstdlib> #include <iostream> using namespace std; void draw(int feld[][8]) { for (int zeile = 0; zeile < 9; ++zeile) { for(int spalte = 0; spalte < 9; ++spalte) { cout << feld[spalte][zeile] << " "; } cout << endl; } } void eingabe(int feld[][8]) { int spalte; int zeile; int wert; char input = ' '; while(input != 'q') { cout << "Ihr Sodokufeld: " << endl << endl; cout << "------------------------------------------" << endl << "-|| 0 | 1 | 2 || 3 | 4 | 5 || 6 | 7 | 8 ||" << endl << "-||-----------||-----------||-----------||" << endl << "0|| x | x | x || x | x | x || x | x | x ||" << endl << "1|| x | x | x || x | x | x || x | x | x ||" << endl << "2|| x | x | x || x | x | x || x | x | x ||" << endl << "-||-----------||-----------||-----------||" << endl << "3|| x | x | x || x | x | x || x | x | x ||" << endl << "4|| x | x | x || x | x | x || x | x | x ||" << endl << "5|| x | x | x || x | x | x || x | x | x ||" << endl << "-||-----------||-----------||-----------||" << endl << "6|| x | x | x || x | x | x || x | x | x ||" << endl << "7|| x | x | x || x | x | x || x | x | x ||" << endl << "8|| x | x | x || x | x | x || x | x | x ||" << endl; cout << endl << "Spalte (0-8): "; cin >> spalte; cout << endl << "Zeile (0-8): " ; cin >> zeile; cout << endl << "Wert (1-9) "; cin >> wert; feld[spalte][zeile] = wert; cout << endl << "'q' + Enter zum fertigstellen. Beliebige Taste + Enter zum fortfahren." << endl << endl; cin >> input; } } bool chkZeile(int zeile, int wert, int arr[8][8]) { for (int spalte = 1; spalte < 9; ++spalte) //für Spalten-koordinate { if (arr[spalte][zeile] == wert) //wenn Feld (spalte, koordinnate) schon wert hat { return false; } } return true; } bool chkSpalte(int spalte, int wert, int arr[8][8]) { for (int zeile = 1; zeile < 9; ++zeile) { if (arr[spalte][zeile] == wert) { return false; } } return true; } bool chkBox(int spalte, int zeile, int wert, int arr[8][8]) { for (int i = 1; i < 9; ++i) { for (int j = 1; i < 9; ++i) { if (arr[spalte - (spalte%3) + i][zeile - (zeile%3) + j] == wert) //von links-oben nach rechts-unten { return false; } } } return true; } bool chkall(int spalte, int zeile, int wert, int arr[8][8]) { if (chkZeile(zeile, wert, arr) == false) { return false; } if (chkSpalte(spalte, wert, arr) == false) { return false; } if (chkBox(spalte, zeile, wert, arr) == false) { return false; } return true; } int solve(int spalte, int zeile, int wert, int arr[8][8]) { int workarr[8][8]; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { workarr[i][j] = arr[i][j]; } } workarr[zeile][spalte] = wert; for (int x = 0; x < 9; ++x) { for (int y = 0; y < 9; ++y) { if(workarr[x][y] == 0) { for (int val = 1; val < 9; ++val) { if(chkall(x,y,val,workarr)) { solve(x,y,val,workarr); } } return NULL; } } } } int main(int argc, char *argv[]) { int feld[8][8] = {0}; eingabe(feld); solve(0,0,0,feld); draw(feld); system("Pause"); return 0; }Es wird jetzt an der Stelle angehalten, an der ich eine Kopie von dem der Funktion übergebenem Array, um damit dann weiter zu arbeiten, kommt die Fehlermeldung:
Unbehandelte Ausnahme bei 0x012b8d38 in Sudoku-Löser.exe: 0xC0000005: Zugriffsverletzung beim Lesen an Position 0xa835bbca.
Weiß da jmd. einen Rat? :o
-
bitte lösche den code da, das ist einfach nur c mit cout, absolut unbrauchbar. gründe für den runtime error:
1. zeile 13 (vll solltest du dir array-indices nochmals anschauen)
2. zeile 65 (dito)
3. zeile 78 (dito)
4. zeile 93 (dito)
5. zeile 139 (dito)
6. zeile 143 (dito)
7. zeile 124 (stackoverflow wenn zu tiefe rekursion)
-
1. zeile 13 (vll solltest du dir array-indices nochmals anschauen)
Was soll denn damit sein?
-
Goldienator schrieb:
1. zeile 13 (vll solltest du dir array-indices nochmals anschauen)
Was soll denn damit sein?
Zähl mal alle Zahlen von 0 an, die kleiner sind als 9. Wie viele sind das?
-
0, 1, 2, 3, 4, 5, 6, 7, 8
Sind neun Zahlen
-
Oder irr ich mich da?
-
Goldienator schrieb:
Sind neun Zahlen
Und wie groß ist dein Feld?
-
Und wie groß ist dein Feld?
0-8 (also 9) Zeilen und 0-8 Spalten.
Sind ja dann insgesamt 81...Sieht man doch eigentlich auch im Code oder?
cout << "------------------------------------------" << endl << "-|| 0 | 1 | 2 || 3 | 4 | 5 || 6 | 7 | 8 ||" << endl << "-||-----------||-----------||-----------||" << endl << "0|| x | x | x || x | x | x || x | x | x ||" << endl << "1|| x | x | x || x | x | x || x | x | x ||" << endl << "2|| x | x | x || x | x | x || x | x | x ||" << endl << "-||-----------||-----------||-----------||" << endl << "3|| x | x | x || x | x | x || x | x | x ||" << endl << "4|| x | x | x || x | x | x || x | x | x ||" << endl << "5|| x | x | x || x | x | x || x | x | x ||" << endl << "-||-----------||-----------||-----------||" << endl << "6|| x | x | x || x | x | x || x | x | x ||" << endl << "7|| x | x | x || x | x | x || x | x | x ||" << endl << "8|| x | x | x || x | x | x || x | x | x ||" << endl;
-
Goldienator schrieb:
Und wie groß ist dein Feld?
0-8 (also 9) Zeilen und 0-8 Spalten.
Sind ja dann insgesamt 81...Sieht man doch eigentlich auch im Code oder?
nicht die Zeichen, die du ausgibst. Wie groß ist dein Array?
-
nicht die Zeichen, die du ausgibst. Wie groß ist dein Array?
Ich glaub ich versteh jetzt was ihr sagen wollt
Wenn ich ein Array mit 8 Speicherplätzen erstelle, kann ich das Array nur bis [7] ansprechen, weil [0] ja auch zu den 8 Plätzen dazu zählt, oder?!
-
Goldienator schrieb:
Wenn ich ein Array mit 8 Speicherplätzen erstelle, kann ich das Array nur bis [7] ansprechen, weil [0] ja auch zu den 8 Plätzen dazu zählt, oder?!
So ist es.
-
Argghh... jetzt bin ich komplett verwirrt
-
damit du ein array hast mit 9 einträgen musst du es mit "int array[9]" definieren und kannst es dann mit "array[0]" ... "array[8]" ansprechen.
-
Okay... hab ich so weit verstanden
Jetzt erklärt mir das mal bitte mit dem Stackoverflow bei einer zu tiefen Rekursion...
Was ist damit genau gemeint?
-
mach einfach eine klasse die ein sudoku-spielfeld darstellt und intern einen vektor benutzt. etwa so:
#include <vector> #include <iostream> using namespace std; class sudoku { public: enum { width = 9, height = 9 }; private: vector<int> data; public: sudoku(int fill = 0) : data(width * height, fill) { } void solve() { //... } int operator() (size_t x, size_t y) const { return data[x + y * width]; } int& operator() (size_t x, size_t y) { return data[x + y * width]; } }; ostream& operator<< (ostream& s, sudoku const& d) { //... } int main() { sudoku mein_spielfeld; mein_spielfeld(0, 0) = 1; mein_spielfeld.solve(); cout << mein_spielfeld; }das ganze ist viel einfacher zu bedienen...
das mit dem möglichen stackoverflow wird damit gerade auch behoben denn ein std::vector speichert seine elemente auf dem heap. (bzw. nein, er legt sie mit new[] an aber damit wird normalerweise der heap angesprochen)
-
Goldienator schrieb:
Okay... hab ich so weit verstanden
Jetzt erklärt mir das mal bitte mit dem Stackoverflow bei einer zu tiefen Rekursion...
Was ist damit genau gemeint?
Jeder rekurtsive Aufruf braucht ein wenig Stackspeicher, so 20-50 Bytes vielleicht. Ruft sich eine Funktion oft selber auf, vieltausenmal, kann der STack ausgehen und das Programm stürzt ab.
Wird Dir aber nicht passieren, weil Du bei vor jedem Abstieg eine Zahl einträgst und nach jedem Aufstieg sie wieder austrägst. Kannst nicht tiefer als 81 Ebenen abteigen. 81 ist voll unkritisch.
Sogar, wenn Du nicht streichst (warum nicht, ist doch viel schneller und einfach genug), sondern Kopien hältst, wie Du es mit dem workarray machst, 81*sizeof(int)*81 ist auch locker um die 30k, kannst davon ausgehen, ca 1M zu haben.
