?

Log in

No account? Create an account
entries friends calendar profile My Website Previous Previous Next Next
Эн-квадрашки - Уголок Школьника
scolar
scolar
Эн-квадрашки
Дошло до меня, о великий шах, что в одной компании в целях предварительного отделения козлов от козлищ дают на дом задачку: написать алгоритм решения игры в 15 (в просторечьи " пятнашки", хотя пятнашки - это совсем другая игра). Дело нехитрое, хотя и требующее известной аккуратности, типа проверки четности перестановки - а то в конце и зациклиться можно. Но вот что меня заинтересовало: кроме "механического" человеческого решения, наверняка должно быть "алгебраическое" - связанное с разложением перестановки в произведение транспозиций определенного вида (натурально, пустышка меняется местами с одним из соседей). Мало того, среди всех таких разложений существует минимальное, и запросто может оказаться, что снятое "кино" (особенно, при больших n) окажется довольно забавным: на свои места будут становиться не последовательно 1, 2, 3 ..., а будут возникать слегка флуктуирующие островки правильно поставленных фишек, которые будут разрастаться и сливаться по мере прохождения пустышки по некоторому маршруту. Одна беда, не могу придумать, как эффективно (без бэктрэкинга) разложить перестановку в произведение таких транспозиций.
3 comments or Leave a comment
Comments
vvagr From: vvagr Date: September 10th, 2006 08:42 am (UTC) (Link)
Слышал я, что именно так выглядели чемпионаты по сборке кубика Рубика. Чемпионы не складывали кубик послойно, а совершали операции, приближающие его к правильному состоянию в метрике некоторого пространства состояний кубика. Подробности и источника не помню, но наверняка при наличии времени можно их нагуглить.

Gоупражняться с перемещениями в метрике пространстве состояний пятнашек было бы любопытно даже в экспериментальном режиме, не зная, приближают ли упражнения к решению. Жаль, что я не агнец.
scolar From: scolar Date: September 10th, 2006 08:56 am (UTC) (Link)
Ага, а в качестве призовой игры - пятнашки на торе. Впрочем, они могут оказаться сильно проще.
From: dmpogo Date: September 10th, 2006 03:38 pm (UTC) (Link)
I to, ne dumaju chto poslojno chisto fizicheski mozhno slozhit' kubik za 12 secund.

3 comments or Leave a comment