N ферзей

[sidestep]

Расставить N ферзей на шахматном поле N на N, так чтобы они не били друг друга.

Написал программу, использовав алгоритм с возвратом, но еще не оптимизировал его(пока не до этого). Но есть ошибка

Вот код:

#include <stdio.h>
#include <conio.h>

const int N = 4;
int j_deletnoe = 0;


bool checkfull(int my_mat[N][N]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (my_mat[i][j] == 0) {
				return false;
			} else {
				return true;
			}
		}
	}
}

int checkline(int my_i, int my_j, int my_mat[N][N]) {
	for (int j = my_j; j < N; j++) {
		if (my_mat[my_i][j] == 0) {
			return j;
		} else {
			return -1;
		}
	}
}

int addQueen(int my_i, int my_j, int matrix[N][N]) {
	matrix[my_i][my_j] = -2*N;
	for (int j = 0; j< N; j++)
		matrix[my_i][j] += 1;
	for (int i = 0; i < N; i++)
		matrix[i][my_j] += 1;
	for (int k = 0; k < N; k++) {
		if (k + my_i <= N && k + my_j <= N)
			matrix[k+my_i][k+my_j] += 1;
		if (k + my_i <= N && k - my_j >= 0)
			matrix[k+my_i][k-my_j] += 1;
		if (k - my_i >= 0 && k + my_j <= N)
			matrix[k-my_i][k+my_j] += 1;
		if (k - my_i >= 0 && k - my_j <= 0)
			matrix[k-my_i][k-my_j] += 1;
	}

	return 1;
}

int delQueen(int my_i, int my_j, int matrix[N][N]) {
	matrix[my_i][my_j] = 0;
	for (int j = 0; j< N; j++)
		matrix[my_i][j] -= 1;
	for (int i = 0; i < N; i++)
		matrix[i][my_j] -= 1;
	for (int k = 0; k < N; k++) {
		if (k + my_i <= N && k + my_j <= N)
			matrix[k+my_i][k+my_j] -= 1;
		if (k + my_i <= N && k - my_j >= 0)
			matrix[k+my_i][k-my_j] -= 1;
		if (k - my_i >= 0 && k + my_j <= N)
			matrix[k-my_i][k+my_j] -= 1;
		if (k - my_i >= 0 && k - my_j <= 0)
			matrix[k-my_i][k-my_j] -= 1;
	}

	return 1;
}

int krutaya_fun(int i, int j, int s, int matrix[N][N]) {
	
	while (true) {
		//------------------------
		bool a;
		int III, JJJ;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (matrix[i][j] == 0) {
					a = false;
					III = i;
					JJJ = j;
				} else {
					a = true;
				}
			}
		}	

		//--------------------------
		//bool a = checkfull(matrix);
		
		if (a == true) {
			if (s == N) {
				// figachim matricu
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (matrix[i][j] < 0) {
							printf("# ");
						} else {
							printf("0 ");
						}
					}
					printf("\n");
					break;
				}
			} else {
				
				for (int j = 0; j < N; j++) {
					if (matrix[s-1][j] < 0) {
						delQueen(s-1, j, matrix);
						matrix[s-1][j] = 0;
						j_deletnoe = j;
					}
				}
				
				krutaya_fun(s-1, j_deletnoe+1, s, matrix);
			}
			
		} else {
			int j_svobodn = checkline(III, JJJ, matrix);
			
			if (j_svobodn >= 0) {
				addQueen(III, j_svobodn, matrix);
				s++;
			} else {
				for (int j = 0; j < N; j++) {
					if (matrix[III-1][j] < 0) {
						delQueen(III-1, j, matrix);
						matrix[III-1][j] = 0;
						JJJ = j;
					}
				}
				krutaya_fun(III-1, JJJ+1, s-1, matrix);
			}
		}
	}
	
}

int main() {
	
	int matrix[N][N];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			matrix[i][j] = 0;
			printf("%i ", matrix[i][j]);
		}
		printf("\n");
	}

	krutaya_fun(0,0,0,matrix);

	getch();
	return 0;
}

Ошибка: Необработанное исключение в "0x004119c9" в "nferz.exe": 0xC00000FD: Stack overflow.

когда вызывается int krutaya_fun(int i, int j, int s, int matrix[N][N])

[EUGY]

Неудивительно, ведь krutaya_fun вызывает саму себя с одними и теми же параметрами.
Результат - бесконечная рекурсия и переполнение стека.
Вы отладчиком-то пользуетесь?

[sidestep]

а где с теми же параметрами?

[EUGY]

В окне отладки, называемом Call Stack.
krutaya_fun(int i=4, int j=4, int s=1,....

[AlexDark]

Вот тебе рабочая версия... делал когда то, мб поможет

#include<iostream>
#include<stdio.h>

using namespace std;
//Размерность доски NхN (Количество ферзей - N)
   const int N=8;  int X[N];  int Count;

  bool P(int X[N],int k,int y) // Поиск позиции для ферзя
  { int i=0;
   while ((i<k)&&(y!=X[i])&&(abs(k-i)!=abs(y-X[i]))) {i++;}
	 if(i==k)
	 return true;
	 else return false;  }

  void Backtracking(int k) // Поиск с возвратом позиций
  {   int i,y;
     for (y=0;y<N;y++)
       if (P(X,k,y))
	   {  X[k]=y;
		   if (k==N-1)   {
			   for (i=0;i<N;i++){cout<<char('A'+i)<<X[i]+1<<" ";}
			   cout<<endl;
			   Count++;  }
		   Backtracking(k+1); }  }
 int main()
 { for(int i=0;i<N;i++)X[i]=0;
   Count=0;
   cout<<"Rasstanovki "<<N<<" ferzey:"<<endl;
   cout<<"Na doske "<<N<<" na "<<N<<endl;
   Backtracking(0);
   cout<<"Vsego "<<Count<<" rasstanovok";
   system("pause"); }

[EUGY]

if(i==k)
return true;
else return false; }

Предлагаю дополнить:

if(i==k)
    return true;
else if( i!=k)
    return false;
else
    return !true && !false;

return (i==k); // ведь это скучно

[AlexDark]

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

Предлагаю дополнить:

else
    return !true && !false;

return (i==k); // ведь это скучно

это не то чтобы скучно но менее читабельно для непросвященных

[sidestep]

2AlexDark
спасибо, а ты не можешь описать сам алгоритм расстановки ферзей, почему используется такое условие в while? и не могу понять, почему он выводит все варианты расстановок ферзей для каждого N.

[AlexDark]

Если честно признатся сам не очень помню подробности
Смысл там в том что к-вертикаль, а y-горизонталь

функция P - это, проверка позиции (комент неправильный)...
т.е. для k-й вертикали, и y-й горизонтали

while ((i<k)&&(y!=X[i])&&(abs(k-i)!=abs(y-X[i]))) {i++;}

(i<k) - проверяем шо там понаставляли на предыдущих вертикалях

(y!=X[i]) не на одной горизонтали

(abs(k-i)!=abs(y-X[i])) - не на одной диагонали

т.е. если на предыдущих вертикалях нет ферзей которые бъют ферзя на [k,y], то цикл выйдет с i=k; значит позиция есть.



функция backtracking выполняет именно перебор позиции на очередной вертикали и когда доходит до k = N-1 т.е. последней вертикали, и находит там позицию то выводит что получилось, ну и вся эта рекурсия катится дальше, поэтому выводятся все полученные.

[sidestep]

а где происходит возврат, при неудачной попытке расстановки? тут же только увеличивается k, я что-то не заметил