Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 63, средняя оценка - 4.70
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
24.03.2011, 18:04     Обход доски шахматным конем #1
решал задачу "Тур конем". :
На шахматной доске размером 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
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
26.03.2011, 19:37  [ТС]     Обход доски шахматным конем #2
Два способа решения!
способ номер (эвристика) один за основу взято Правило Варнсдорфа
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     Обход доски шахматным конем #3
сам спросил сам ответил
Такой самодиалог помогает вам выпрямлять руки? Или же они еще больше заворачиваются?
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
26.03.2011, 19:45  [ТС]     Обход доски шахматным конем #4
Цитата Сообщение от IrineK Посмотреть сообщение
Такой самодиалог помогает вам выпрямлять руки? Или же они еще больше заворачиваются?
понимаешь не варик вообще 8 часов в выходной день дочить пяву)

не подскажешь как через графы можно рубануть задачу... мне не нужен код...
нужна подсказка или алгоритм в общих чертах
sofia_s
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 7
14.01.2013, 19:16     Обход доски шахматным конем #5
olleg90, привет, ти б мог подробнее описать способ номер два через рекурсию з откатом?
Yandex
Объявления
14.01.2013, 19:16     Обход доски шахматным конем
Ответ Создать тему
Опции темы

Текущее время: 16:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru