​

Теоретическое и практическое знакомство с гениальным "Алгоритмом икс" Дональда Кнута с примерами
​

Чему вы научитесь
Поймут суть алгоритма X для быстрого поиска решений
Решат задачу расстановки пентамимо с использованием алгоритма Dancing Links

Требования
Логическое мышление
Основы языка программирования C#

Описание
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, заполнение области Пентамимо-фигурами, решение Судоку, размещение ферзей на шахматной доске и так далее.
В первой части курса "Теория" мы разберём принцип работы алгоритма, выполним его построчно "ручками" на конкретном примере, чтобы лучше понять, как он устроен и как работает.
Во второй части курса "Практика" мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации "Алгоритма Икс" Дональда Кнута. и напишем весь алгоритм.
Во третьей части курса "Пентамимо" мы применим созданный алгоритм к конкретной олимпиадной задаче по размещению пентамимо-фигур в заданной области. Алгоритм Икс решает эту задачу максимально быстро, так как отметает множество тупиковых веток - он их просто пропускает и делает это красиво.
Если вам нравятся алгоритмы - обязательно пройдите этот курс, не пожалеете.

Какова целевая аудитория?
Для любителей алгоритмов
Для инженеров и программистов
Для студентов с лабораторкой по Dancing Links

Что входит в курс?
4 часа видео

Спойлер: Продолжение описания

Материалы курса
14 лекций - 04:07:25

Теория - 32:04

Что такое Dancing Links - 08:35
В этой серии уроков мы познакомимся с гениальным "алгоритмом X" Дональда Кнута — Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Ссылки на статью Дональда Кнута и обзорная статья на Хабре с описанием данного алгоритма — внизу описания урока.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Подходит ли данный алгоритм для решения задачи Судоку или Парад Ферзей.
3. Приложить интересную картинку на тему урока.

Работа алгоритма - 12:43
На этом уроке мы пошагово рассмотрим статью на Хабре (см. ссылки ниже).
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Напишите своё мнение по поводу данного урока.
3. Самостоятельно рассмотреть варианты поиска решения.
4. Приложить скриншот проработанного алгоритма.

Двусвязный список с удалением - 10:46
На этом уроке мы пошагово рассмотрим статью автора данного алгоритма — Дональда Кнута, и рассмотрим пошаговое удаление и возвращение элемента.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Нарисовать циклический список из 4 элементов ABCD.
3. Проработать весь алгоритм самостоятельно.
4. Приложить скриншот проработанного алгоритма.
5. * Продемонстрировать удаление/восстановление всех элементов.

Практика - 01:54:55

Расширение хоровода - 24:08
На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать новый проект AlgorithmX.
3. Создать новый класс Cell().
4. Добавить необходимые переменные и конструктор в классе Cell().
5. Избавиться от статика в классе Program().
6. Реализовать функцию test() в классе Program().
7. Реализовать функцию InsertLeft() в классе Cell().
8. Доработать конструктор в классе Cell().
9. Доработать функцию test() в классе Program(), использовав InsertLeft().
10. Приложить скриншот результата.

Заголовки столбцов - 12:17
На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, а также создадим класс Header(), для того чтобы знать, в каком столбце мы находимся.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить новые переменные в классе Cell().
3. Доработать в конструктор класса Cell() начальные значение новых переменных.
4. Реализовать функцию InsertUp() в классе Cell().
5. Создать класс Header() с необходимыми переменными.
6. Заменить переменную name на header в классе Cell().
7. Добавить конструктор в классе Header().
8. Доработать функцию test() в классе Program(), использовав InsertUp() и Header().
9. Приложить скриншот результата.

Единичная матрица - 25:01
На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать класс Dance() с необходимыми переменными.
3. Добавить конструктор в классе Dance().
4. Модифицировать тип переменной name в классе Header().
5. Реализовать функцию AddRow() в классе Dance().
6. Реализовать функцию start() в классе Program(), использовав класс Dance().
7. Приложить скриншот результата.
8. * Добавить все 12 строчек по образцу.

Как ссылки пошли впляс - 21:15
На этом уроке мы реализуем заготовку функции Dance() в классе Dance().
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить все 12 строчек в матрицу.
3. Реализовать функцию Dance() в классе Dance().
4. Создать заглушки для функций Cover/Uncover().
5. Добавить вывод текущего шага в функции Dance().
6. Приложить скриншот результата.

