Путь обхода конём всех 36 клеток шахматной доски размера 6x6.

Конь занимает каждое поле шахматной доски только по одному разу.

Рекурсия.

Программа knight6r.zip

Код программы knight6r.zip(DOS-кодировка)

Цикл.

Программа knight5z.zip

Код программы knight5z.zip(DOS-кодировка)

Рекурсия.

/*Путь обхода конём всех 36 клеток шахматной доски размера 6x6. Рекурсия. */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <conio.h>

using namespace std;

const n = 6;        //длина шахматной доски

int x[n*n+1];       //номер горизонтали на k-м шаге, 1<=k<=n*n, 1<=x[k]<=n 
int y[n*n+1];       //номер горизонтали на k-м шаге, 1<=k<=n*n, 1<=y[k]<=n 
bool r[n*n+2];      //r[p[k]]==true = занята клетка с номером p[k]=n*(x[k]-1)+y[k] на k-м шаге, 1<=k<=n*n
FILE *f;            //файл для хранения результата
float time1;        //время начала работы
float time2;        //время нахождения очередного решения 
int u;              //номер решения
double c;           //количество ходов
char fileout[15];   //имя файла для хранения результата

void chessknight(int k);  //Функция поиска всех решений при помощи рекурсии
void print();             //Вывод решения в файл
void input();             //Ввод данных
void output();            //Завершение работы   

int main()
{ 
   input();
   float time1=clock(); 
   u = 0; 
   c = 0;
   r[n*(x[1]-1)+y[1]] = true;
   chessknight(1);
   output();
   getch(); 
   return 0;
}

void chessknight(int k)
{
   c++; 
   if (k==n*n)    print(); 
   if  ((r[n*x[k]+y[k]+2]==false) && (x[k]<=n-1) && (y[k]<=n-2))
   {
      r[n*x[k]+y[k]+2] = true;
      x[k+1] = x[k]+1;
      y[k+1] = y[k]+2;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]+1)+y[k]+1]==false) && (x[k]<=n-2) && (y[k]<=n-1))
   {
      r[n*(x[k]+1)+y[k]+1] = true;
      x[k+1] = x[k]+2;
      y[k+1] = y[k]+1;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]+1)+y[k]-1]==false) && (x[k]<=n-2) && (y[k]>=2))
   {
      r[n*(x[k]+1)+y[k]-1] = true;
      x[k+1] = x[k]+2;
      y[k+1] = y[k]-1;
      chessknight(k+1);
   } 
   if  ((r[n*x[k]+y[k]-2]==false) && (x[k]<=n-1) && (y[k]>=3))
   {
      r[n*x[k]+y[k]-2] = true;
      x[k+1] = x[k]+1;
      y[k+1] = y[k]-2;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-2)+y[k]-2]==false) && (x[k]>=2) && (y[k]>=3))
   {
      r[n*(x[k]-2)+y[k]-2] = true;
      x[k+1] = x[k]-1;
      y[k+1] = y[k]-2;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-3)+y[k]-1]==false) && (x[k]>=3) && (y[k]>=2))
   {
      r[n*(x[k]-3)+y[k]-1] = true;
      x[k+1] = x[k]-2;
      y[k+1] = y[k]-1;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-3)+y[k]+1]==false) && (x[k]>=3) && (y[k]<=n-1))
   {
      r[n*(x[k]-3)+y[k]+1] = true;
      x[k+1] = x[k]-2;
      y[k+1] = y[k]+1;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-2)+y[k]+2]==false) && (x[k]>=2) && (y[k]<=n-2))
   {
      r[n*(x[k]-2)+y[k]+2] = true;
      x[k+1] = x[k]-1;
      y[k+1] = y[k]+2;
      chessknight(k+1);
   }
   r[n*(x[k]-1)+y[k]] = false;
   x[k] = 1;
   y[k] = 0;
   c++;
}

