Логические головоломки и программирование, по-моему, идут где-то рядом и имеют очень много общего. Лично я считаю, что человек, способный логически думать и размышлять иметь все шансы стать успешным программистом на любом языке программирования. Но здесь есть одно «но»: логическое мышление не всегда развито в человеке до того уровня, на котором он смог бы мыслить в силу многих факторов. Поэтому его всегда можно так сказать «доразвить», чем мы и будем заниматься в статьях, посвященных логическим головоломкам. Данная статья будет посвящена одной очень известной и интересной логической головоломке, придуманной и реализованной математиком Эйлером, называется она «путешествие коня». Вот в чем ее суть:
«Есть шахматная доска стандартного размера 8 х 8 клеток. Нужно с помощью фигуры «конь», которая как вы все знаете ходит буквой «Г», обойти все 64 клетки шахматной доски, побывав на каждой из них только единожды. Начинать свой путь «конем» можно с любой клетки шахматной доски.«
Вот такая вот логическая головоломка, которая, конечно же, имеет свое решение. Для начала предлагаю вам поэкспериментировать, дабы представлять себе все возможные проблемы при решении этой головоломки. Возьмите лист бумаги, ручку и нарисуйте матрицу 8х8 — это и будет наша доска, затем пробуйте ходить конем с любой точки доски, нумеруя использованные клетки по порядку. Заметьте сколько ходов вы смогли совершить, прежде чем зашли в тупик. Проанализируйте и выясните что вам мешает для совершения полного путешествия конем: возможно вы заметили, что те клетки, которые находятся по краям доски, и в особенности угловые, более трудны для обхода. Возможно нужно сначала начать именно с этих «трудных» клеток, а «более легкие» центральные оставить напоследок. Таким образом, вы сможете сделать уже заметно больше ходов «конем», прежде чем зайдете в тупик. Поэкспериментируйте уже исходя из этих соображений: возьмите новый лист бумаги, ручку и снова зарисуйте матрицу 8х8, начните делать ходы конем, отмечая пройденные клетки цифрами 1, 2, 3, 4 и так далее. Проанализируйте теперь то, что вы получили…
Как видите, теперь вы смогли сделать гораздо больше ходов, чем прежде — значит мы сделали правильные выводы на счет «тяжелых» и «более легких» клеток доски. Теперь давайте попробуем систематизировать наши полученные знания, дабы можно было всегда гарантированно обходить все 64 клетки, начиная свой путь с любой точки. Давайте еще раз нарисуем на листе бумаги шахматную доску и уже для каждой клетки зададим ее уровень доступности. Уровнем доступности у нас будет целое число и оно будет выражать количество возможных ходов на данную клетку с других клеток. Чтобы лучше это понять, смотрим рисунок
Теперь вы поняли как это делается, поэтому пометим все ячейки их уровнями доступности. Вот что в итоге должно получиться
Теперь давайте рассмотрим один важный момент. Мы имеем уровни доступностей каждой клетки шахматной доски и знаем, что «путешествие конем» нужно начинать в первую очередь с «тяжелых» клеток, т.е. с тех, у которых уровень доступности ниже. После того как мы сделаем первый ход конем, клетку нужно отметить как пройденную и пересмотреть уровни доступностей заново, т.к. с этой «пройденной» клетки уже нельзя будет больше походить. Вот такая картина получается
Давайте теперь распишем все наши производимые действия по порядку:
1. Первый ход делается на любую клетку шахматной доски (это оговорено в условии, что путешествие коня может начинаться с любого места)
2. Затем пересматриваются уровни доступностей, как показано на рисунке выше (т.к. первая клетка, на которую мы походили уже «отработала», то более с нее ходить нельзя, а значит доступности тех клеток, на которые можно было с нее ходить уменьшаются на единицу — думаю с этим понятно)
3. Следующих ход (второй) организуем так, чтобы пойти на клетку с наименьшей доступностью (так называемую «тяжелую»). На рисунке выше, этот ход отмечен синей стрелкой — это будет угловая клетка, у которой уровень доступности равен одному.
4. Затем опять пересматриваем доступности так же, как и в пункте 2 и продолжаем по пункту 3, пока не сделаем все 64 хода!
5. Читать обязательно!!! Еще один момент важный момент! Если доступности двух клеток, на которые мы можем походить равны, то нужно выбрать из них «более перспективную», то есть ту, в перспективе с которой можно будет сделать ход на клетку с более меньшей доступностью. Иными словами, нужно будет заглянуть на один ход вперед и посмотреть, где можно «убить» более «тяжелую» клетку)
А вот теперь самое интересное!!! Переходим к программированию: нужно написать программу, реализующую эту интересную логическую головоломку) Честно скажу, что написал я эту программу примерно где-то с год назад, и тогда решение пришло мне в голову не сразу. Поэтому не отчаивайтесь, если у вас не сразу получиться реализовать этот интересный алгоритм логической головоломки «путешествия конем». Сейчас вот приложу скрины того, что должна выдавать программа: как мы уже знаем, «путешествие коня» может начинаться с любой клетки, поэтому в начале программы у пользователя нужно запросить эти начальные координаты. В случае, когда путешествие коня начинается с той клетки, как у меня изображено на рисунке выше, результат прохождения будет иметь такой вид:
#include <iostream>
#include <iomanip>
//глобальные константы, определяющие размерность массива board
const int hor = 8, ver = 8;
using namespace std;
//вывод массива, печатающего шахматную доску, на экран
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;
}
}
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(1 - 8): ";
//сохранение введенных данных в переменной
cin >> currentRow;
//ввод координаты по вертикали
cout << "Enter a vertical coordinate(1 - 8): ";
//сохранение данных ввода
cin >> currentColumn;
//переменные currentRow и currentColumn модифицируються для изменения доступностей, поэтому сохраняем их
int mainRow = currentRow-1, mainColumn = currentColumn-1;
//переменные для записи координат следующего хода конем
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);
return 0;
}
Получайте новые статьи блога прямо себе на почту
Рекомендую также:
- Примеры работы с массивами на С++
- Примеры работы со структурами в С++
- Проверка числа открывающих и закрывающих фигурных скобок в программе
- Потоки и файлы. Готовая лабораторная работа (сведения о наличии билетов на рейсы аэрофлота)
- Потоки и файлы. Готовая лабораторная работа (сведения о сотрудниках института)