Открытие/закрытие столбцов - 32:14
На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(), а также реализуем функции Cover/Uncover().
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить номер строки в классе Cell().
3. Доработать функцию AddRow() в классе Dance().
4. Доработать функцию Dance() в классе Dance(), использовав стек для хранения целых чисел.
5. Реализовать функции Cover/Uncover() в классе Dance().
6. Перенумеровать ячейки от 0 до 11, чтобы избавиться от пустых столбцов.
7. Приложить скриншот результата.

Пентамимо - 01:40:26

Фигуры из пентамимо - 18:16
На этом уроке мы приступаем к решению олимпиадной задачи "Пентамино", заполнив массив всеми вариантами расположения фигур.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать структуру Figure() и Variant().
3. Создать класс Pentaminos().
4. Заполнить массив всеми 63 вариантами расположения фигур в классе Pentaminos().
5. Создать функцию startPent() в классе Program().
6. Проверить заполнение массива всеми вариантами фигур.
7. Приложить скриншот результата.
8. ** Доработать функцию startPent() для решения поставленной задачи.
9. *** Реализовать генератор всевозможных расположений фигур.

Фигуры в консоли - 14:59
На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть, что происходит в процессе работы алгоритма.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Реализовать функцию Show() в классе Figure().
3. Добавить в классе Figure() строку символов фигур.
4. Доработать функцию startPentamino() в классе Program() для отображения фигур.
5. Реализовать перегрузку функции Show() в классе Figure() для более короткой записи.
6. Использовать короткую запись в функции startPentamino() класса Program().
7. Приложить скриншот результата.
8. * Вывести все 12 фигур в консоли.

Матрица Пентагона - 15:55
На этом уроке мы завершим реализацию функции поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Реализовать алгоритм перебора всех вариантов расположения фигур Пентамино.
3. Дождаться завершения работы алгоритма и написать время ожидания.
4. Приложить скриншот результата.

Пентагон в деталях - 09:40
На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Исправить ошибку прошлого урока связанную с nr++.
3. Использовать отображение генерации расположения вариантов фигур через функцию Show().
4. Добавить задержку после вывода каждого варианта расположения фигур по нажатию клавиш.
5. Реализовать функцию Hide() в классе Figure().
6. Использовать функцию Hide() вместо Console.Clear().
7. Приложить скриншот результата.

Пентагон ищет решение - 22:01
На этом уроке мы визуализируем поиск решения Пентамино с использованием yield.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Модифицировать функцию Dance() в классе Dance(), чтобы она возвращала IEnumerable.
3. Воспользоваться возвращаемым IEnumerable для визуализации текущего состояния поиска решений.
4. Модифицировать работу рекурсии с использованием yield return.
5. Создать структуру FigureRow для хранения расположения фигуры на поле.
6. Использовать динамический список для хранения объектов FigureRow.
7. Добавить конструктор для удобства добавления информации в список.
8. Сделать структуру FigureRow глобальной.
9. Реализовать функции Show/Hide() с параметром FigureRow.
10. Добавить задержку между отображением/стиранием текущего состояния поиска решения.
11. Приложить скриншот результата.
12. * Дождаться окончания поиска решений.

Десятикратная оптимизация - 19:35
В завершение знакомства с гениальным "алгоритмом X" Дональда Кнута — Dancing Links,
мы оптимизируем наш алгоритм поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Оптимизировать функцию Dance() в классе Dance().
3. Реализовать счётчик количество найденных вариантов.
4. Реализовать счётчик времени потраченного на поиск решений.
5. Поэкспериментировать с разными размерами поля.
6. Убрать геттеры/сеттеры в классе Cell() для многократного ускорения работы алгоритма.
7. Приложить скриншот результата.
8. *** Реализовать решение Судоку, используя данный алгоритм.
9. *** Реализовать решение Парад Ферзей, используя данный алгоритм.

О преподавателе
Евгений Волосатов
Магистр математики и информатики, C#, Java, PHP программист
Я — Игромистр.
Моё призвание — показать пошаговый процесс создания игровых и прикладных программ, с нуля до результата.
Меня зовут Волосатов Евгений Витольдович, мне 40 лет, живу в Литве,
закончил Вильнюсский государственный университет магистром математики и информатики, также имею педагогическое образование.
За плечами сотни различных проектов на C#, Java, PHP, ASP.NET, SQL и т.д.
Всю свою сознательную жизнь я пишу программы и обучаю этому других.