Кубик Рубика прорыв

Наконец, компьютерам с небольшой помощью математики удалось выяснить, насколько на самом деле сложен кубик Рубика. Это прорыв, который некоторые называют «числом Бога».

Чтобы сразу перейти к делу — прорыв заключается в следующем:

Каждая позиция кубика Рубика может быть решена за двадцать или меньше ходов.

Или же

число бога 20

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

Рассказ о том, как был получен этот результат, тоже увлекателен. Наименьшее количество ходов, необходимое для сборки Куба, также известно как «число Бога», потому что это количество ходов, которое сделает всевидящая сущность. Верхняя граница этого числа в течение некоторого времени медленно приближалась к нижней, но теперь мы знаем, что любая позиция может быть решена за 20 ходов или меньше. Однако способ, которым было получено доказательство, может не понравиться многим чистым математикам, поскольку это был чисто метод грубой силы.

Команда разделила возможные положения куба на 55 882 296 смежных классов, используя симметрию и покрытие множеств. Затем они написали программу, которая решала один набор примерно за 20 секунд. Программа искала решения, которые требовали менее 20 ходов, вместо того, чтобы находить оптимальное решение в любом случае. Примерно через 35 лет использования процессора программа проверила все наборы, и все они могли быть решены за 20 или меньше ходов. Время вычислений было предоставлено Google как несколько недель простоя на своих серверах.

Не желая преуменьшать достижение — это впечатляющий вычислительный подвиг — единственная умная математика использовалась для разделения конфигураций с использованием симметрии. Остальная часть алгоритма — это чистый перебор. Это очень похоже на то, как многие математические теоремы доказываются с помощью компьютеров — теорема о четырех цветах была доказана с использованием аналогичной процедуры. Аргумент против этого подхода заключается в том, что, хотя результат доказан, не было достигнуто глубокого понимания того, почему он верен.

В этом случае было доказано, что не существует наборов расстояний, превышающих 20 от начальной конфигурации (где расстояние измеряется в ходах). Это кажется тем более примечательным, когда вам говорят, что существует 43 252 003 274 489 856 000 потенциальных позиций. Для решения большинства решений требуется от 15 до 19 ходов. Есть только около 300000000 позиций, требующих 20 ходов для достижения решения.

Такая сложность — такая простота.

Конечно, всегда есть куб 4х4, а потом …