void print()
{  
   u++;
   float time2 = clock(); 
   printf("Решение  %6d найдено. Время работы = %3.3f  с\n", u,  (time2-time1)/1000);
   f = fopen(fileout, "a");
   fprintf(f,"The solution %6d,  step = %e,  time = %3.3f s:\n", u, c, (time2-time1)/1000);
   for (int k=1; k<=n*n; k++)  fprintf(f, "%2d  %c%d  %2d\n", k, x[k]+96, y[k], n*(x[k]-1)+y[k]);
   fprintf(f,"\n");
   fclose(f);
}

void input()
{
   cout << "Путь обхода конём всех " << n*n <<" клеток шахматной доски размера "<< n <<"x" << n <<". Рекурсия\n"; 
   char x0;
   char y0;
   do
   {
     printf("Введите одну из %d букв: a..%c:   ", n, 96+n);
     cin >> x0;
   }
   while ((x0 <'a')||(x0>96+n)); 
   do
   {
     printf("Введите одну из %d цифр: 1..%c:   ", n, 48+n);
     cin >> y0;
   }
   while ((y0 <'1')||(y0>48+n)); 
   strcpy(fileout, "knight ");
   fileout[strlen(fileout)-1]=n+48;
   char v0[] = "  ";
   v0[0] = x0; 
   v0[1] = y0;
   strcpy(fileout+strlen(fileout), v0);
   strcpy(fileout+strlen(fileout), "r.txt");
   time1=clock(); 
   f = fopen(fileout, "w");
   fprintf(f, "This program use recursion.\n");
   fprintf(f, "The course of knight on chess board. \n");
   fprintf(f, "The chess board have size %dx%d, %d fields. \n", n, n, n*n);
   fprintf(f, "The knight occupy every fields only one times. \n\n");
   fclose(f);
   for (int k=0; k<=n*n; k++) x[k] = 1;
   for (int k=0; k<=n*n; k++) y[k] = 0;
   x[1] = x0-96;
   y[1] = y0-48;
   for (int k=0; k<=n*n; k++) r[k] = false;
}

void output()
{
   float time2 = clock(); 
   printf("Время работы  =  %6.3f    с\n",  (time2-time1)/1000); 
   f = fopen(fileout, "a");
   fprintf(f, "The total time  =  %6.3f    seconds\n",(time2-time1)/1000); 
   if (u==0) fprintf(f, "There is no  solutions\n");
   else fprintf(f, "Numbers of solutions =  %d\n", u);
   fprintf(f, "The total numbers of steps =  %e\n", c); 
   fclose(f);
   cout << "Сделано всего пробных ходов конём: "  << c <<'\n'; 
   if (u==0) cout << "Решений нет\n"; 
   else cout << "Решения сохранены в файле " << fileout  <<'\n'; 
}

Цикл.

/*Путь обхода конём всех 36 клеток шахматной доски размера 6x6. Цикл. */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <conio.h>

using namespace std;

const n = 6;        //длина шахматной доски

int x[n*n+1];       //номер горизонтали на k-м шаге, 1<=k<=n*n, 1<=x[k]<=n 
int y[n*n+1];       //номер горизонтали на k-м шаге, 1<=k<=n*n, 1<=y[k]<=n 
int s[n*n+1];       //номер варианта хода на k-м шаге, 1<=k<=n*n, 1<=s[k]<=8
bool r[n*n+2];      //r[p[k]]==true = занята клетка с номером p[k]=n*(x[k]-1)+y[k] на k-м шаге, 1<=k<=n*n
FILE *f;            //файл для хранения результата
float time1;        //время начала работы
float time2;        //время нахождения очередного решения 
int u;              //номер решения
double c;           //количество ходов
char fileout[15];   //имя файла для хранения результата

void knightpass();  //Функция поиска всех решений при помощи циклов
void print();       //Вывод решения в файл
void input();       //Ввод данных
void output();      //Завершение работы   

