Желающие могут выбрать вариант 32. :)

Цель: ознакомиться с классическими задачами на алгоритм поиска с возвратом.
В отчёте необходимо описать алгоритм решения задачи по варианту и продемонстрировать принципиально разные случаи данного для алгоритма. В программе вести подсчёт шагов поиска.

Варианты заданий

1. Движение в лабиринте по четырем направлениям.
   Лабиринт представлен матрицей, состоящей из М строк и N столбцов. Движение в лабиринте разрешено поклеточно по четырем направлениям: на восток, на юг, на запад и на север, пользователь может задавать точку входа в лабиринт и точку выхода из него индексами соответствующих элементов в матрице.
   Написать программу, определяющую, существует ли путь в лабиринте от входа к выходу. Если путь существует, его необходимо вывести.

Входные данные - матрица, определяющая лабиринт по следующим правилам: Если значение элемента матрицы равно 0, то такая клетка доступна для перемещения, значение 1 определяет точку входа, значение 2 - точку выхода. -1 переход запрещен.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0, а запрещённые клетки -1.

2. «Конь и лабиринт». Лабиринт содержит n×n клеток. Клетка может быть «проходима» или «непроходима». По лабиринту перемещается конь, шаг коня определяется шахматными правилами. Задаются координаты точки входа в лабиринт и точки выхода из него. Написать программу, определяющую, существует ли путь конем в лабиринте от входа к выходу, и выводящую путь коня с минимальным количеством перемещений, если выход найден.

Входные данные - матрица, определяющая лабиринт по следующим правилам: Если значение элемента матрицы равно 0, то такая клетка доступна для перемещения, значение 1 определяет точку входа, значение 2 - точку выхода. -1 переход запрещен.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0, а запрещённые клетки -1.

3. Расстановка слонов. Написать программу нахождения такой расстановки n слонов на шахматной доске размером n×n, при которой каждое поле будет находиться под ударом одного из слонов. Первые три фигуры расставляет пользователь.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие 1 или отсутствие 0 установленной фигуры.

4. Расстановка ладей. Написать программу нахождения такой расстановки n ладей на шахматной доске размером n×n, чтобы ни одна из них не угрожала другой. Первые три фигуры расставляет пользователь.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

5. Расстановка ферзей. Написать программу нахождения расстановки n ферзей на шахматной доске размером n×n так, чтобы ни один из них не угрожал другому. Пользователю разрешается поставить одного ферзя на одно из полей.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

6. Расстановка пяти Ферзей.

Написать программу нахождения расстановки на шахматной доске 5 ферзей, при которой каждое поле будет находиться под ударом. На шахматную доску пользователю разрешается поместить одну фигуру.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

7. Расстановка двенадцати коней. Написать программу нахождения расстановки на шахматной доске 12 коней таким образом, что каждое поле шахматной доски находится под ударом одного из коней.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

8. Обход конем шахматной доски.

Имеется доска размером n×n. Конь помещается на клетку с начальными координатами x₀, y₀ и далее ходит согласно шахматным правилам. Требуется написать программу, в результате которой будет совершен обход шахматной доски так, что каждая клетка будет посещена только один раз.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0.

9. Обход конем шахматной доски.

Имеется доска размером n×n. Конь помещается на клетку с начальными координатами x₀, y₀ и далее ходит согласно шахматным правилам. Происходит обход шахматной доски конем так, что каждая клетка будет посещена только один раз.

Написать программу, которая определяет все поля, начиная с которых невозможен полный обход доски.

В результате работы программа должна вывести на экран доску в виде матрицы, в которой найденные поля обозначаются -1, а все остальные 0.

10. Задано описание кубика и входная строка. Требуется написать программу, которая определяет можно ли получить входную строку, прокатив кубик, и показывает последовательность выпавших граней.

11. «Судоку». Имеется игровое поле в виде квадрата размером 9×9, разделенного на меньшие квадраты со стороной в 3 клетки. В начале игры в некоторых клетках уже записаны числа от 1 до 9. Необходимо написать программу, заполняющую свободные клетки числами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.

