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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
strange_man
9 / 9 / 0
Регистрация: 17.05.2012
Сообщений: 118
#1

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

11.11.2012, 14:02. Просмотров 760. Ответов 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++
//PC1.cpp== Считывает числа с текстового файла и записывает в массив. #include &lt;fstream&gt; #include &lt;iostream&gt; int SIZE = 50; using...

Головоломка - C++
Я ломаю мозг, не знаю что делать помогите. Пытался вспоминать программач, не помогло, кто ответ знает ? #include&lt;iostream&gt; #include...

Интересная головоломка - C++
1.С помощью текстового редактора создать файл который содержит текст.Длина ряда с текстом не должна превышать 80 символов.Это входной файл....

интересная головоломка - C++
помоготе решить задачу про спички я уже неделю голову ломаю....Даны n-спичек и 2 игрока,каждый может вытянуть от 1 до 3 спичек...выигрывает...

Головоломка Хитори - C++
Выберите на сайте Nikoli любую головоломку, кроме судоку: http://www.nikoli.co.jp/en/puzzles/. Напишите для неё функцию, которая получает...

Похождения коня - C++
Добрый день! Пишу программу для решения шахматной задачи &quot;Похождения коня,&quot; ( Условие : Требуется обойти конем все 64 клетки шахматной...

Ход коня - C++
Здравствуйте, уважаемые форумчане!!! у меня возникла проблема с задачей про коня!!! Дело в том что первоначальные значения координат...

Путешесвтие коня. - C++
Я написал программу про ход коня. Мне надо доделать, если ход сделать нельзя (выходит за размер доски) то писал введите другое число и...

головоломка для знающих... - C++
Описать функцию Ln1(x, ) вещественного типа (параметры x,  — вещественные, |x| &lt; 1,  &gt; 0), находящую приближенное значение функции ln(1...

Очень интересная головоломка.. - C++
Дан массив целых чисел (n=10); Переставить элементы след образом a,a,a,a,a,a..... Целый день думаю, ничего на ум не...

Головоломка о голландском флаге - C++
Даны три числа - a, b, c. Они равны 0,1,2, но не упорядочены. Не используя if поменять их местами так, чтобы а=1, b=0, с=2. Может...

Задача - Путешествие коня - C++
Выдает необработанное исключение #include &lt;iostream&gt; using std::cout; using std::endl; #include &lt;ctime&gt; using std::time; ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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, и вопрос от меня. Ты по времени сколько ее делал?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru