Visual brute force на примере решения 3D-пазлы

Visual brute force на примере решения 3D-пазлы

443
ПОДЕЛИТЬСЯ

Издавна друзья подарили мне эту загадку:

Потому было решено написать програмку. Собрать ее без помощи других, я никогда не могла (постоянно оставался один фрагмент).
Для тех , кто не любит читать, решение доступно по ссылке (обратите внимание, что сильно загружать процессор).
Итак, у нас есть пазл, который состоит из 25 схожих частей, которые должны быть депонированы в куб 5х5х5, где единицы измерения, принятые нижний край элемента.
Жертвуя производительностью ради визуализации (чрезвычайно хотелось сделать визуализированы грубой силы, как в кино), благо процесс экспертизы не обещал быть очень длинноватым (то, что будет написано ниже). Язык выбор пал на JavaScript.

Поделить элементы головоломки на кубики с 1-го участника
Основной процесс сборки будет происходить в трехмерном integer array (5х5х5), назовем его «коробки», где неотрицательное значение будет указывать на клеточку, занятую Куба элемент. Для простоты подсчета количества позиций я представил кубик Рубика, чьи лица раскрашены в различные цвета. Для большей информативности это значение равно порядковому номеру элемента в трехмерном пространстве. Каждый раз, когда он обращается к нам с новеньким лицом и поворачивается в четыре раза по часовой стрелке на 90° так, чтоб это лицо постоянно смотрели на нас. Всего 6 граней x 4 вращения = 24 положение в пространстве, где наши глаза являются фиксированными. Есть в общей трудности 24 положения элемента в трехмерном пространстве, раз угол поворота вокруг каждой оси кратный 90°.
К огорчению, формула для расчета количества ходов, чтоб отыскать решения, чтоб привести я не могу, потому раз кто-то может, пожалуйста, пишите в комментах, добавлю в статью. Зная количество позиций объекта в трехмерном пространстве и добавляя свое отражение в каждом государстве (два остальных отражают коллективно и персонально дам или же Куба либо 1-ое отражение опосля кручения), получаем, что для каждого неповторимое решение головоломки, которая может быть наиболее 1-го, учет 47 больше вариантов, и, следовательно, время, нужное для решения, будет меньше времени brute force.
Таковым образом, мы упростили для себя (и не лишь) для дальнейших расчетов. Основное условие для расположения базисной точки является ее обязательное присутствие элемента таковым образом, что при заполнении этого элемента Куба, базисная точка была размещена на базисном уровне Куба. Положение элемента в пространстве будет представлять относительные координаты 5 единичные кубики, которые составляют элемент координаты будут приняты относительно базисной точки (координаты [0,0,0], соответственно). Ниже базисного уровня будет осознать уровень по оси Z, которая на данный момент происходит сборка (ниже полная).

24 положение//x,y,z
var elems=[
[[0,0,0],[1,0,0],[1,1,0],[2,1,0],[3,1,0]],//0
[[0,0,0],[1,0,0],[2,0,0],[0,0,1],[-1,0,1]],//1
[[0,0,0],[1,0,0],[1,-1,0],[2,-1,0],[3,-1,0]],//2
[[0,0,0],[1,0,0],[1,0,1],[2,0,1],[3,0,1]],//3
[[0,0,0],[1,0,0],[2,0,0],[2,-1,0],[3,-1,0]],//4
[[0,0,0],[1,0,0],[2,0,0],[2,0,1],[3,0,1]],//5
[[0,0,0],[1,0,0],[2,0,0],[2,1,0],[3,1,0]],//6
[[0,0,0],[1,0,0],[0,0,1],[-1,0,1],[-2,0,1]],//7
[[0,0,0],[0,1,0],[1,1,0],[1,2,0],[1,3,0]],//8
[[0,0,0],[0,1,0],[0,1,1],[0,2,1],[0,3,1]],//9
[[0,0,0],[0,1,0],[-1,1,0],[-1,2,0],[-1,3,0]],//10
[[0,0,0],[0,1,0],[0,2,0],[0,0,1],[0,-1,1]],//11
[[0,0,0],[0,1,0],[0,2,0],[-1,2,0],[-1,3,0]],//12
[[0,0,0],[0,1,0],[0,0,1],[0,-1,1],[0,-2,1]],//13
[[0,0,0],[0,1,0],[0,2,0],[1,2,0],[1,3,0]],//14
[[0,0,0],[0,1,0],[0,2,0],[0,2,1],[0,3,1]],//15
[[0,0,0],[0,0,1],[0,0,2],[0,1,2],[0,1,3]],//16
[[0,0,0],[0,0,1],[0,0,2],[-1,0,2],[-1,0,3]],//17
[[0,0,0],[0,0,1],[0,0,2],[0,-1,2],[0,-1,3]],//18
[[0,0,0],[0,0,1],[0,0,2],[1,0,2],[1,0,3]],//19
[[0,0,0],[0,0,1],[0,1,1],[0,1,2],[0,1,3]],//20
[[0,0,0],[0,0,1],[-1,0,1],[-1,0,2],[-1,0,3]],//21
[[0,0,0],[0,0,1],[0,-1,1],[0,-1,2],[0,-1,3]],//22
[[0,0,0],[0,0,1],[1,0,1],[1,0,2],[1,0,3]]//23
];

Порядок сборки определяется головоломки: сборник снизу ввысь, как лишь уровень заполнен, перебегаем к последующему. Раз, опосля частичного наполнения уровня неких вольных очков, нереально отыскать положение, предыдущий элемент найден некорректно, удаляется из массива текущего состояния и «поле», поиск длится. Порядок перебора определяется массив положение частей в пространстве.
Как для визуализации, трехмерного представления Куба будет следовать в виде 5 фрагментов вдоль оси Z, срез на каждом уровне.
Чтоб понизить нагрузку состояния массива будет отображаться один раз в секунду либо в критические моменты: старт, пауза, стоп опосля нахождения ответа. Доп работы будут применять «line save», которая дозволяет Для вас сделать паузу, чтоб внести конфигурации в код и продолжить поиск с места паузы, и не с начала. Фрагменты представляют 5х5 таблицы, заполненными ячейками с неотрицательными числами от «коробки». Также, экран, количество циклов (в конце цикла пользоваться моментом, чтоб показать текущее состояние массива), количество «пропусков» в течение крайнего цикла и общее количество «проходов». Клеточки дополнительно окрашивать в различные цвета, чтоб отделить элементы головоломки друг от друга.
Для доборной универсальности, возможность конфигурации значения Размер «коробки» по всем трем координатам. Из особенностей стоит отметить, что в предстартовой подготовке в начале делает массив вероятных позиций для каждой координаты «поле» pre-cut положения, которые не могут быть помещены в этот момент. Для роста скорости визуализации добавил массив ячеек таблицы ломтиками.
Полный код с комментами:
— GitHub
— JSFiddle
Запустить, подождать (это заняло у меня 114 циклов на Google Chrome, перейдите по 96969659 варианты), находить ответ и собирать в настоящей жизни.

Ответ

Строчку » сохранить для тех, кто желает сделать тест, отражение[[5,0,0,0],[5,0,4,0],[12,3,0,0],[12,4,1,0]] habrahabr.ru