Входные данные представляют собой матрицу с заполненными некоторыми числами. Неуказанные числа можно обозначить 0.

*Усложнение: программа должна находить решения для судоку размером n²×n².

12. Задано множество X = {x₁, x₂, …, x_n} целых положительных чисел и число S. Требуется узнать, может ли число S быть представлено как сумма некоторых из чисел множества X, если каждое число можно использовать не более чем по одному разу.

Пример: X = {1,2,3,4,5,8} и S = 18.

Ответ: 18 = 1 + 4 + 5 + 8. Или 18 = 2 + 3 + 5 + 8.

13. Задача о рюкзаке.

Дано множество вещей S = {x₁, x₂, x₃, …, x_n}. Каждая i-я вещь имеет свой вес w_i, и свою стоимость c_i. Необходимо написать программу, которая из множества S выбирает такой набор вещей, что их общий вес не превышал бы заданного числа K, а их общая стоимость была бы максимальной.

14. Движение в лабиринте по четырем направлениям.
    Лабиринт представлен матрицей, состоящей из М строк и N столбцов. Движение в лабиринте разрешено поклеточно по четырем направлениям: на восток, на юг, на запад и на север, пользователь может задавать точку входа в лабиринт и точку выхода из него индексами соответствующих элементов в матрице.
    Написать программу, определяющую, существует ли путь в лабиринте от входа к выходу. Если путь существует, его необходимо вывести.

Входные данные - матрица, определяющая лабиринт по следующим правилам: Если значение элемента матрицы равно 0, то такая клетка доступна для перемещения, значение 1 определяет точку входа, значение 2 - точку выхода. -1 переход запрещен.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0, а запрещённые клетки -1.

15. «Конь и лабиринт». Лабиринт содержит n×n клеток. Клетка может быть «проходима» или «непроходима». По лабиринту перемещается конь, шаг коня определяется шахматными правилами. Задаются координаты точки входа в лабиринт и точки выхода из него. Написать программу, определяющую, существует ли путь конем в лабиринте от входа к выходу, и выводящую путь коня с минимальным количеством перемещений, если выход найден.

Входные данные - матрица, определяющая лабиринт по следующим правилам: Если значение элемента матрицы равно 0, то такая клетка доступна для перемещения, значение 1 определяет точку входа, значение 2 - точку выхода. -1 переход запрещен.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0, а запрещённые клетки -1.

16. Расстановка слонов. Написать программу нахождения такой расстановки n слонов на шахматной доске размером n×n, при которой каждое поле будет находиться под ударом одного из слонов. Первые три фигуры расставляет пользователь.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие 1 или отсутствие 0 установленной фигуры.

17. Расстановка ладей. Написать программу нахождения такой расстановки n ладей на шахматной доске размером n×n, чтобы ни одна из них не угрожала другой. Первые три фигуры расставляет пользователь.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

18. Расстановка ферзей. Написать программу нахождения расстановки n ферзей на шахматной доске размером n×n так, чтобы ни один из них не угрожал другому. Пользователю разрешается поставить одного ферзя на одно из полей.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

19. Расстановка пяти Ферзей.

Написать программу нахождения расстановки на шахматной доске 5 ферзей, при которой каждое поле будет находиться под ударом. На шахматную доску пользователю разрешается поместить одну фигуру.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

20. Расстановка двенадцати коней. Написать программу нахождения расстановки на шахматной доске 12 коней таким образом, что каждое поле шахматной доски находится под ударом одного из коней.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

21. Обход конем шахматной доски.

Имеется доска размером n×n. Конь помещается на клетку с начальными координатами x₀, y₀ и далее ходит согласно шахматным правилам. Требуется написать программу, в результате которой будет совершен обход шахматной доски так, что каждая клетка будет посещена только один раз.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0.

22. Обход конем шахматной доски.

Имеется доска размером n×n. Конь помещается на клетку с начальными координатами x₀, y₀ и далее ходит согласно шахматным правилам. Происходит обход шахматной доски конем так, что каждая клетка будет посещена только один раз.

