backtracking

[ARLy_19]

Здравствуйте
не можете объяснить что делает valid и bkt?
в теории я знаю что такое "поиск с возвратом", но не могу понять код
спасибо!

int n, sol[10];

int valid(int k) {
	for (int i = 1; i < k; i++)
		if (sol[i] == sol[k])
		return 0;
	if (k % 2 == 0 && sol[k] != k)
		return 0;
	return 1;
}

void pokaz() {
	for (int i = 1; i <= n; i++) {
		cout << sol[i] << " ";
	}
		cout << endl;
	
}

void bkt(int k) {
	for (int i= 1; i <= n; i++) {
	sol[k]= i;
	if (valid(k))
		if (k == n)
			pokaz();
			
		else
			bkt(k + 1);
	}
}

void main () {
  printf("n= ");
  scanf("%d", &n);
  bkt(1);
	_getch();
}

[p51x]

Очередной код перелизанный с паскаля на С с багом.

Сообщение от ARLy_19

не можете объяснить что делает valid и bkt?
в теории я знаю что такое "поиск с возвратом", но не могу понять код

Видимо не знаете. Даже названия подсказывают.
valid - проверяет правильность решения
bkt - основная функция бкт, пытается делать шаги алгоритма

[ARLy_19]

это я понимаю
я не пойму что делает этот кусок кода

for (int i = 1; i < k; i++)
		if (sol[i] == sol[k])
                return 0;

и почему в main у bkt параметр = 1

[p51x]

Сообщение от ARLy_19

я не пойму что делает этот кусок кода

очевидно проверяет, что в решении все значения различны

Сообщение от ARLy_19

и почему в main у bkt параметр = 1

потому что решения строятся по шагам (цепочкой) и, естественно, первая цепочка состоит из 1 элемента
1
1 2
1 2 3
...

[ARLy_19]

а этот тогда что делает?

if (k % 2 == 0 && sol[k] != k)
		return 0;

[p51x]

вы не поверите... но именно то, что написано... Вы знаете, что такое if?

[ARLy_19]

знаю
пока формулировала что не поняла получилось понять
благодарю