Как решать головоломные задачи на компьютере. Нетривиальные головоломки для программистов на языке C#

Многие головоломки – это совсем не тривиальные программистские задачи! Недаром ими занимались и занимаются серьёзные учёные. Достаточно назвать Леонарда Эйлера, Карла-Фридриха Гаусса, Эжена Шарля Каталана и классика программирования Дональда Кнута, чтобы доказать это утверждение.
Решению многих исторических головоломок посвящена моя книга Как решать комбинаторные задачи на компьютере. Там, в частности, рассматриваются:
- Считалка Иосифа Флавия – обсуждается в книге Дональда Кнута и соавторов Concrete Mathematics (Graham, Knuth, Patashnik), страницы 8-20.
- Головоломка Дьюдени о представлении сотни – подробно анализируется в книге Дональда Кнута Искусство программирования, том 4, выпуск 4.
- Генерирование случайных латинских квадратов по алгоритмам Джона Байерса. А теорию построения латинских квадратов разработал великий швейцарский учёный Леонард Эйлер.
- Расстановка ферзей на шахматной доске – эту задачу решал великий немецкий математик Карл-Фридрих Гаусс.
А в этой книге мы будем решать японскую головоломку судоку, для которой Дональд Кнут придумал алгоритм Dancing Links, описанный им в статье с тем же названием.
Насколько мне известно, единственная книга на русском языке (и то в переводе с французского), хоть сколько-нибудь систематически описывающая решение головоломок на компьютере, - это книга Жака Арсака Программирование игр и головоломок, выпущенная издательством Наука в 1990 году. Однако в ней рассматриваются классические, давно известные головоломки – Ханойские башни, расстановка ферзей на шахматной доске, криптарифмы, прыгающие лягушки, лабиринт, солитер и пентамино. Я же выбрал в качестве примеров современные и очень популярные во всём мире головоломки – словесные, числовые, логические и комбинаторные.
Думаю, что программистам на языке C# будет интересно и полезно решить с помощью компьютера такие головоломки:
· Магические квадраты (Magic squares)
· Euro-Tableau (Евро-табло)
· Voisinage (Соседство)
· Расставить числа – Rechenquadrat; Atomium (Kreisrechnen); Multiplikationsratsel; Числовое колесо (Zahlenrad); Summennetz; 5,6.
· Буквенное лото, Отгадать слово
· Словоскоп (Word Search Puzzle, Wortersuchen)
· Домино-пасьянс (Domino Puzzle), Квадрильи
· Крисс-кросс, Кроссворд, Чайнворд
· Сквэрворд (Squareword)
· Диаго, Диаго-плюс (Diago)
· Судоку (Sudoku)
· Gebiete (Области, Gebietssummen)
· Кен-кен (KENKEN, KenDoku)
· Какуро (Kakuro, Kreuzsummenratsel)
· Хитори (Hitori)
· Фобидоши (Fobidoshi)
· Лабиринт-алфавит (Zahlenschlange)
· Змейки
· Японский кроссворд (Edel, Нонограмма, Nonogram, Paint-by-numbers, Japanese puzzle, pic-a-pix, griddlers, Hanjie)
Система «домашних» заданий позволит укрепить навыки программирования при самостоятельном решении таких головоломок:
· Сколько номеров?
· Криптарифмы (числовые ребусы)
· Пирамида
· Rechenproblem
· Symbolratsel
· Кроссворд с выражениями
· Числа в «коробках»
· Муравейник
· 13 кружков
· Королевская балда
· Футошики (Futoshiki, Больше-меньше)
· Sudoku X
· Судоку-аргайл
· Судоку-астериск
· Судоку-жирандоль
· Судоку-Center Dot
· Судоку-убийца (Killer Sudoku, сум-до-ку)
· Аруконе (Arukone)
· Филиппинский кроссворд (Link-a-Pix, Paint by pairs)
Основной метод решения головоломных задач – как представленных в этой книге, так и многих других – перебор с возвратами (поиск в глубину, DFS, backtracking). Однако без серьёзного анализа конкретной головоломки обычно не удаётся решить её за разумное время. Поэтому решение всех задач предваряет разработка достаточно эффективного алгоритма, а затем подробно обсуждается его реализация на языке Си-шарп. Здесь вы узнаете:
· как представить информацию о задаче в файле на диске;
· какие типы данных выбрать для хранения данных в приложении;
· как показать условие задачи и процесс её решения на экране;
· как сохранить найденные решения на диске;
· как не только решать, но и составлять свои собственные задачи.
Все приложения написаны на языке Си-шарп, который идеально подходит для решения головоломных задач, но исходный код без труда может быть переведён на любой другой современный язык программирования.
Исходные коды прилагаются!
Название: Как решать головоломные задачи на компьютере: Нетривиальные головоломки для программистов на языке C#
Автор: Рубанцев Валерий
Издательство: RVGames
Жанр: Компьютерная
Год: 2013
Страниц: Много
Язык: Русский
Формат: PDF