int main()
{ 
   input();
   float time1=clock(); 
   u = 0; 
   c = 0;
   r[n*(x[1]-1)+y[1]] = true;  
   s[1] = 0;
   knightpass();
   getch(); 
   return 0;
}

void knightpass()
{ 
   int k = 0;
   while (1)
   {  
      k++;
      c++;
      if(k==n*n) print();
      while(1)      
      {
         s[k] = s[k]+1;
         if  ((s[k]==1) && (r[n*x[k]+y[k]+2]==false) && (x[k]<=n-1) && (y[k]<=n-2))
         {
            r[n*x[k]+y[k]+2] = true;
            x[k+1] = x[k]+1;
            y[k+1] = y[k]+2;
            s[k+1] = 0;
            break;
         }
         if  ((s[k]==2) && (r[n*(x[k]+1)+y[k]+1]==false) && (x[k]<=n-2) && (y[k]<=n-1))
         {
            r[n*(x[k]+1)+y[k]+1] = true;
            x[k+1] = x[k]+2;
            y[k+1] = y[k]+1;
            s[k+1] = 0;
            break;
         }
         if  ((s[k]==3) && (r[n*(x[k]+1)+y[k]-1]==false) && (x[k]<=n-2) && (y[k]>=2))
         {
            r[n*(x[k]+1)+y[k]-1] = true;
            x[k+1] = x[k]+2;
            y[k+1] = y[k]-1;
            s[k+1] = 0;
            break;
         } 
         if  ((s[k]==4) && (r[n*x[k]+y[k]-2]==false) && (x[k]<=n-1) && (y[k]>=3))
         {
            r[n*x[k]+y[k]-2] = true;
            x[k+1] = x[k]+1;
            y[k+1] = y[k]-2;
            s[k+1] = 0;
            break;
         }
         if  ((s[k]==5) && (r[n*(x[k]-2)+y[k]-2]==false) && (x[k]>=2) && (y[k]>=3))
         {
            r[n*(x[k]-2)+y[k]-2] = true;
            x[k+1] = x[k]-1;
            y[k+1] = y[k]-2;
            s[k+1] = 0;
            break;
         }
         if  ((s[k]==6) && (r[n*(x[k]-3)+y[k]-1]==false) && (x[k]>=3) && (y[k]>=2))
         {
            r[n*(x[k]-3)+y[k]-1] = true;
            x[k+1] = x[k]-2;
            y[k+1] = y[k]-1;
            s[k+1] = 0;
            break;
         }
         if  ((s[k]==7) && (r[n*(x[k]-3)+y[k]+1]==false) && (x[k]>=3) && (y[k]<=n-1))
         {
            r[n*(x[k]-3)+y[k]+1] = true;
            x[k+1] = x[k]-2;
            y[k+1] = y[k]+1;
            s[k+1] = 0;
            break;
         }
         if  ((s[k]==8) && (r[n*(x[k]-2)+y[k]+2]==false) && (x[k]>=2) && (y[k]<=n-2))
         {
            r[n*(x[k]-2)+y[k]+2] = true;
            x[k+1] = x[k]-1;
            y[k+1] = y[k]+2;
            s[k+1] = 0;
            break;
         }
         if (((s[k]==8)&&(r[n*(x[k]-2)+y[k]+2]==true))||((s[k]==9)&&(r[n*(x[k]-1)+y[k]]==true)))  
         {
            r[n*(x[k]-1)+y[k]] = false; 
            x[k] = 1;
            y[k] = 0;
            s[k] = 0;
            k--;
            c++;
            if (k==0)   {output();  return; } 
            continue;
         }
      }
   }
}

void print()
{  
   u++;
   float time2 = clock(); 
   printf("Решение  %6d найдено. Время работы = %3.3f  с\n", u,  (time2-time1)/1000);
   f = fopen(fileout, "a");
   fprintf(f,"The solution %6d,  step = %e,  time = %3.3f s:\n", u, c, (time2-time1)/1000);
   for (int k=1; k<=n*n; k++)  fprintf(f, "%2d  %c%d  %2d\n", k, x[k]+96, y[k], n*(x[k]-1)+y[k]);
   fprintf(f,"\n");
   fclose(f);
}

