DOSUG CZ– розовая кнопка на сайте!
Logo

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

Вы, наверное, замечали, что шахматы представляют интерес не только в качестве игры, но и являются "полем битвы" многочисленных головоломок и логических задач. Многие из них основаны на особом ходе коня в виде английской буквы L. Классический пример - поход коня по всей шахматной доске, пришедший к нам из математических трактатов начала 18 века. Проблема состоит в том, чтобы начиная из левого верхнего угла шахматной доски пройти конем так, чтобы фигура побывала в каждой из 64 клеток шихматной доски один и только один раз. Одно из решений этой задачи было предложено Ворнсдорфом (J. C.  Warnsdorff) в 1823 г. Программа, приведенная ниже, предлагает еще одно решение, основанное на использовании рекурсии. 

Самая большая проблема в решении этой задачи - определиться с форматом данных, т.е. как шахматная доска будет храниться в компьютере. Наверное, самым естественным решением было бы представить шахматную доску в виде двумерного массива 8 х 8. Однако, поступим по другому. Используем два одномерных массива row[64] и  col[64]  для хранения соответственно номеров строк и колонок, которые конь последовательно проходит по доске.

Конь, находящийся в позиции ( i, j ), может следующим ходом оказаться в клетках с координатами  (i-2, j+1), (i-1,  j+2), (i+1,  j+2), (i+2, ,j+1),  (i+2, ,j-1), (i+1, j-2),  (i-1, j-2),  (i-2,  j-1). Заметим, что если конь находится вблизи края доски, то некоторые ходы могут вызвать перемещение коня за ее пределы, что, конечно же, недопустимо. Восемь возможных перемещений коня могут быть заданы в виде двух массивов ktmov1[ ] и ktmov2[ ],  как продемонстрировано в следующем фрагменте программы. Исходя из этого, конь, находящийся в позиции (i, j) может переместиться в позицию (i+ktmov[k], j+ktmov2[k]), где k - какое-либо значение из диапазона 0 - 7, выбираемое из условия, что конь должен остаться на доске. Итак, программа, реализующая перемещение коня в соответствии с вышеприведенными условиями будет выглядеть следующим образом:

      int arr[8][8], row[64], col[64] ; int ktmov1[8] = { -2, -1, 1, 2, 2, 1, -1, -2 } ;
      int ktmov2[8] = { 1, 2, 2, 1, -1, -2, -2, -1 } ;
      int i, j, move_num, d ; 
	  
	  main()
      {
	      addknight( ) ;
      }
	  
      addknight( )
      {
	      register int a, b, e ; 
		  
    	  /* пометить клетку как посещенную и запомнить координаты клетки */
	      arr[i][j] = 1 ;
	      row[move_num] = i ;
	      col[move_num] = j ;
    	  move_num++ ;
		  
		  /* проверить 8 возможных перемещений коня */
	      for ( a = 0 ; a <= 7 ; a++ )
	      {
		      /* если все ходы сделаны, печатаем их */
		      if ( move_num >= 64 )
		      {
			      writeboard( ) ; 
			      exit ( 0 ) ;
		      }
			  
		      /* определяем колонку и строку для следующего хода */
		      b = i + ktmov1[a] ;
      		  e = j + ktmov2[a] ;
			  
		      /* проверяем, что после выполенения хода конь остается на шахматной доске */
		      if ( b < 0 || b > 7 || e < 0 || e > 7 )
			      continue ; 
				  
		      /* проверяем, были ли мы уже в этой клетке */
		      if ( arr[b][e] == 1 )
			      continue ; 
		      i = b ;j = e ;
		      addknight( ) ;
	      } 
		  
	      /* уменьшить счетчик ходов и попробовать сделать следующий ход */
    	  move_num-- ;
	  
	      /* освобождаем клетку, ранее занятую конем */
    	  arr[row[move_num]][col[move_num]] = 0 ;
	      move_num-- ;  /* пробуем сделать следующий ход */
	      i = row[move_num] ;j = col[move_num] ;
	     move_num++ ; 
      }
	  
      writeboard( )
      {
	   	  int a ;
		  
    	  clrscr( ) ;
		  gotoxy ( 1, 10 ) ;
      	  printf ( "Hit any key for next move " );
 	      gotoxy ( 1, 11 ) ;
	      for ( a = 0 ; a <= 63 ; a++ )
	      {
		      if ( a % 8 == 0 )
			      printf ( "\n" ) ;
			  printf ( "#" ) ;
	      }
    	  for ( a = 0 ; a <= 63 ; a++ )
	      {
    		  gotoxy ( col[a] * 3 + 1, 12 + row[a] ) ;
		      printf ( "%3d", a + 1 ) ;
		      getch( ) ;
	      }
      }
Удачного программирования!
главная - о проекте - контакты - реклама на сайте
 
LBN100 Elite

SoftStudio.Ru - студия разработки программ
LBN100 Elite