Написать программу, которая определяет все поля, начиная с которых невозможен полный обход доски.

В результате работы программа должна вывести на экран доску в виде матрицы, в которой найденные поля обозначаются -1, а все остальные 0.

23. Задано описание кубика и входная строка. Требуется написать программу, которая определяет можно ли получить входную строку, прокатив кубик, и показывает последовательность выпавших граней.

24. «Судоку». Имеется игровое поле в виде квадрата размером 9×9, разделенного на меньшие квадраты со стороной в 3 клетки. В начале игры в некоторых клетках уже записаны числа от 1 до 9. Необходимо написать программу, заполняющую свободные клетки числами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.

Входные данные представляют собой матрицу с заполненными некоторыми числами. Неуказанные числа можно обозначить 0.

*Усложнение: программа должна находить решения для судоку размером n²×n².

25. Задано множество X = {x₁, x₂, …, x_n} целых положительных чисел и число S. Требуется узнать, может ли число S быть представлено как сумма некоторых из чисел множества X, если каждое число можно использовать не более чем по одному разу.

Пример: X = {1,2,3,4,5,8} и S = 18.

Ответ: 18 = 1 + 4 + 5 + 8. Или 18 = 2 + 3 + 5 + 8.

26. Задача о рюкзаке.

Дано множество вещей S = {x₁, x₂, x₃, …, x_n}. Каждая i-я вещь имеет свой вес w_i, и свою стоимость c_i. Необходимо написать программу, которая из множества S выбирает такой набор вещей, что их общий вес не превышал бы заданного числа K, а их общая стоимость была бы максимальной.

27. Движение в лабиринте по четырем направлениям.
    Лабиринт представлен матрицей, состоящей из М строк и N столбцов. Движение в лабиринте разрешено поклеточно по четырем направлениям: на восток, на юг, на запад и на север, пользователь может задавать точку входа в лабиринт и точку выхода из него индексами соответствующих элементов в матрице.
    Написать программу, определяющую, существует ли путь в лабиринте от входа к выходу. Если путь существует, его необходимо вывести.

Входные данные - матрица, определяющая лабиринт по следующим правилам: Если значение элемента матрицы равно 0, то такая клетка доступна для перемещения, значение 1 определяет точку входа, значение 2 - точку выхода. -1 переход запрещен.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0, а запрещённые клетки -1.

28. «Конь и лабиринт». Лабиринт содержит n×n клеток. Клетка может быть «проходима» или «непроходима». По лабиринту перемещается конь, шаг коня определяется шахматными правилами. Задаются координаты точки входа в лабиринт и точки выхода из него. Написать программу, определяющую, существует ли путь конем в лабиринте от входа к выходу, и выводящую путь коня с минимальным количеством перемещений, если выход найден.

Входные данные - матрица, определяющая лабиринт по следующим правилам: Если значение элемента матрицы равно 0, то такая клетка доступна для перемещения, значение 1 определяет точку входа, значение 2 - точку выхода. -1 переход запрещен.

Вывод программы должен визуализировать найденный путь. Перемещения по клеткам пронумеровать натуральными числами, непосещенные клетки обозначаются 0, а запрещённые клетки -1.

29. Расстановка слонов. Написать программу нахождения такой расстановки n слонов на шахматной доске размером n×n, при которой каждое поле будет находиться под ударом одного из слонов. Первые три фигуры расставляет пользователь.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие 1 или отсутствие 0 установленной фигуры.

30. Расстановка ладей. Написать программу нахождения такой расстановки n ладей на шахматной доске размером n×n, чтобы ни одна из них не угрожала другой. Первые три фигуры расставляет пользователь.

В результате работы программа должна вывести на экран матрицу, в которой обозначается наличие (1) или отсутствие (0) установленной фигуры.

31. Расстановка ферзей. Написать программу нахождения расстановки n ферзей на шахматной доске размером n×n так, чтобы ни один из них не угрожал другому. Пользователю разрешается поставить одного ферзя на одно из полей.

32. Интересный. Задание у преподавателя.

(Количество уникальных вариантов - 13)