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

Головоломка о путешествии коня - C++

Восстановить пароль Регистрация
 
strange_man
 Аватар для strange_man
9 / 9 / 0
Регистрация: 17.05.2012
Сообщений: 117
11.11.2012, 14:02     Головоломка о путешествии коня #1
Задача - составить такую последовательность ходов, при которой конь может обойти всю шахматную доску, побывав на каждой клетке лишь один раз, при этом не важно, с какой клетки фигура начнет свое путешествие.
У меня задача вышла, но только для 63 начальных клеток.
В учебнике для этой задачи есть пункт d) - написать программу так, чтобы при встрече с двумя или более альтернативными клетками, у которых одинаковый уровень доступности (то бишь со скольки клеток можно сделать ход сюда), решала бы, какую выбрать, чтобы после следующего хода конь смог походить на клетку с меньшим уровнем доступности.
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
#include <iostream>
 
using namespace std;
 
void calculateAccessibility (int [][8], const int[], const int[]); //calculates accessibility of each square;
int determineMoveNumber (int, int, int[][8], const int [], const int [], int[][8]); //determines the most efficient move;
void decrementAccessibility (int, int, int[][8], const int[], const int[], int[][8]); // when knight is gone it decrements accessibility of all nearby squares where knight can go;
 
int main()
{
    int horizontal[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int vertical[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
    for (int startPointX = 0; startPointX <= 7; startPointX++)  // we can check if program working correctly when knight starts his travelling from each square;
        for (int startPointY = 0; startPointY <= 7; startPointY++)
        {
            int board[8][8] = { 0 }; // starting board is empty. no moves have done yet;
            int accessibility[8][8] = { 0 }; //accessibility of each square will be calculated later. now it equals 0;
 
            int currentRow = startPointY; // Y coordinate of starting square;
            int currentColumn = startPointX; // X coodinate of starting square;
            int numberOfTurns = 0; //counter;
            int moveNumber; // knight can do 8 different moves. they will have values from 0 to 7;
            int &m = moveNumber; 
 
            calculateAccessibility (accessibility, vertical, horizontal);
 
            for (int i = 1; i <= 64; i++)
            {   
                board[currentColumn][currentRow] = 1; //marks square where knight is gone;
                numberOfTurns++; //incrementing counter;
                decrementAccessibility (currentRow, currentColumn, accessibility, vertical, horizontal, board);
                m = determineMoveNumber(currentRow, currentColumn, accessibility, vertical, horizontal, board); 
                if (m == -1) //if there are no possible moves program will stop;
                    break;
                //knight does new turn:
                currentRow += vertical[m]; 
                currentColumn += horizontal[m];
            }
            
            cout << startPointX << "-" << startPointY << ": " << numberOfTurns << " turns" << endl;
        }
    system("pause");
    return 0;
}
 
void calculateAccessibility (int accessibility[][8], const int vertical[], const int horizontal[])
{
    for (int i = 0; i <= 7; i++)
        for (int j = 0; j <= 7; j++)
        {
            int currentRow = j;
            int currentColumn = i;
            int n = 0;
 
            do {
                currentRow += vertical[n];
                currentColumn += horizontal[n];
                if (currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7)
                    ++accessibility[currentColumn][currentRow];
                currentRow -= vertical[n];
                currentColumn -= horizontal[n];
                n++;
            } while (n < 8);
        }
}
 
int determineMoveNumber (int row, int column, int accessibility[][8], const int vertical[], const int horizontal[], int board[][8])
{
    int min = 8; //minimal accessibility of square where knight can go from here;
    int move = -1; //on start it equals -1. if it isn't change function will return -1 and program swill stop.
 
    for (int n = 0; n <=7; n++) //counting all ways of moving
    {
        //doing pseudoturn
        row += vertical[n]; 
        column += horizontal[n]; 
 
        if (board[column][row] == 0 && row >= 0 && row <= 7 && column >= 0 && column <= 7) //cheking if knight crossed out of boards or if it have already been on this square;
            //if accessibility of this square is lower than minimal value, program gives 'move' variable a value of this way of turn
            if (accessibility[column][row] < min) 
            {
                min = accessibility[column][row];
                move = n;
            }
            //if turn is possible move must have a value, even if it's have accessibility of 8;
            else if (min == 8)
                move = n;
 
        //restore starting position
        row -= vertical[n];
        column -= horizontal[n]; 
    }
 
    return move;
}
 
//when move is done we have to decrement accessibility some squares
void decrementAccessibility (int row, int column, int accessibility[][8], const int vertical[], const int horizontal[], int board[][8])
{
    for (int n = 0; n <= 7; n++)
    {
        row += vertical[n];
        column += horizontal[n];
 
        if (board[column][row] == 0 && row >= 0 && row <= 7 && column >= 0 && column <= 7)
            --accessibility[column][row];
 
        row -= vertical[n];
        column -= horizontal[n];
    }
}
Миниатюры
Головоломка о путешествии коня  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2012, 14:02     Головоломка о путешествии коня
Посмотрите здесь:

C++ интересная головоломка
C++ Очень интересная головоломка..
Головоломка о голландском флаге C++
Путешесвтие коня. C++
C++ Интересная головоломка
C++ головоломка для знающих...
C++ Похождения коня
C++ Головоломка

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
undertacker
 Аватар для undertacker
9 / 9 / 0
Регистрация: 28.04.2013
Сообщений: 55
26.05.2013, 19:37     Головоломка о путешествии коня #2
strange_man, если еще нужно,
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
#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;
   }
}
Добавлено через 6 часов 21 минуту
strange_man, и вопрос от меня. Ты по времени сколько ее делал?
Yandex
Объявления
26.05.2013, 19:37     Головоломка о путешествии коня
Ответ Создать тему
Опции темы

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