Обход доски шахматным конем

@olleg90 · Регистрация: 06.01.2011

Студворк — интернет-сервис помощи студентам

решал задачу "Тур конем". :
На шахматной доске размером n*n на поле с координатами x0,y0 находится конь - фигура , перемещающаяся по шахматным правилам. Задача заключается в поиске последовательности ходов, при которых конь точно один раз побывает на всех полях доски.
Проблема:
Решить задачу самостоятельно не получилось, хоть она и считается классической (на рекурсии с возвратом). воспользовался книгой Н. Вирта "алгоритмы и структуры данных".
нашел там алгоритм и код на паскале.
код:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 program KnightWay;
       const
         n=8;
         dx: array [1..8] of integer=(-1,1,2,2,1,-1,-2,-2);
         dy: array [1..8] of integer=(2,2,1,-1,-2,-2,-1,1);
       var Solution: array [1..n,1..n] of integer;
         // массив ходов
procedure TryM(x,y: integer; var Success: boolean);
 procedure Try0(i,x,y: integer);
 var k,             // номер кандидата
      u,v: integer; // координаты следующего хода коня
 begin
   k:=0;
   repeat
      Inc(k);
      u:=x+dx[k]; v:=y+dy[k];
      if (u>0) and (u<=n) and (v>0) and (v<=n) and
        (Solution[u,v]=0) then
      begin
        Solution[u,v]:=i;
        if i<n*n then
        begin
          Try0(i+1,u,v);
          if not Success then
            Solution[u,v]:=0;
        end
        else Success:=True;
      end
   until Success or (k=8);
 end;
var i,j: integer;
begin // TryM
  for i:=1 to n do
  for j:=1 to n do
    Solution[i,j]:=0;
  Solution[x,y]:=1;
  Success:=False;
  Try0(2,x,y);
end; // TryM
var x0,y0: integer;
    Success: boolean;
begin // основная программа
  read(x0,y0);
  TryM(x0,y0,Success);
  if Success then
     WriteArr(Solution,n); // вывод массива ходов
  else writeln('решений нет');
end.

Далее я попытался реализовать эту программу на с++
код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <conio.h>
#include <fstream>
 
using namespace std;
 
 
bool Success=NULL;
int Solution [8][8];
 
void Try0(int i,int x,int y,int *dx,int *dy,int n)
{
 int k,             // номер кандидата
      u=0,v=0; // координаты следующего хода коня
 k=0;
 
  do
 {
      k++;
  u=x+dx[k]; 
  v=y+dy[k];
  if((u>0)&&(u<=n)&&(v>0)&&(v<=n)&&(Solution[u][v]=0)) 
  {
        Solution[u][v]=i;
        if (i<n*n)
  {
          Try0(i+1,u,v,dx,dy,n);
          if (!Success) Solution[u][v]=0;
  }
        else Success=true;
  }
 }
  while (Success||k<8);
}
 
void TryM(int x,int y,int *dx,int *dy,int n)
{
int i,j;
for (i=0;i<n;i++)for(j=0;j<n;j++)Solution[i][j]=0;
  Solution[x][y]=1;
  Success=1;
  Try0(2,x,y,dx,dy,n);
}
 
void main()
{
setlocale(LC_ALL,"");
int dx[] ={-1,1,2,2,1,-1,-2,-2},
dy[]={2,2,1,-1,-2,-2,-1,1};
int x,y;
const int n=8;
cout<<"введите x"<<endl;
cin>>x;
cout<<"введите y"<<endl;
cin>>y;
TryM( x,y,dx,dy,n);
if(Success)
 for (int i=0;i<n;i++)
 {
  cout<<endl;
  for(int j=0;j<n;j++)
  cout<<Solution[i][j]<<" ";
 }
else cout<<"Решений нет";
  cout<<endl;
 system ("pause");
}

Уважаемые форумчане, помогите пожалуйста найти ошибку или подсказать свой вариант программы ибо моя прога не работает. Т.е. она компилируется но получить осмысленный результат мне так и не удалось.

P.S. заранее спасибо.

@olleg90 · 26.03.2011, 19:37 **[ТС]**

Два способа решения!
способ номер (эвристика) один за основу взято Правило Варнсдорфа

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <iostream>
#define M 30
int numberOfSteps(int x, int y, int A[M][M]);
void printArray(int A[M][M]);
int offset[8][2];
 
int main()
{
    setlocale(LC_CTYPE,"");
    int A[M][M];
    int steps[8];
    int x=3, y=3, count=1, idx=0;
    std::cout<<"введите х"<<std::endl;
    std::cin>>x;
    std::cout<<"введите y"<<std::endl;
    std::cin>>y;
 
    offset[0][0]= 2; offset[0][1]= 1; 
    offset[1][0]= 2; offset[1][1]=-1; 
    offset[2][0]= 1; offset[2][1]= 2;
    offset[3][0]= 1; offset[3][1]=-2; 
    offset[4][0]=-1; offset[4][1]= 2; 
    offset[5][0]=-1; offset[5][1]=-2;
    offset[6][0]=-2; offset[6][1]= 1; 
    offset[7][0]=-2; offset[7][1]=-1;
    for(int i=0;i<M;i++) {
        for(int j=0;j<M;j++) {
            A[i][j]=0;    
        }
    }
    A[x][y]=count;
    
    do {
        for(int k=0; k<8; k++) {
            steps[k]=numberOfSteps(x+offset[k][0], y+offset[k][1], A);
        }
        for(int k=0; k<8; k++) {
            if(steps[k]>0) {
                idx = k;
                break;
            }
            if(k==7) {
                for(int i=0; i<8; i++) {
                    if(steps[i]==0) {
                        A[x+offset[i][0]][y+offset[i][1]]=++count;
                    }
                }
                printArray(A);
                return 0;    
            }
        }
        for(int k=0; k<8; k++) {
            if(steps[k]<steps[idx] && steps[k]>0) {
                idx = k;
            }
        }
        
        x += offset[idx][0]; 
        y += offset[idx][1]; 
        A[x][y]=++count;
        
    } while(true);
    return 0;
}
 
