Бесплатная реклама

Сниппеты

Обход шахматной доски конём

C++

Решение задачи с помощью алгоритма перебора с возвратом. Ход шахматного коня - начертание буквы «Г». Найти путь коня, состоящий из всех полей шахматной доски, и не содержащий ни одного поля более чем один раз.


#include <stdio.h>
#include <conio.h>


int i,j, n, nsqr, q;
int dx[9], dy[9], h[29][29];

void prnt(void)
  {
  int p, r ;
  for (p = 1 ; p<=n ; p++)
    {
    for ( r = 1 ; r<=n ; r++ )
        printf("%2d ", h[p][r] );
    printf("\n");
    }
  printf("\n");
  }
 
// возвращает 1, если доска заполнена, 0 - если нет продолжений
int t (int i, int x, int y)
  {
  int j, u, v , q1=0;
  for (j=1; (!q1) && (j<=8); j++)
    {
    u = x+dx[j];
    v = y +dy[j];
    if ( 1<= u && u <=n && 1 <=v && v<=n && h[u][v]==0)
      {
      h[u][v] = i;
      if (i<nsqr)
        {
        q1 = t (i+1, u, v);
        if (q1==0) h[u][v]=0;
        }
        else q1 = 1;
      }
    }
  return q1 ;
  }

main()
  {
  dx[1] =  2;  dx[2] =  1;  dx[3] = -1;  dx[4] = -2;
  dx[5] = -2;  dx[6] = -1;  dx[7] =  1;  dx[8] =  2;
  dy[1] =  1;  dy[2] =  2;  dy[3] =  2;  dy[4] =  1;
  dy[5] = -1;  dy[6] = -2;  dy[7] = -2;  dy[8] = -1;
  n=8;
  nsqr = n*n;
  clrscr();
  h[1][1]=1;
  if (t (2, 1, 1)==0) printf("\nнет решений");
    else prnt();
  getch();
  }