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

Путь обхода конём всех 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 влево
На главную страницу.