int numberOfSteps(int x, int y, int A[M][M])
{
    if((x<0 || x>=M || y<0 || y>=M || A[x][y]!=0)) {
        return -1;
    }
    int count=0;
    for(int k=0; k<8; k++) {
        int xn=x+offset[k][0];
        int yn=y+offset[k][1];
        if(xn>=0 && xn<M && yn>=0 && yn<M && A[xn][yn]==0) {
            count++;
        }
    }
    return count;
}
 
void printArray(int A[M][M])
{
    for(int i=0;i<M;i++) {
        for(int j=0;j<M;j++) {
            printf("%4d",A[i][j]);
        }
        printf("\n");
    }    
     system("pause");
}

способ номер два Через рекурсию с откатом

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <time.h>
 
using namespace std;
 
#define move_types 8
 
int possible_moves[move_types][2]  = {
        {-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
        {-1,  2}, { 2, -1}, { 1,  2}, { 2,  1} 
};
 
int **global;       
int size_x, size_y;          
int max_moves, back_ret;
 
 
/*Функция проверяет может ли быть сделан ход на клетку с координатами x,y*/
int move_possible(int x, int y) 
{
        return x >= 0 && y >= 0 && x < size_x && y < size_y && global[x][y] == 0;
}
 
 
int find_path(int cur_x, int cur_y, int move_num)
{
        int next_x = 0, next_y = 0;
        global[cur_x][cur_y] = move_num;
        
        if(move_num > max_moves)
                return 1;
 
        for(int i = 0; i < move_types; i++)
        {       next_x = cur_x + possible_moves[i][0];
                next_y = cur_y + possible_moves[i][1];
                if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1))
                return 1;
        }
 
        global[cur_x][cur_y] = 0;
        back_ret++;
        move_num++;
        return 0;
}
 
 
 
/*главная функция*/
void main() 
{
setlocale (LC_ALL,"");
 
int i,nrows,ncols,sy,sx,**desc = NULL;
time_t start,end;
//вводим данные
cout<<"Введите размерность доски (от 2 до 8) :"<<endl
 <<"по оси \"X\"\t"; cin>>size_x;
cout<<"по оси \"Y\"\t";cin>>size_y;
if(size_x>8||size_x<2||size_y>8||size_y<2)
{cout<<"Неверный размер";system("pause");return;}
//проверяем размерность
cout<<"Введите начальные координаты:"<<endl
 <<"Координата по оси\"X\"\t";cin>>sx;
cout<<"Координата по оси\"Y\"\t";cin>>sy;
//проверяем координаты
 
 
start=time(NULL);//стартуем
//инициализируем увзвтель и выделяем память
desc = (int **)malloc(sizeof(int) * size_x);
for(i = 0; i < size_x; ++i) 
        desc[i] = (int *)malloc(sizeof(int) * size_y);
 
//инициализируем другие переменные
back_ret = 0;
global = desc;
max_moves = size_x * size_y - 1;
 
//зануляем массив
for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
                global[i][j] = 0;
}
 
 
//поиск решения
if(find_path(sx, sy, 1)){
 cout<<"___________________________________________"<<endl
  <<"\t***Решение***"<<endl
  <<"___________________________________________"<<endl;
 for(int i = 0; i < size_x; ++i) {
  cout<<endl;
  for(int j = 0; j < size_y; ++j)
    cout<<global[i][j]<<"\t";
    cout<<endl;} 
 cout<<"___________________________________________"<<endl;
}
else cout<<"Нет решения"<<endl;
 
 
//освобождаем память
for(i = 0; i < size_x; ++i)
        free(desc[i]);
free(desc);
end=time(NULL);//время конца цикла
 
//время поиска решения
cout<<"время поиска решения "<<difftime(end, start) <<" сек."<<endl;
cout<<"___________________________________________"<<endl;
system("pause");
}

сам спросил сам ответил

Добавлено через 7 минут
На wiki нашел следующее :
"В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня."
ребята подскажите кто ни будь как можно через графы решить а то что то не пойму гамильтонов путь и цикл )

@IrineK · 26.03.2011, 19:37

сам спросил сам ответил

Такой самодиалог помогает вам выпрямлять руки? Или же они еще больше заворачиваются?

@olleg90 · 26.03.2011, 19:45 **[ТС]**

Сообщение от IrineK

Такой самодиалог помогает вам выпрямлять руки? Или же они еще больше заворачиваются?

понимаешь не варик вообще 8 часов в выходной день дочить пяву)

не подскажешь как через графы можно рубануть задачу... мне не нужен код...
нужна подсказка или алгоритм в общих чертах

@sofia_s · 14.01.2013, 19:16

olleg90, привет, ти б мог подробнее описать способ номер два через рекурсию з откатом?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@sofia_s 0 / 0 / 0 Регистрация: 22.12.2012 Сообщений: 7
	14.01.2013, 19:16
	olleg90, привет, ти б мог подробнее описать способ номер два через рекурсию з откатом? 0