Задача с ферзями, С++/Pascal

[dessaber]

Народ, помогите решить задачу.
Задача, во многом, известная: нужно разместить 8 ферзей на шахматной доске, чтобы они не били друг друга.
НО: обязательно использование рекурсии + пользователь вводит номер строки и столбца одной из клеток и указывает её значение (0, если оставить клетку пустой, и 1, если поместить в неё ферзя). Соответственно, на выходе выводится матрица с 0-ми и 1-ми. Определенные наработки есть, но толку от них чуть.

Нужен код на С++ и Pascal.

Заранее спасибо.

[rrrFer]

прилагай наработки и излагай конкретно в чем проблема. В интернетах можно найти эту задачу уже решенной, может быть, за исключением:

пользователь вводит номер строки и столбца одной из клеток и указывае

вся рекурсивная функция(получает координаты текущей, просматриваемой клетки поля в качестве параметров) :

в двух циклах, один из которых вложен в другой перебираю все клетки поля, начиная с текущей{
    если(удалось поставить ферзя()) {
        увеличиваю счетчик ферзей;
        вычисляю координаты следующей клетки поля;
        рекурсивный вызов функцией самой себя, параметры - координаты новой клетки;
        снимаю ферзя();
        уменьшаю счетчик ферзей;
    }
}

вроде-бы как-то так, не проверял, могут быть ошибки тут ))

при установке ферзя и при его снятии с доски нужно разметить клетки, которые он бьет.
структура клетки может быть такой:

struct cell{
   int type; //тип клетки, 0 - фигура, 1 - пустая клетка
   int value; //если тип=1 - то в этом поле может быть "урон", который фигуры наносят на эту клетку
    //если тип=0 - то это может быть вид фигуры, если нам надо расставлять не только ферзей, но и лошадей например
};

хотя, по конкретной задаче value не особенно нужно если тип=0.
Но для тип=1 - это очень удобно, вместо матрицы с 0 и 1 будет матрица с 0 и разными числами ))
это упрощает процесс снимания ферзя с доски, когда снимаешь ферзя - надо отметить клетки, которые он бил (потому что после снятия он их не бьет, а значит в них можно что-нибудь поставить). Возможна ситуация когда несколько ферзей бью одну клетку, если в этом случае мы используем матрицу из 0 и 1 - то чтобы правильно отметить битые клетки - надо снять ферзя, отметить все пустые клетки доски как небитые, перебрать все оставшиеся на доске фигуры и отметить для каждой клетки, которые она бьет.
Если же считать число фигур, которые бьют клетку - то после съема фигуры достаточно уменьшить это значение(value) на единицу для всех клеток, котоыре била эта фигура.

[dessaber]

удалось поставить ферзя()

один из ключевых моих камней преткновения. Не могу сделать лаконичное условие. В итоге приходится перебирать клетки вне пределов массива. Мб в этом проблема. Так-то они 0 по умолчанию, но все-таки.

снимаю ферзя();
уменьшаю счетчик ферзей;

Встречал уже подобные решения, никак не могу понять в какой ситуации мне может понадобиться снимать его с доски. А даже если и могу, то как передать условие, что вот сейчас, мол, надо снимать)

вычисляю координаты следующей клетки поля

рекурсивный вызов функцией самой себя, параметры - координаты новой клетки

Имеется ввиду передача координат из счетного цикла?

[rrrFer]

dessaber
если текущие координаты клетки поля это (i,j)
то координаты следующей клетки поля это (i,j+1) если j+1<n
или(i+1,0) если j+1>=n.
снимать ферзя надо, т.к. используется перебор с возвратами, т.е. фактически перебираются вообще все варианты размещения ферзей.
Могу написать вам программу за не большое материальное вознаграждение - обращайтесь ICQ 395-546-218,почта [ник на форуме]@mail.ru, или выкладывайте свои конкретные попытки(не копипаст из интернетов) и конкретные вопросы.

[rrrFer]

вот проверка возможности установки ферзя:

bool field::checkQueenTo(int ii,int jj){
	int i,j;
	//проверка вертикалей и горизонталей:
	for(i=0;i<n;i++)
		if((i!=ii&&t[i][jj].type==1)||(i!=jj&&t[ii][i].type==1))
			return 0;
	//проверка диагоналей
	for(i=ii+1,j=jj+1;i<n&&j<n;i++,j++)
		if(t[i][j].type==1)
			return 0;
	for(i=ii+1,j=jj-1;i<n&&j>=0;i++,j--)
		if(t[i][j].type==1)
			return 0;
	for(i=ii-1,j=jj+1;i>=0&&j<n;i--,j++)
		if(t[i][j].type==1)
			return 0;
	for(i=ii-1,j=jj-1;i>=0&&j>=0;i--,j--)
		if(t[i][j].type==1)
			return 0;
	return 1;
}

t - это двумерный массив, образ доски.
t[i][j].type = 1 если в клетке i,j стоит фигура
После установки ферзя надо пометить клетки которые он бьет, для этого можно исопльзовать что-то вроде:

bool field::tokenQueenTo(int ii,int jj,int flag){
	int i,j;
	if(!checkQueenTo(ii,jj))
		return 0;
	//------------разметка битых полей
	//разметка вертикалей и горизонталей:
	for(i=0;i<n;i++){
		if(i!=ii)
			t[i][jj].damage+=flag;
		if(i!=jj)
			t[ii][i].damage+=flag;
	}
	//разметка диагоналей
	for(i=ii+1,j=jj+1;i<n&&j<n;i++,j++)
		t[i][j].damage+=flag;
	for(i=ii+1,j=jj-1;i<n&&j>=0;i++,j--)
		t[i][j].damage+=flag;
	for(i=ii-1,j=jj+1;i>=0&&j<n;i--,j++)
		t[i][j].damage+=flag;
	for(i=ii-1,j=jj-1;i>=0&&j>=0;i--,j--)
		t[i][j].damage+=flag;
	return 1;
}

[rrrFer]

во второй функции flag = 1 если устанавливаем ферзя, и -1 если снимаем ферзя ))
а кроме разметки надо отметить клетку, непосредственно в которой стоит фигура:

bool field::setFigure(int ii,int jj,char c,int flag){
		//проверка текушей клетки:
	if(flag==1){
		if(t[ii][jj].type==1||t[ii][jj].damage)
			return 0;
		//------------уствновка фигуры
		t[ii][jj].type=1;
		t[ii][jj].damage=c;
	}
	else
		t[ii][jj].type=t[ii][jj].damage=0;
	return 1;
}

тут t[i][j].damage выполняет ту же роль что я описал для t[i][j].value
t[ii][jj].damage=c; означает что в этом поле может хранится тип фигуры, т.е. вызов может быть примерно такой:
setFigure(ii,jj,'R',flag)
значит что в клетку ii,jj ставим фигуру(type=1) с value='R'