Sudoku-Rätsel lösen lassen

SeppJ

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)

volkard

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.