[5. Указующий перст] [Оглавление] [7. Как компьютер сам рассказал...]

 

Ход коня

   С самых младших классов в нашей школе была распространена игра, в которой нужно было заполнить поле размером 10х10 на листах в клетку. Причем, заполнение нужно было делать только "ходом шахматного коня". Один ход состоял из двух полушагов - продвижение на одну или две клетки в одном из четырех направлений от текущего положения, а затем на две или одну клетку под углом в 90 градусов от первоначального движения.

   Хоть и был я в школе отличником, однако, никак не мог научиться заполнять это проклятое поле. И другие поля, 3х4, 5х5, 6х6... я тоже не мог заполнять так быстро и хорошо, как делали это мои товарищи. При этом, они не блистали умением получать пятерки и перебивались с двойки на тройку, в лучшем случае на четверку. Хорошо помню, что лучше всех, играючи, заполнял все эти поля Алеша Родионов. Я завидовал ему белой завистью, пытался научиться делать это сам, однако бесчисленные листочки в клеточку оставались заполненными только на 70-80 процентов.

   Наконец, когда я учился в 9 классе, а на дворе стоял 1987 год, в школе был открыт компьютерный класс. Там стояли БК-0010 - компьютеры с интерпретатором ФОКАЛА. Одной из первых программ, написанных мной, было заполнение "ходом коня" поля произвольной конфигурации. Больше всего я гордился не тем, что моя программа правильно и довольно быстро работала, а тем, что она могла заполнять поля любой конфигурации.

   Как я потом узнал на младших курсах института, задача заполнения поля сводится к aльфа- или бета-обходу дерева возможных ходов. Такая задача и вариант ее решения есть, например, у Н. Вирта в его классической книге по языку программирования Паскаль (ничего, что я так подробно Паскаль описываю? :-)). И решение ее приводится путем динамического формирования дерева ходов с помощью связанных списков. Проверка того, что очередной планируемый ход коня не выйдет за поле размером 8х8, если мне не изменяет память, проводилась сравнением координат с координатами поля. Я же, еще не зная этого, придумал заполнять поле нулями. Границы поля были обозначены двойной окантовкой из единиц для того, чтобы следующий ход не мог вывести за границы поля. Все это происходило в двухмерном массиве памяти компьютера. Конечно, моя программа не использовала динамические структуры данных, зато работала наверняка и безошибочно выполняла задание.

   Так, впервые, я приобрел превосходство над другими людьми с помощью компьютера.

   Впоследствии, мои друзья очень сильно удивлялись, как мне удалось написать такую сложную программу... Мне же было искренне не понятно, как они не могут написать такую простую последовательность кодов. Программа была всего 1,5-2 экрана длиной - около 40-50 строк. Помню, как я менял направление обхода, логику перебора вариантов, логику выбора направления следующего шага. В конце концов, я довольно хорошо "обучил" мою программу заполнять поля. Мне удалось добиться значительной экономии памяти и ускорения работы программы, когда я начал обозначать границы полей -1, а в поле, по мере заполнения его клеток, записывал число от 1 до 8, означающее рассматриваемое ветвление на этом шаге. При неудачной попытке я шел назад, пока мне не попадалось число, меньшее 8, увеличивал его на 1 и дальше испытывал новый вариант заполнения поля.

 

 

[5. Указующий перст] [Оглавление] [7. Как компьютер сам...]

 

[Пишите мне]

[Главная страница сайта]

 

TopList