void input()
{
   cout << "Путь обхода конём всех " << n*n <<" клеток шахматной доски размера "<< n <<"x" << n <<". Цикл.\n"; 
   char x0;
   char y0;
   do
   {
     printf("Введите одну из %d букв: a..%c:   ", n, 96+n);
     cin >> x0;
   }
   while ((x0 <'a')||(x0>96+n)); 
   do
   {
     printf("Введите одну из %d цифр: 1..%c:   ", n, 48+n);
     cin >> y0;
   }
   while ((y0 <'1')||(y0>48+n)); 
   strcpy(fileout, "knight ");
   fileout[strlen(fileout)-1]=n+48;
   char v0[] = "  ";
   v0[0] = x0; 
   v0[1] = y0;
   strcpy(fileout+strlen(fileout), v0);
   strcpy(fileout+strlen(fileout), "z.txt");
   time1=clock(); 
   f = fopen(fileout, "w");
   fprintf(f, "This program use iteration.\n");
   fprintf(f, "The course of knight on chess board. \n");
   fprintf(f, "The chess board have size %dx%d, %d fields. \n", n, n, n*n);
   fprintf(f, "The knight occupy every fields only one times. \n\n");
   fclose(f);
   for (int k=0; k<=n*n; k++) x[k] = 1;
   for (int k=0; k<=n*n; k++) y[k] = 0;
   x[1] = x0-96;
   y[1] = y0-48;
   for (int k=0; k<=n*n; k++) r[k] = false;
}

void output()
{
   float time2 = clock(); 
   printf("Время работы  =  %6.3f    с\n",  (time2-time1)/1000); 
   f = fopen(fileout, "a");
   fprintf(f, "The total time  =  %6.3f    seconds\n",(time2-time1)/1000); 
   if (u==0) fprintf(f, "There is no  solutions\n");
   else fprintf(f, "Numbers of solutions =  %d\n", u);
   fprintf(f, "The total numbers of steps =  %e\n", c); 
   fclose(f);
   cout << "Сделано всего пробных ходов конём: "  << c <<'\n'; 
   if (u==0) cout << "Решений нет\n"; 
   else cout << "Решения сохранены в файле " << fileout  <<'\n'; 
   return; 
}

 Сохраните программы knight6r.zip e knight6z.zip в папке. В той же папке будут созданы файлы с решениями.

Следует ввести одну из букв a, b, c, d, e, f, нажать Enter, ввести одну из цифр 1, 2, 3, 4, 5, 6, нажать Enter. Время нахождения всех решений - не более 30 минут.
Номер поля номер поля p=n*(x-1)+y , 1<=x<=n, 1<=y<=n, n=6:

6
12
18
24
30
36
5
11
17
23
29
35
4
10
16
22
28
34
3
9
15
21
27
33
2
8
14
20
26
32
1
7
13
19
25
31


Если на k-м шаге номер поля field = p[k], то на k+1-м шаге возможны следующие 8 ходов:
  1. p[k+1] = p[k]+n+2; - на 2 вверх и на 1 вправо
  2. p[k+1] = p[k]+2*n+1; - на 1 вверх и на 2 вправо
  3. p[k+1] = p[k]+2*n-1; - на 1 вниз и на 2 вправо
  4. p[k+1] = p[k]+n-2;- на 2 вниз и на 1 вправо
  5. p[k+1] = p[k]-n-2; - на 2 вниз и на 1 влево
  6. p[k+1] = p[k]-2*n-1; - на 1 вниз и на 2 влево
  7. p[k+1] = p[k]-2*n+1; - на 1 вверх и на 2 влево
  8. p[k+1] = p[k]-n+2; - на 2 вверх и на 1 влево
На главную страницу.