Пробовали ли вы когда-нибудь расставить 8 ферзей на шахматной доске так, чтобы ни один из них не находился под ударом? Зная, что ферзь бьет по вертикали, горизонтали и диагонали, довольно непросто подобрать такую позицию. Таких вариантов 92. Один из них:
Расставить 8 ферзей
Сообщений 1 страница 3 из 3
Поделиться22007-03-15 01:08:28
На С:
int col[8], up_free[15], dn_free[15], coln[8] ;
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 ;
clrscr( ) ;
addqueen( ) ;
}
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-- ; /* уменьшаем счетчик строк, пробуем следующую комбинацию */
}
Поделиться32007-03-15 01:09:42
А тут есть решение на Паскале + математическое описание. Задача 4.13.