Слоны

[[MI_nor]]

Помогите с алгоритмом...требуется расставить 8 слонов на шахматном поле так чтобы каждое поле находилось под ударом одного из них...нужно найти все варианты. Сама задача не сложная конечно...но вот если реализовывать полный перебор к примеру, то там получается туева куча вариантов...это хорошая нагрузка...может кто-то подсказать более экономный вариант?

[ISergeyN]

чтобы каждое поле находилось под ударом одного из них...

Может чтобы они друг друга не били (обычно так задача ставилась)

[[MI_nor]]

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

Может чтобы они друг друга не били (обычно так задача ставилась)

Ну можно и так, хотя смысл практически один и тот-же

[TAVulator]

Помогите с алгоритмом...требуется расставить 8 слонов на шахматном поле так чтобы каждое поле находилось под ударом одного из них...нужно найти все варианты.

Я тебе так скажу - 16 вариантов.
Нужно слоны поставить в одну линию. Таких возможностей всего 16.
Если ошибаюсь - поправьте. Хочу узнать еще варианты как поставить слонов )))

[ISergeyN]

Нужно слоны поставить в одну линию. Таких возможностей всего 16.

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

#include <iostream>
void addqueen();

int col[8], up_free[15], dn_free[15], coln[8] ;
int main()
{            
	int i ;

	for ( i = 0 ; i <= 7 ; i++ )
		col[i] = 1 ;
	for ( i = 0 ; i <= 14 ; i++ )
		up_free[i] = dn_free[i] = 1 ;
	system("cls");
	addqueen( ) ;  
	return 0;
}            

void addqueen( )            
{            
	int i, c, r ;            
	static int comb, row = -1 ;

	row++ ;

	/* Проверяем колонки */            
	for ( i = 0 ; i <= 7 ; i++ )            
	{            
		/* если клетка не находится под ударом */            
		if ( col[i] && up_free[i+row] && dn_free[row-i+7])
		{            
			/* запоминаем, что в строке находится ферзь */
			coln[row] = i ;

			/* маркируем колонку и диагональ */ 
			col[i] = 0 ;             
			up_free[i+row] = 0 ;             
			dn_free[row-i+7] = 0 ;

			/* если заполнены все строки */            
			if ( row >= 7 )            
			{            
				comb++ ;            
				printf ( "\n\n\ncombination no. %d", comb ) ;
				for ( r = 0 ; r <= 7 ; r++ )
				{            
					printf ( "\n" ) ;            
					for ( c = 0 ; c <= 7 ; c++ )
					{            
						if ( c == coln[r] )            
							printf ( " Q " ) ;
						else            
							printf ( " . " ) ;
					}            
				}            
			}            
			else            
				addqueen( ) ;

			/* снимаем пометку с колонки и диагонали */            
			col[ coln[row] ] = 1 ;            
			up_free[ row + coln[row] ] = 1 ;            
			dn_free[ row - coln[ row ] + 7 ] = 1 ;            
		}            
	}            
	row-- ; /* уменьшаем счетчик строк, пробуем следующую комбинацию */
}

Вот глянь (ели не видел..) http://www.codenet.ru/progr/alg/ferzi.php

[TAVulator]

глянул.

Зная, что ферзь бьет по вертикали, горизонтали и диагонали

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

[ISergeyN]

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

Точно.. напутал (просто когда учили в шахматы то все фигуры по другому называли.. )

[[MI_nor]]

Да не совсем, вариантов там больше 16) стандартные 16(как вы сказали) + например вот такой вариант...

0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0

[TAVulator]

0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0

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

так чтобы каждое поле находилось под ударом одного из них

[[MI_nor]]

0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0

Эм, как ходят Ваши слоны? Я привык что они могут ходить вправо/влево/вверх/вниз по всей ширине доски) тогда получается что если поставить слона как Вы говорили(зеленый) то его будет бить слон(красный)...
З.Ы но такой вариант не приемлем ввиду того что условие "ОДНОГО из них" не выполняется, несмотря на то что кадое поле под "ударом"...