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

последовательность ходов коня - C++

Восстановить пароль Регистрация
 
Ботью
 Аватар для Ботью
3 / 3 / 0
Регистрация: 12.09.2012
Сообщений: 90
19.12.2013, 23:12     последовательность ходов коня #1
доброго времени суток, есть задача:
"Разработать программу, решающую задачу о ходе коня. Дана доска размером n x n (n<=10). На поле с координатами x0, y0 помещается конь (правила перемещения этой фигуры как в шахматах). Задача заключается в поиске последовательности ходов (если она существует), при которой конь точно один раз побывает на всех полях доски (обойдет доску), т. е. нужно вычислить n2-1 ходов. Полученную в качестве результата последовательность ходов отобразить на экране."

я нашел некоторое подобие этой задачи, но ни в какую не могу подогнать под свое условие, может кто помочь?
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
//глобальные константы, определяющие размерность массива board
const int hor = 8, ver = 8;
//прототип функции для вывода массива, имитирующего шахматную доску, на экран   
void printBoard(int[][ver]);  
using namespace std;
 
int main()
{
   //выделяем память для массива, эмитирующего шахматную доску
   int board[hor][ver] = {0};                        
   //описываем этими двумя массивами варианты ходов конем на доске(их всего восемь от 0 до 7)
   int horizontal[hor] = { 2, 1,-1,-2,-2,-1, 1, 2};  
   int vertical[ver] =   {-1,-2,-2,-1, 1, 2, 2, 1};
   //массив доступности ходов конем  
   int accessibility[hor][ver] = {{2,3,4,4,4,4,3,2}, 
                                  {3,4,6,6,6,6,4,3},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {3,4,6,6,6,6,4,3},
                                  {2,3,4,4,4,4,3,2}};
   //переменные, запоминающие текущие координаты нахождения коня
   int currentRow, currentColumn;
   //переменная, определяющая вариант хода конем(от 0 до 7)                    
   int moveNumber;
   //счетчик ходов конем                                   
   int counter = 0;                                  
 
   //предложение ввода координаты нахождения коня по горизонтали
   cout << "Enter a horizontal coordinate(0 - 7): "; 
   //сохранение введенных данных в переменной
   cin >> currentRow;
   //ввод координаты по вертикали                                
   cout << "Enter a vertical coordinate(0 - 7): "; 
   //сохранение данных ввода  
   cin >> currentColumn;                             
   
   //переменные currentRow и currentColumn модифицируються для изменения доступностей, поэтому сохраняем их
   int mainRow = currentRow, mainColumn = currentColumn;
   //переменные для записи координат следующего хода конем 
   int Row, Column; 
   
   //начинаем поиск решения
   for(int i = 1; i <= 64; i++)                      
   {
      board[mainRow][mainColumn] = ++counter;
      
      //делаем равным максимально возможной доступности
      int minAccessibility = 8;
      //временные переменные для исследования субдоступностей  
      int minA = 8, minB = 8;  
      
      //уменьшение доступности на единицу клеток, расположенных в одном ходу от выбранной
      for(moveNumber = 0; moveNumber <= 7; moveNumber++) 
      {
         //запоминаем положение коня на доске перед модификацией для изменения доступностей
         currentRow = mainRow;      
         currentColumn = mainColumn;
         
         //исследуем доступность всех возможных ходов не выходящих за границы доски
         currentRow += horizontal[moveNumber];  
         currentColumn += vertical[moveNumber];
         
         //не выходит ли за границы доски
         if(currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7) 
         {
            //уменьшаем доступность всех клеток в одном ходу
            accessibility[currentRow][currentColumn]--;  
            
            //если доступность больше, то меняем на меньшую
            if(minAccessibility > accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               //нашли минимальную доступность и ее координаты
               minAccessibility = accessibility[currentRow][currentColumn];  
               
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0)  
               {
                  //подготовили координаты к ходу на эту клетку
                  Row = currentRow;  
                  Column = currentColumn;
               }
               //временных переменные для нахождения минимальной доступности у тех, что меньше
               int RowA = currentRow, ColumnA = currentColumn; 
               
               for(int moveA = 0; moveA <= 7; moveA++)
               {
                  RowA += horizontal[moveA];
                  ColumnA += vertical[moveA];
                  
                  if(RowA >= 0 && RowA <= 7 && ColumnA >= 0 && ColumnA <= 7)
                  {
                     if(minA >= accessibility[RowA][ColumnA] && board[RowA][ColumnA] == 0)
                        //наименьшая доступность следующего хода
                        minA = accessibility[RowA][ColumnA]; 
                  }
               }
            }
   
            //если доступности равны
            if(minAccessibility == accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               minAccessibility = accessibility[currentRow][currentColumn];
               
               //временных переменные для нахождения минимальной доступности у тех, что равны
               int RowB = currentRow, ColumnB = currentColumn; 
               
               for(int moveB = 0; moveB <= 7; moveB++)
               {
                  RowB += horizontal[moveB];
                  ColumnB += vertical[moveB];
                  
                  if(RowB >= 0 && RowB <= 7 && ColumnB >= 0 && ColumnB <= 7)
                  {
                     if(minB >= accessibility[RowB][ColumnB] && board[RowB][ColumnB] == 0)
                        //наименьшая доступность следующего хода
                        minB = accessibility[RowB][ColumnB]; 
                  }
               }
   
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0 && minB < minA)  
               {
                  //изменяем подготовленные для следующего хода координаты в случае, если доступность следующего хода меньше
                  Row = currentRow;       
                  Column = currentColumn;
               }
            }
         }
      }
   
      mainRow = Row;
      mainColumn = Column;
   }
   
   //вызов функции для печати массива, моделирующего шахматную доску
   printBoard(board);                                
   system ("pause void");
   return 0;
}
   
