Обсуждение:Скьюб

Сложность

Ерунда в статье написана:

> скьюб производит впечатление сложной головоломки, но на самом деле таковой не является. Существуют 3 149 280 различных положений скьюба, что для головоломок такого типа является относительно небольшим числом и компьютер может найти оптимальный алгоритм решения.

На самом деле оценивать сложность головоломки по числу состояний - очень глупая идея. Так можно договориться до того, что пятнашки с расширенным полем до 5 на 5 сложнее кубика рубика, ибо в них 25!/2 состояний, что равно (select exp(sum(ln(level)))/2 from dual connect by level<=25) = 7,75560502166549E24 - больше чем у кубика рубика.

Я бы сказал наоборот, мне, как опытному в таких головоломках , скюьб показался весьма сложным. Например, в нем сложно придумать стандартным способом коммутаторы по понятным причинам: Слой в нем это понятно что, и вот, например, поставить только один угловой элемент в слой невозможно, потому что в нем 3 элемента принадлежат одной орбите, в которой всего лишь 4 элемента, поэтому единственным результатом могла бы быть транспозиция, но она невозможна по причине четности головоломки. Поэтому это у меня пока единственная головоломка, в которой почти не работают стандартные подходы.

Для компьютера да, меньшее число состояний означает проще построить граф кэли - весь уместится в памяти, поэтому поиск в ширину тут наверняка пройдет, но это другая тема80.89.129.116 00:47, 31 июля 2018 (UTC)