Здравствуйте. Может быть кто-нибудь поможет в решении следующей задачи:
Имеется шахматная доска размером 5x5 и одна фишка в левом верхнем углу. Требуется определить количество всевозможных вариантов ее перемещения в правый нижний (противоположный) угол.
Как я понимаю, решение сводится к составлению и обходу дерева вариантов, но я пока не представляю, как его составить. Если сможете, подскажите пожалуйста алгоритм.
Обход шахматной доски
-
Serge_Bliznykov
- Сообщения: 375
- Зарегистрирован: 31 авг 2007, 03:06
1) поищите, был пример обхода шахматной доски конём
2)
Наверно, условие задачи подразумевает запрет повторного захода на клетки доски - т.е. варианты ее перемещения в правый нижний (противоположный) угол, причём в любой клетке фишка не может быть более одного раза...
2)
если это ПОЛНАЯ формулировка задачи, то могу Вас поздравить - она не решается - точнее - количество вариантов БЕСКОНЕЧНО! ведь ничего не сказано про повторы ходов (можно возращаться назад сколько угодно раз - а это всё варианты...;-(" писал(а):Имеется шахматная доска размером 5x5 и одна фишка в левом верхнем углу. Требуется определить количество всевозможных вариантов ее перемещения в правый нижний (противоположный) угол.
Наверно, условие задачи подразумевает запрет повторного захода на клетки доски - т.е. варианты ее перемещения в правый нижний (противоположный) угол, причём в любой клетке фишка не может быть более одного раза...
переформулирую задачу: требуется определить количество всевозможных вариантов перемещения фишки в правый нижний (противоположный) угол за 50 ходов по доске. Фишка может двигаться за 1 ход на 1 клетку в любом направлении (горизонтальном, вертикальном и диагональном).
даже при такой формулировке количество вариантов будет огромным
если не учитывать границы то получается примерно 3*8^49 тоесть 5,3521788476473495539685723854356e+44 - нереальное для обработки количесво вариантов
с учетом границ и конечной цели выпиантов будет меньше но не намного
такчто перебор тут не годиться
в это случае надо смотреть в сторону комбинаторики http://ru.wikipedia.org/wiki/Комбинаторика
если не учитывать границы то получается примерно 3*8^49 тоесть 5,3521788476473495539685723854356e+44 - нереальное для обработки количесво вариантов
с учетом границ и конечной цели выпиантов будет меньше но не намного
такчто перебор тут не годиться
в это случае надо смотреть в сторону комбинаторики http://ru.wikipedia.org/wiki/Комбинаторика
Как раз перебор и нужен. Требуется реализовать именно такой метод выполнения задачи, на выполнение которого уходило бы много времени. Для начала можно ограничиться хотя бы 10ю ходами. Подскажите плиз алгоритм перебора.
для перебора из 50 ходов на моем компьтере уйдет 154961556049029385 миллиардов лет 
десять ходов куда реальнее
алгоритм примерно такой:
делаеш десять вложенных друг вдруга циклов от 1 до 8
в самом внутреннем цикле заполняеш табличку текущего варианта набора ходов(два столбца, десять строчек ) по принципу
1 строка - состояние внешнего цикла, 2 строка состояние вложенного в него итд
состояния высчитываются по таблице состояний:
значение цикла первый столбец(х) второй столбец(у)
1 -1 -1
2 -1 0
3 -1 1
4 0 -1
5 0 1
6 1 -1
7 1 0
8 1 1
когда заполниш таблицу,начнется проверка доходит ли данный вариант
проверка:
в цикле слаживаеш значения элементов каждого столбца таблицы текущего варианта набора ходов
на каждом шаге цикла цикла сумма должна быть больше либо равна нулю и меньше либо равна 4
если цикл пройден успешно
и сумма по столбцам равна 4 то этот вариант удовлетворяет условиям задачи(можно увеличить счетчик найденых вариантов)
многа букофф конечно но в коде все выглядит не очень сложно
десять ходов куда реальнее
алгоритм примерно такой:
делаеш десять вложенных друг вдруга циклов от 1 до 8
в самом внутреннем цикле заполняеш табличку текущего варианта набора ходов(два столбца, десять строчек ) по принципу
1 строка - состояние внешнего цикла, 2 строка состояние вложенного в него итд
состояния высчитываются по таблице состояний:
значение цикла первый столбец(х) второй столбец(у)
1 -1 -1
2 -1 0
3 -1 1
4 0 -1
5 0 1
6 1 -1
7 1 0
8 1 1
когда заполниш таблицу,начнется проверка доходит ли данный вариант
проверка:
в цикле слаживаеш значения элементов каждого столбца таблицы текущего варианта набора ходов
на каждом шаге цикла цикла сумма должна быть больше либо равна нулю и меньше либо равна 4
если цикл пройден успешно
и сумма по столбцам равна 4 то этот вариант удовлетворяет условиям задачи(можно увеличить счетчик найденых вариантов)
многа букофф конечно но в коде все выглядит не очень сложно
-
Serge_Bliznykov
- Сообщения: 375
- Зарегистрирован: 31 авг 2007, 03:06
demon416, Вы не заметили, что доска 5 на 5 (ПЯТЬ на ПЯТЬ) клеточек...
все правильно доска 5 на 5 поэтому из одного угла в другой надо сделать 4 хода
спасибо, попробую реализовать, потом напишу что получилось
demon416 вы писали:
1 строка - состояние внешнего цикла, 2 строка состояние вложенного в него итд
состояния высчитываются по таблице состояний:
значение цикла первый столбец(х) второй столбец(у)
1 -1 -1
2 -1 0
3 -1 1
4 0 -1
5 0 1
6 1 -1
7 1 0
8 1 1
когда заполниш таблицу,начнется проверка доходит ли данный вариант
проверка:
в цикле слаживаеш значения элементов каждого столбца таблицы текущего варианта набора ходов
на каждом шаге цикла
поясние пожалуйста как составляется таблица состояний, и почему все таки 4 хода? Мне без разницы, за сколько ходов он дойдет до конца, лишь бы не больше чем за 10.
1 строка - состояние внешнего цикла, 2 строка состояние вложенного в него итд
состояния высчитываются по таблице состояний:
значение цикла первый столбец(х) второй столбец(у)
1 -1 -1
2 -1 0
3 -1 1
4 0 -1
5 0 1
6 1 -1
7 1 0
8 1 1
когда заполниш таблицу,начнется проверка доходит ли данный вариант
проверка:
в цикле слаживаеш значения элементов каждого столбца таблицы текущего варианта набора ходов
на каждом шаге цикла
поясние пожалуйста как составляется таблица состояний, и почему все таки 4 хода? Мне без разницы, за сколько ходов он дойдет до конца, лишь бы не больше чем за 10.