//вывод массива, печатающего шахматную доску, на экран
void printBoard(int array[][ver])   
{
   cout << endl;
   for(int j = 0; j < ver; j++)
   {
      for(int i = 0; i < hor; i++)
         cout << setw(4) << array[i][j];
         
      cout << endl << endl;
   }
}
Добавлено через 1 час 6 минут
мои попытки привели вот к такому вот коду, он запускается, но падает в неизвестном мне месте циклов
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
//прототип функции для вывода массива, имитирующего шахматную доску, на экран   
void printBoard(int **arr, int , int);  
using namespace std;
 
int main()
{
    int hor,ver;
    cout<<"Enter N\t\t";
    do {
    cin>>hor;
    }while(hor<1&&hor>10);
    ver=hor;
   //выделяем память для массива, эмитирующего шахматную доску
   int **board=new int*[hor];
   for(int i=0;i<hor;i++)
       board[i]=new int [ver];                      
   //описываем этими двумя массивами варианты ходов конем на доске(их всего восемь от 0 до 7)
   int horizontal[8]={ 2, 1,-1,-2,-2,-1, 1, 2};  
   int vertical[8]=   {-1,-2,-2,-1, 1, 2, 2, 1};
   //массив доступности ходов конем  
   
   int **accessibility=new int*[hor];
   for(int i=0;i<hor;i++)
       accessibility[i]=new int[ver];
   for(int i =0;i<hor;i++)
   {
       for(int j=0; j< ver; j++)
       {
           if(i==0||i==ver-1)
           {
               if(j==0||j==ver-1) accessibility[i][j]=2;
               else{
               if(j==1||j==ver-2) accessibility[i][j]=3;
               else accessibility[i][j]=4;}
           }
           if(i==1||i==ver-2)
           {
               if(j==0||j==ver-1) accessibility[i][j]=3;
               else{
               if(j==1||j==ver-2) accessibility[i][j]=4;
               else accessibility[i][j]=6;}
           }
           else if(i!=0&&i!=1&&i!=ver-1&&i!=ver-2)
           {
               if(j==0||j==ver-1) accessibility[i][j]=4;
               else{
               if(j==1||j==ver-2) accessibility[i][j]=6;
               else if(i!=2||i!=3||i!=4||i!=6)accessibility[i][j]=8;}
 
           }
       }
   }
       
       
       /* = 
                                 {{2,3,4,4,4,4,3,2}, 
                                  {3,4,6,6,6,6,4,3},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {3,4,6,6,6,6,4,3},
                                  {2,3,4,4,4,4,3,2}};*/
   //переменные, запоминающие текущие координаты нахождения коня
   printBoard(accessibility, hor,ver);
   int currentRow, currentColumn;
   //переменная, определяющая вариант хода конем(от 0 до 7)                    
   int moveNumber;
   //счетчик ходов конем                                   
   int counter = 0;                                  
 
   //предложение ввода координаты нахождения коня по горизонтали
   cout << "Enter a horizontal coordinate(0 - 7): "; 
   //сохранение введенных данных в переменной
   cin >> currentRow;
   //ввод координаты по вертикали                                
   cout << "Enter a vertical coordinate(0 - 7): "; 
   //сохранение данных ввода  
   cin >> currentColumn;                             
   
   //переменные currentRow и currentColumn модифицируються для изменения доступностей, поэтому сохраняем их
   int mainRow = currentRow, mainColumn = currentColumn;
   //переменные для записи координат следующего хода конем 
   int Row, Column; 
   
   //начинаем поиск решения
   for(int i = 1; i <= hor*hor; i++)                      
   {
      board[mainRow][mainColumn] = ++counter;
      
      //делаем равным максимально возможной доступности
      int minAccessibility = 8;
      //временные переменные для исследования субдоступностей  
      int minA = 8, minB = 8;  
      
      //уменьшение доступности на единицу клеток, расположенных в одном ходу от выбранной
      for(moveNumber = 0; moveNumber < 8; moveNumber++) 
      {
         //запоминаем положение коня на доске перед модификацией для изменения доступностей
         currentRow = mainRow;      
         currentColumn = mainColumn;
         
         //исследуем доступность всех возможных ходов не выходящих за границы доски
         currentRow += horizontal[moveNumber];  
         currentColumn += vertical[moveNumber];
         
         //не выходит ли за границы доски
         if(currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7) 
         {
            //уменьшаем доступность всех клеток в одном ходу
            accessibility[currentRow][currentColumn]--;  
            
            //если доступность больше, то меняем на меньшую
            if(minAccessibility > accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               //нашли минимальную доступность и ее координаты
               minAccessibility = accessibility[currentRow][currentColumn];  
               
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0)  
               {
                  //подготовили координаты к ходу на эту клетку
                  Row = currentRow;  
                  Column = currentColumn;
               }
               //временных переменные для нахождения минимальной доступности у тех, что меньше
               int RowA = currentRow, ColumnA = currentColumn; 
               
               for(int moveA = 0; moveA < 8; moveA++)
               {
                  RowA += horizontal[moveA];
                  ColumnA += vertical[moveA];
                  
                  if(RowA >= 0 && RowA < 8 && ColumnA >= 0 && ColumnA <8 )
                  {
                     if(minA >= accessibility[RowA][ColumnA] && board[RowA][ColumnA] == 0)
                        //наименьшая доступность следующего хода
                        minA = accessibility[RowA][ColumnA]; 
                  }
               }
            }
   
            //если доступности равны
            if(minAccessibility == accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               minAccessibility = accessibility[currentRow][currentColumn];
               
               //временных переменные для нахождения минимальной доступности у тех, что равны
               int RowB = currentRow, ColumnB = currentColumn; 
               
               for(int moveB = 0; moveB <8; moveB++)
               {
                  RowB += horizontal[moveB];
                  ColumnB += vertical[moveB];
                  
                  if(RowB >= 0 && RowB <hor && ColumnB >= 0 && ColumnB <hor)
                  {
                     if(minB >= accessibility[RowB][ColumnB] && board[RowB][ColumnB] == 0)
                        //наименьшая доступность следующего хода
                        minB = accessibility[RowB][ColumnB]; 
                  }
               }
   
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0 && minB < minA)  
               {
                  //изменяем подготовленные для следующего хода координаты в случае, если доступность следующего хода меньше
                  Row = currentRow;       
                  Column = currentColumn;
               }
            }
         }
      }
   
      mainRow = Row;
      mainColumn = Column;
   }
   
   //вызов функции для печати массива, моделирующего шахматную доску
   printBoard(board, ver, hor);                                
   system ("pause void");
   return 0;
}
   
//вывод массива, печатающего шахматную доску, на экран
void printBoard(int **array, int ver, int hor)   
{
   cout << endl;
   for(int j = 0; j < ver; j++)
   {
      for(int i = 0; i < hor; i++)
         cout << setw(4) << array[i][j];
         
      cout << endl << endl;
   }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2013, 23:12     последовательность ходов коня
Посмотрите здесь:

C++ за сколько ходов конь переместиться в указанные координаты
Путешесвтие коня. C++
Удалить символы из строки за минимальное количество ходов. C++
C++ Определить последовательность ходов, которая позволит обойти все поля и вернуться на исходную.
C++ Похождения коня
Как сделать систему ходов в карточной игре? C++
C++ Увеличить количество ходов
C++ Просчет ходов Слона по шахматной доске

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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