Zevs vs дешкомпьютер

[Суматра]

Сообщение от ПавелК

Правила игры в дешки:
1) строишь любую дешграмму - к ней будет привязана какая-то система счисления;
2) первый ход на любое поле дешграммы;
3) все последующие должны отличаться от предыдущего значением в одном произвольно выбранном разряде (из системы счисления, которая у дешграммы) или, что то же самое, отличаться в значении только по одной какой-то оси;
4) если ты не можешь сделать такой ход и не все поля дешграммы заняты ходами, то ты проиграл, если заняты все поля, то ничья.

Спорим, опять никто ничего не понял . Короче, берем обыкновенный мангустин... ээээ ..... 16-клеточный Бинардик.

!) Играют двое, один нечетными, другой четными (собственно, можно хоть крестиками и ноликами, но числами удобнее для протоколирования и чтоб не сбиться).
2) Первый игрок делает первый ход в любое открытое окно. Единичку туда ставит.
3) Второй передвигает ОДНУ ЛЮБУЮ клавишу и ставит в открывшееся окно двойку.
4) Первый опять передвигает одну любую клавишу, но так, чтоб попасть в НЕЗАНЯТУЮ клетку, и ставит туда "3".
5) И так они ходят по очереди в НЕЗАНЯТЫЕ клетки, которые отстоят НА 1 ПЕРЕКЛЮЧЕНИЕ КЛАВИШ от клетки с предыдущим ходом партнера. Пока кого-нибудь противник не загонит в тупик (клетку, с которой нет выхода - все клетки на расстоянии одного переключения заняты). Кто в тупике - тот проиграл.

Все, собственно. Дальше маленькое лирико-математическое отступление, которое можно не читать.

С точки зрения теории графов игра эквивалентна такой. Берем 3-мерную проекцию тессеракта. Такую вот хреновину:

Ее можно сделать из конструктора "Молекула", макарон и проч. Или взять плоское изображение.
Помечаем (например, кусочками пластилина) по очереди узлы модели, отстоящие от хода противника на 1 ребро и ранее непомеченные. Кто попал в тупик - проиграл.

Если честно, подозреваю, что есть хитрый алгоритм, при котором противник все равно проиграет. Как в "20 спичек и монета". Но я не спец по играм.

(отступление как бы закончилось)

Эти правила можно распространить на любую произвольную дешграмму, что и сделал выше Павел.