Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11650
Последний выпуск: 19.06.2015

Расставляем ферзей на шахматной доске

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

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-- ; /* уменьшаем счетчик строк, пробуем следующую комбинацию */
}

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог