Автор Тема: Алгоритм анализа возможности сборки кубика из произвольной ситуации.  (Прочитано 956 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
Допустим возьмём кубик 3х3х3. Собирём его наугад из кучи деталей.
Каким образом проверить возможно ли его привести в собранное состояние?
Т.е. на входе рандомный кубик на выходе ответ возможно собрать или не возможно.
Если, например, посчитать количество поворотов каждого элемента отдельного до нужного положения без учёта всех других(типа «манхэттенское расстояние»)? Чёт/нечет этих поворотов? Этого достаточно или всё намного сложнее?

Онлайн Zatamon

  • Постоялец
  • ***
  • Сообщений: 156
  • Пол: Мужской
Допустим возьмём кубик 3х3х3. Собирём его наугад из кучи деталей.
Каким образом проверить возможно ли его привести в собранное состояние?
Т.е. на входе рандомный кубик на выходе ответ возможно собрать или не возможно.
Если, например, посчитать количество поворотов каждого элемента отдельного до нужного положения без учёта всех других(типа «манхэттенское расстояние»)? Чёт/нечет этих поворотов? Этого достаточно или всё намного сложнее?
Ну дак вероятность сборки известна - 1/12 осталось все эти множители проверить, а они несложны
2: четность подстановки на реберных элементах должна быть равна четности подстановки на угловых
2: подстановка на реберных стикерах должна бьть четной
3: ориентация углов. Проверяется так: мысленно выделяем один цвет и, вместе с его противоположным перекрашиваем в один и тот же цвет. Считаем число поворотов уголов, чтобы все углы повернулись этим цветом. СМотрим делится или не делится на 3
2*2*3=12 Воти  все

Оффлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 089
  • Пол: Мужской
  • Спящий.
У меня вся диагностика минуты 2-3 занимала. Проще всего проверить углы. С ребрами чуть сложнее, но там помогает оценка куба перед "EO"-стадией (метод HTA). Труднее всего подсчитать перестановки. Может это и несложно на самом деле, но сам лично здесь хорошо так тупить начинаю.
F R U L D * 252

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
Zatamon, спасибо, как-то я не выходил на эту информацию, вот после вашего сообщения по 1/12 сразу нашлось несколько страниц с обсуждениями по этой теме.

Леннон, я для программки, ей точно не сложно будет. А для себя конечно тоже полезно попробовать потренироваться.

Оффлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 089
  • Пол: Мужской
  • Спящий.
А вот что примечательно, домино в любом случае соберется (то что 3*3*2). Догадываетесь почему? :)
F R U L D * 252

Онлайн Zatamon

  • Постоялец
  • ***
  • Сообщений: 156
  • Пол: Мужской
А вот что примечательно, домино в любом случае соберется (то что 3*3*2). Догадываетесь почему? :)
В смысле кубоид 3х3х2? Естьу  меня такой, но я его ой сколько не крутил... Есть еще у меня 3х3х4, так его можно рассматривать как 2 кубоида 3х3х2, а в 3х3х4 правда, кажется любая ситуация возможна, какую возможно воткнуть

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
Догадываетесь почему? :)
Даже и не знаю... Ну 2 угла меняются, 2 ребра тоже, но 1 угол в нём вроде всё равно не перевернуть? Могу предположить только, что из-за особенности конструкции угол развёрнутым не поставится?
Интересно откуда домино в названии? Я только сегодня заметил, что он так называется))
« Последнее редактирование: 24 Апреля 2017, 22:03:08 от Isaev »

Оффлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 089
  • Пол: Мужской
  • Спящий.
F R U L D * 252

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
Возвращаясь к 3х3...
Получается можно абсолютно наугад расставить 18 элементов и правильным положением последних 2 элементов (ребро и угол) его можно всегда сделать валидным, так же?
Нет, всё таки наверное последних 3 (2 угла и ребро), т.к. второй угол может быть поменян с первым
« Последнее редактирование: 26 Апреля 2017, 09:00:18 от Isaev »

Онлайн Zatamon

  • Постоялец
  • ***
  • Сообщений: 156
  • Пол: Мужской
Возвращаясь к 3х3...
Получается можно абсолютно наугад расставить 18 элементов и правильным положением последних 2 элементов (ребро и угол) его можно всегда сделать валидным, так же?
Нет, я же писал, надо еще проверить
2: четность подстановки на реберных элементах должна быть равна четности подстановки на угловых

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
Нет, я же писал, надо еще проверить
2: четность подстановки на реберных элементах должна быть равна четности подстановки на угловых

Нет, всё таки наверное последних 3 (2 угла и ребро), т.к. второй угол может быть поменян с первым

двумя углами мы эту чётность подгоним же... а 17 ставим произвольно
так?
« Последнее редактирование: 26 Апреля 2017, 19:04:36 от Isaev »

Онлайн Zatamon

  • Постоялец
  • ***
  • Сообщений: 156
  • Пол: Мужской
Ну, если оставить последние 3 - 2 угла и ребро, то один из углов важно только воткнуть на свое место, ориентация не важна, то есть важна только вместе с ориентацией второго угла, которой мы компенсируем любую ориентацию первого
то есть оставляем 2 уга и ребро, дальше нужно правильно сориентировать ребро перед втыканием, дальше вычислить место для углов, один воткнуть как попало, а ориентацию второго вычислить

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
Zatamon, спасибо ещё раз)

Оффлайн Isaev

  • Постоялец
  • ***
  • Сообщений: 239
  • Пол: Мужской
В соседней теме оказывается было подробное описание проблемы.   ::)

Оффлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 089
  • Пол: Мужской
  • Спящий.
Немного иная интерпретация того, что было известно ранее. Просто вместо единиц поворотов, сумма которых должна быть кратна 3 (в правильно собранной механически модели), сумма градусов кратная 360, если условно считать, что ребра или углы "поворачиваются" относительно неких осей.

Ориентировку ребер кстати можно определить не только по принципу EO-стадии, но и по типу того, как ребра располагаются в головоломке Master Skewd -' из-за особенностей вращения механизма скьюба, ребро попадая на свое место, там имеет всегда правильный разворот, при попадании на другое место позиция тоже всегда одна, а не две, как в кубе бывает. Картину можно усвоить для себя, а потом сравнивая с ней запутанный кубик выявить "неправильности", и их число (чет/нечет).
Картину того, какие положения занимают ребра в скьюбе, можно получить, "размешивая" куб таким алгоритмом как M U M' U2 M U M'. Если передвигать ребра только им, и 180-градусными вспомогательными поворотами, то расположения ребер будут аналогичны скьюбовским, без "флипов".

В произвольно собранном кубе с числом слоев 2n (двушка, четверка, шестерка...) просчитать возможность сборки кстати даже проще - соберется или нет, будет зависеть лишь от числа поворотов среди уголков. А остальное значение не имеет. Итого вероятность 1/3.

Скваер-1, как и домино соберется в любом случае.

А вот с пирамидкой все гораздо сложнее. Если ее разобрать механически, и потом собрать как попало, то вероятность решения скорее всего будет гораздо ниже чем в трешке. Там ведь основания углов могут встать так, что повороторами никак не решить, и уголки тоже, и ребра.
Предполагаю что...
1/ (2 * 4! * 4) = 1/192
F R U L D * 252