Авто сбор кубик рубика 3х3

Быстрая сборка кубика Рубика

Возможно, многие из читателей задавались вопросом, как людям удаётся собирать кубик Рубика 3×3 за 7 секунд. Если даже предположить, что рекордсмену сильно повезло, то таблица мирового рейтинга по среднему из пяти результатов уже не оставляет сомнений: если больше 80 человек в среднем укладываются в 12 секунд, очевидно они что-то знают. В этом кратком обзоре я постараюсь приоткрыть секреты скоростной сборки. Сразу оговорюсь, что после прочтения этой статьи вы не станете чемпионами: здесь приведены только основные моменты и ссылки на более подробную информацию. Кроме того, даже после изучения метода полностью вам потребуются долгие тренировки для достижения хороших результатов. Зато вы получите неплохое представление о том, как это делается, и при желании будете знать, куда двигаться дальше. Я думаю, при достаточной усидчивости после нескольких месяцев тренировок многие смогут достичь среднего результата в районе 30 секунд.

Я буду ссылаться в основном на SpeedSolving Wiki и на Badmephisto. Итак, поехали.

Метод CFOP

Наиболее популярным методом скоростной сборки кубика является метод CFOP, он же метод Джессики Фридрих, которая его доработала и популяризовала, хотя свой вклад внесли и другие люди. Если всё делать правильно, в среднем кубик удаётся собрать за 56 ходов (увы не за двадцать). Существуют и другие методы, с помощью которых можно получить неплохие результаты: Petrus, ZZ, Roux и т. д. Они менее популярны и ради краткости мы ограничимся рассмотрением метода CFOP.

Cross — крест

Цель стадии — правильно разместить четыре рёберных кубика на одной из граней. С этим справится любой, кто умеет собирать кубик хоть как-то, однако собрать крест за несколько секунд не так тривиально. По правилам соревнований перед сборкой вам даётся 15 секунд на изучение комбинации (inspecting), за которые как минимум надо найти эти четыре рёберных кубика, а хорошо бы и составить в голове полную последовательность ходов. Доказано, что для сборки креста на заранее выбранной грани всегда требуется не больше восьми поворотов (поворот на 180° считается за один), причём восемь крайне редко, да и семь нечасто (среднее чуть меньше шести). На практике, чтобы быстро научиться находить оптимальную последовательность, требуется немало тренироваться.

Выбирать грань для сборки креста можно по-разному. Наиболее популярный способ — всегда собирать его на одной и той же грани (часто — на белой). Тогда вы на всех стадиях сборки точно знаете относительное расположение цветов, что облегчает процесс. Некоторые люди собирают первой ту грань, которую легче всего собрать. В среднем это экономит один поворот, однако вам постоянно приходится перестраиваться на другое расположение цветов. Используется также компромиссный вариант — собирать одну из двух противоположных граней (скажем, либо белую, либо жёлтую), тогда набор цветов боковых граней не меняется.

Основная хитрость сборки креста в том, что его надо собирать относительно. К примеру, если вы собираете крест на белой грани и бело-синий рёберный кубик уже на ней стоит белым цветом к белому центру, то вам не так важно, совмещена ли синяя сторона этого кубика с синей гранью. Достаточно поставить бело-зелёный кубик на противоположной стороне, а бело-красный и бело-оранжевый слева и справа. В процессе сборки вы можете крутить белую грань как угодно, а в конце одним движением сразу совместите все боковые центры с кубиками креста. Важно лишь помнить точный порядок цветов на кубике: если смотреть на белую грань, то по часовой стрелке идут синий, красный, зелёный, оранжевый (сзади — жёлтый).

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

Некоторые продвинутые хитрости сборки креста описаны в этом видео.

F2L — первые два слоя

Пожалуй, наиболее длинная стадия, цель которой — собрать полностью два слоя: слой с крестом и промежуточный слой. По сути дела вам нужно расставить на места восемь кубиков: четыре угловых нижнего слоя и четыре рёберных боковых в среднем слое. В отличие от методов сборки для начинающих пара (столбик) из углового и рёберного кубика собирается сразу же (то есть надо собрать четыре таких пары). В зависимости от первоначальной расстановки кубиков пары вам нужно применить тот или иной алгоритм (последовательность поворотов). Всего таких алгоритмов больше 40, можно их просто вызубрить, однако почти все они выводятся интуитивно. Есть два простейших случая, когда пара собирается в три движения:

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

Основная сложность этапа в том, чтобы быстро находить парные кубики. Они могут находиться в 16 различных местах: 8 мест в последнем слое и 8 в столбиках. Столбики просматривать сложнее, а чем меньше столбиков у вас собрано, тем больше шансов, что в несобранных находятся нужные вам кубики. Если вы при сборке креста не обращали внимания на кубики для F2L, при переходе к этому этапу вы можете потерять много времени просто на поиск. Также не всегда разумно начинать с первой найденной пары: возможно, она собирается длинным алгоритмом, а если начать с другой, то в процессе первая перестроится в более удачную комбинацию.

OLL — ориентация последнего слоя

На этом этапе кубики последнего слоя ориентируются так, чтобы последняя (в нашем случае — жёлтая) грань оказалась собранной. При этом неважно, что кубики по сути не стоят на своих местах: этим мы займёмся на последнем этапе.

Существует 57 различных исходных ситуаций, для каждой из которых есть свой алгоритм сборки, от 6 и где-то до 14 ходов. Необходимо не только выучить все эти алгоритмы, но и быстро идентифицировать, какой из них необходимо применить на данный момент. Вот пример одного из OLL:

Слева на картинке изображена исходная ситуация с точностью до поворота (предполагается, что мы собираем жёлтую грань). Чтобы применить эту OLL, должны совпасть расположения жёлтых квадратиков не только на верхней грани, но и на боковых (квадратики остальных цветов игнорируем). Не всегда требуется сличать кубик со схемой полностью, надо лишь сличить достаточно квадратиков, чтобы отличить от остальных комбинаций. Справа приведено два алгоритма (кому-то удобнее делать один, кому-то другой) в стандартной нотации, внизу номер OLL и вероятность его выпадения. Почти все выпадают с вероятностью 1/54, некоторые с 1/108 и две с вероятностью 1/216 (включая счастливую комбинацию, когда OLL собралась сама).

Начинающим заучивать 57 комбинаций может показаться пыткой, поэтому придуман упрощённый, но более медленный вариант — 2-look OLL. В этом случае OLL разбивается на два этапа, сперва собирается крест, а затем углы. Тут надо заучить лишь 10 алгоритмов (3 для креста, 7 для углов). Набравшись опыта в 2-look OLL, можно неспеша взяться за изучение полного набора. При этом 2-look в любом случае пригодятся: во-первых, они все есть в полном наборе (скажем, если крест собрался сам, то полные OLL совпадают с 2-look OLL для углов), а во-вторых, если вам попался ещё незнакомый OLL, вы можете вернуться к 2-look.

Шпаргалки по OLL (включая 2-look) есть тут или тут, обучающее видео для 2-look OLL вот.

PLL — перестановка последнего слоя

Заключительный этап сборки состоит в том, чтобы расставить кубики последнего слоя на нужные места. Подход примерно аналогичный предыдущему этапу, но комбинаций и алгоритмов здесь меньше, всего 21 (13, если считать зеркальные и обратные за одну). С другой стороны их несколько сложнее опознавать, так как здесь надо учитывать разные цвета, причём цвета на схеме могут не совпадать с вашими цветами (с точностью до циклической перестановки):

Стрелками обозначены кубики, которые переставляет данный PLL. Вероятности большинства комбинаций — 1/18, изредка 1/36 и 1/72 (включая счастливый случай, когда ничего делать не надо).

Опять же предлагается упрощённый вариант — 2-look PLL, когда сперва расставляются углы (две комбинации), а потом центры (четыре комбинации), их довольно легко выучить.

Шпаргалки по PLL (включая 2-look) есть тут или тут, обучающее видео для 2-look PLL тут.

Кубик и смазка

Даже изучив в совершенстве приведённый метод, вы не достигнете хороших результатов с плохим кубиком. Грани кубика должны легко вращаться толчком одного пальца, при этом он не должен быть слишком разболтан. Слои должны висеть на пружинках так, чтобы не до конца повёрнутый один слой не мешал продолжать вращение в другом направлении (в разумных пределах, конечно). У правильного кубика центральные квадратики можно вытащить и подкрутить болты, что находятся под ними. В обычных магазинах сложно найти хороший кубик, рекомендуют заказывать по интернету, например, тут.

Для достижения наилучших результатов кубик необходимо смазывать. Иногда смазка идёт в комплекте с кубиком, либо покупается отдельно. Подходит силиконовая смазка, которую можно купить в автомагазинах.

Вращения кубика

Вращение всего кубика в руках (а не отдельных граней) отнимает существенное время, поэтому при сборке его стараются как можно сильнее избегать. Скажем, на этапе F2L порой проще собирать столбик в дальнем от себя углу, не видя его, чем поворачивать кубик этим столбиком к себе. На этапе OLL, чтобы повернуть кубик так, как в схеме алгоритма, достаточно покрутить верхний слой, а не крутить весь кубик целиком — это быстрее (положение верхнего слоя относительно нижних на этом этапе не важно).

Look ahead — заглядывание вперёд

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

Fingertricks

Также ключ к значительному ускорению сборки — это fingertricks, умелое использование всех пальцев для вращения. Некоторые частоиспользуемые комбинации выполняются молниеносно, 5 поворотов в секунду и выше, если правильно использовать пальцы. Обратите внимание: не всегда более короткий алгоритм делать быстрее; может оказаться. что придётся делать неудобные повороты. У BadMephisto несколько видеозаписей посвящено fingertricks, например, тут рассказывается про F2L.

Источник

Rubik’s Cube

Rubik’s Cube Simulator

Play with the online cube simulator on your computer or on your mobile phone.

Drag the pieces to make a face rotation or outside the cube to rotate the puzzle.

Apply a random scramble or go to full screen with the buttons.

Rubik’s Cube Solver

Calculate the solution for a scrambled cube puzzle in only 20 steps.

Set up the scramble pattern, press the Solve button and follow the instructions.

Use the color picker, apply an algorithm or use a random scramble.

How to solve the Rubik’s Cube

The beginner’s solution guide with images and easy to follow instructions.

Knowing how to solve the Rubik’s Cube is an amazing skill and it’s not so hard to learn if you are patient. You’ll realize that you don’t have to be a genius to get it done.

In this tutorial we are going to use the easiest layer-by-layer method.

White Edges

Let’s start with the white face. Try to form a plus sign on the top of the cube, matching the colors of the side stickers to the colors of the lateral centers. This step shouldn’t be too hard, try to do this without reading the examples below.

We can easily insert the edge to the top if you move it to the highlighted bottom-front spot first. Depending on where the white sticker is facing do the rotations.

When the white edge is stuck between two solved edges (last image) you can send it to the bottom layer doing this:

I used capital letters to mark the clockwise face rotations: F (front), R (right), L (left), U (up), D (down).

Turns in the opposite direction are marked with an apostrophe.

Finish The White Face

When the white edges are matching we can move on to solve the white coners.

First put the white corner that belongs to the spot marked with the upper arrow in either of the highlighted positions. Next repeat the algorithm below until the white piece comes to its desired destination.

This trick sends the piece back and forth between the top and bottom locations, twisting the corner in each step. Using this you can solve each white corner in less than 6 iterations.

At the end your cube should have a solid white face with the lateral stickers matching the lateral centers.

Center Layer

Turn your cube upside down because we don’t need to work with the white face anymore. We can insert an edge piece from the top-front position to the middle layer using a trick. Do the left or right algorithm depending on which side you have to insert the piece:

When a center layer piece is in a wrong position you can use the same trick to take it out.

You’ll have two solved layers when you finish this stage. We’re almost there.

Yellow Cross

Inspect the top of your cube. You see a yellow cross, a line, an L-shape or a dot. Our goal is to form a yellow cross.

Use this algorithm to shift from one state to the other.

Swap Edges

We have a yellow cross on the top but the edges are not in their final position. They need to match the side colors.

Use this to swap the front and left yellow edges in the top layer.

Cycle Corners

Only the yellow corners are left unsolved at this point. Now we are going to put them in their final position and we’ll rotate them in the last step.

Use the algorithm below to cycle the pieces in the direction marked with the arrows while the top-right-front piece is standing still.

Orient Corners

Everything is positioned, we just have to orient the yellow corners. We use the same algorithm that we used for solving the white corners in the second step:

This step can be confusing for most people so read the explanation very carefully and do exactly what it says!

1. Hold the cube in your hand having an unsolved yellow corner in the highlighted top-right-front position.
2. Repeat the algorithm until this piece is solved.
3. Turn the top layer to bring another unsolved piece in the highlighted position.
4. Repeat R’ D’ R D until that one is also solved.
5. Do 3 and 4 for any other unsolved yellow corner.

Important! During the process it might seem that you have messed up the whole cube but don’t worry because it will come together if you do it correctly, following the instructions.

Video Tutorial

Watch these steps being explaind in this video:

Источник

9 приложений со схемой сборки кубика Рубика

Если вы входите в сообщество поклонников кубика Рубика или хотите присоединиться к нему, приложения на телефоне будут вам полезны. Они помогут вам совершенствовать методы решения головоломки или сократить время, которое требуется для этого. В этой статье представлены лучшие интерактивные кубики Рубика, которые можно загрузить на iOS или Android. Итак, давайте приступим.

В статье есть приложения для разных целей. Мое любимое — Twisty Timer, но если вы раньше не сталкивались с кубиком Рубика, попробуйте Cube Algorithms. А тем, кому просто нравиться процесс сборки, подойдет Cube X. Интерактивные игры не так интересны, как реальные, но если вы хотите чего-то максимально приближенного к реальности, выбирайте Flat Cube.

Cube Algorithms

Принцип работы приложения основан на нескольких способах решения Рубика на разных этапах. Он демонстрирует разные методы, включая 4LLL, CFOP, COLL, F2L и т.д. Сборка достаточно простая, но перед тем, как использовать приложение, вам нужно будет получить представление о перечисленных способах.

Например, вы выбрали самый известный метод решения – CFOP. Он разделит весь процесс на три части – F2L, OLL и PLL, что предусмотрено алгоритмом CFOP. После этого вы увидите все возможные сценарии на этапе F2L и сможете их активировать.

Приложение не сделает из вас профессионала по сборке, но поможет в этом нелегком деле. Видео в YouTube, демонстрирующее основные методы решения головоломки, вместе с Cube Algorithms, которое позволяет реализовать их на практике, творят чудеса.

ASolver

ASolver покажет шаги для решения головоломки. Вам просто нужно снять 6 сторон куба приложению с помощью камеры, и оно покажет лучший вариант сборки. Максимальное количество шагов для куба 3×3 составляет всего 22.

Кроме того, у вас есть возможность собирать разные варианты кубиков – Пирамида, Карманный куб, Мегаминкс и т.д. Цель приложения заключается в том, чтобы просто показать вам оптимальный способ решения головоломки, которая у вас имеется, поэтому оно не демонстрирует технику и не объясняет, какие шаги нужно сделать.

Cube X

Cube X похоже на ASolver, но показывает несколько вариантов решения с разным количеством ходов и формулу для решения. Преимущество приложения заключается в том, что оно предоставляет методы сборки по шаблону.

Вы можете преобразовать куб в разные шаблоны и конструкции вместо того, чтобы собирать его с нуля. Но есть один недостаток – поддержка кубиков только 3*3. Если у вас другой вариант, то придется использовать ASolver.

Magic Cube Solver

Magic Cube Solver – лучший помощник по сборке для iOS. Как и в двух предыдущих случаях, вам нужно просто показать головоломку, а приложение решит ее за 22 шага или меньше.

Кроме того, оно предоставляет небольшие инструкции по сборке, показывая какие шаги для этого нужно сделать. Тем не менее Magic Cube Solver поддерживает только несколько вариантов кубов: 2×2, 3×3, 4×4 и Войд.

Twisty Timer

Twisty Timer – разновидность приложения Pro Timer, которое включает не только таймер, но и другие опции: время прохождения, лучший результат и средний счет. Вы найдете разные варианты таймера для разных алгоритмов – например, OLL и PLL.

Кроме того, у вас будет возможность создавать категории для нескольких таймеров, если вы хотите использовать несколько методов. Twisty Timer поддерживает разные варианты кубиков – 7×7, Пирамида, Мегаминкс, Часы и т.д. Кроме того, есть график, который наглядно продемонстрирует ваш прогресс в игре.

Magic Cube Puzzle 3D

Позволяет собирать кубики Рубика от 2x2x2 до 8x8x8, пирамиду и додекаэдр. Кроме того, в нем есть опция для определения времени, затраченного на ходы, и публикация достижений в социальных сетях. Вы даже можете подключиться к Google Play Games и ознакомиться с таблицей результатов других игроков.

Самая большая проблема с интерактивными кубиками Рубика на телефонах – воспроизведение движения, присущего 3D-объектам, на 2D-экране. В любом случае по сравнению с другими, это приложение имеет лучший интерфейс, а также хорошо распознает движения.

Flat Cube (закрыт)

Flat Cube – модифицированная 2D версия традиционного кубика Рубика. У вас будет квадрат 3×3 со случайно расположенными цветами, и вам нужно будет сделать так, чтобы одинаковые грани образовывали строку или столбец.

Когда вы перемещаете один блок, весь ряд сдвигается горизонтально или вертикально в соответствии с вашим движением. То есть, вы будете самостоятельно собирать кубик Рубика так, как делали бы это в реальной жизни. По мере прохождения уровней будут появляться кубики 4*4, 5*5 и 7*7.

По неизвестной причине оно недоступно в Play Store, поэтому вам нужно скачать АРК-файл и установить его.

Go Cube

Go Cube – это настоящий кубик 3×3, о котором мечтает любой поклонник головоломки. Он способен подключаться к вашему телефону с помощью приложения и отслеживать процесс сборки. Новичкам приложение предоставляет особые возможности для освоения – в нем много инструкций, объясняющих способы решения головоломки с текущего этапа. Go Cube имеет подсветку, позволяющую играть ночью, и просто выглядит очень круто.

Там есть таймер, который останавливается тогда, когда вы обдумываете ход. Вы можете просматривать статистику каждого из этапов и улучшать свои результаты. Если у вас есть друг с Go Cube, у вас есть возможность устраивать соревнования в онлайн. А еще вы можете соревноваться с любым человеком из GoCube Community – сообщества владельцев Go Cube. Есть даже специальные «Комнаты RedBull» для турниров. Представляете масштаб? Но вход в них возможен только финалистам. Каждую неделю составляется таблица лидеров.

Cube Timer

Cube Timer был разработан специально для решения известной головоломки. Оно предоставляет необходимый минимум для игроков – таймер, время прохождения и опцию для перемешивания. Вместо случайного перемешивания приложение предоставит вам возможность перемешать грани определенным образом. Кроме того, можно посмотреть свой лучший результат и средний балл.

Источник

Машина для сборки кубика Рубика на основе системы FAC

Не так давно мы вместе с Wilbert Swinkels закончили работу над машиной, собирающей кубик Рубика. Про нас написали в официальном блоге Raspberry Pi и мы получили массу восторженных отзывов. Тем не менее, в русскоязычном сегменте сети проект как-то остался незамеченным. Так что я решил исправить это упущение, разместив здесь переведенную и дополненную версию оригинального поста.

Под катом речь пойдет (в основном) о софтверной части этой машины, о механической части можно почитать на официальной страничке проекта (да-да, мы знаем, что она немного «олдскульна»)

Вступление

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

Разумеется, когда Вилберт предложил мне помочь ему с машиной для сборки кубика Рубика, я не раздумывал ни секунды, тем более, что к тому времени я уже обнаружил в себе страсть к цветным кубикам. На тот момент он уже работал над машиной в течение 4 (!) с лишним лет, однако софтверную часть все еще предстояло написать.

Опыта программирования под Raspberry Pi и Arduino у меня не было совсем, но в целом задача показалась мне довольно несложной. Конечно же, я ошибался 🙂

Hardware

Сама машина построена с помощью модульной системы FAC. Это что-то вроде советского конструктора, но созданного для прототипирования серьезных и сложных механизмов. Во второй половине прошлого века ее очень активно использовали в лабораториях Philips и других компаний и университетов.

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

Микроконтроллер

Первым делом мы решили использовать Raspberry Pi вместо Arduino. Главным образом это связано с тем, что «умные» алгоритмы решения кубика Рубика требуют значительного объема памяти и процессорных мощностей. В предыдущих попытках использовался примитивный трехслойный алгоритм, но в этот раз мы решили использовать алгоритм Коцембы. Кроме того, мне не очень хотелось писать все на С (хотя частично все же пришлось).

В стандартной версии Raspberry Pi нам не хватило пинов, чтобы подключить все имеющиеся моторы, поэтому мы заказали Development Kit. Кстати, очень советую: пинов не только больше, но и расставлены они, на мой взгляд, более логично. К тому же, на этой плате два разъема для камеры вместо одного.

Первая версия сканера

Для считывания начальной конфигурации кубика нужно было сканирующее устройство. Идея очень проста: по очереди освещаем поверхность кубика тремя светодиодами: красным, зеленым и синим. Каждый раз замеряем отраженный свет при помощи фоточувствительного резистора. Теоретически, мы должны получить RGB-значения, которые можно использовать для распознавания цвета квадратика. От предыдущих программистов у нас остался proof-of-concept код для Arduino, который, казалось бы, даже работал при определенных условиях.

Первой проблемой, с которой мы столкнулись, было несоответствие напряжения. Как известно, логическая единица на пинах Arduino составляет 5В, в то время как у Raspberry Pi это 3.3В. К счастью, контроллеры шаговых двигателей (stepper motor driver), которые мы использовали, продолжили работать, несмотря на изменение амплитуды импульсов.

Гораздо более критичным оказалось то, что в Raspberry Pi нет аналоговых входов. Из-за этого на Raspberry нельзя просто взять и считать напряжение на фоторезисторе. Это, наверное, очевидно для тех, кто хоть раз с таким сталкивался, но я поначалу об этом даже не задумывался. Порыскав в сети в поисках решения, мы наткнулись на эту статью. В двух словах, мы добавляем в цепь конденсатор, и замеряем время, за которое он зарядится от нуля до логической единицы (это мы можем задетектить с помощью цифрового пина). Время зарядки будет пропорционально сопротивлению фоторезистора, поэтому мы можем судить о количестве света.

Этот подход не только ужасно ненадежен (считать время в питоновском скрипте на Linux с кучей фоновых процессов — неблагодарное дело), но и до невозможности долог. Для того, чтобы сгладить случайные отклонения в показаниях, приходилось производить считывание несколько раз, избавляться от выбросов, и усреднять оставшиеся значения. Тем не менее, нам-таки удалось заставить этот сканер работать:

Вторая (финальная) версия сканера

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

Подружить Arduino с Raspberry Pi оказалось невероятно просто: два провода, конвертер напряжения между ними, и вуаля — у нас есть Serial-интерфейс. А если прикрутить сверху простенький протокол Min, то и программировать это дело — одно удовольствие.

Я перенес всю логику управления сканером на Arduino. Скорость сканирования значительно возросла. Благодаря аналоговым входам, мы можем считывать напряжение напрямую с фоторезисторов, и эти значения очень точны. К тому же, так как Arduino смонтирован непосредственно на сканере, нам нужно гораздо меньше проводов от сканера к Raspberry Pi!

Алгоритм сборки

Сборка кубика Рубика с точки зрения математики — довольно трудоемкая задача. Конечно, речь идет о нахождении оптимального решения, а не «какого-нибудь». Я был удивлен, когда узнал, что число Бога (точная нижняя граница для количества ходов, необходимых для решения произвольного кубика) было найдено лишь в 2010.

В этом проекте мы хотели сократить суммарное время, необходимое для просчета решения и сборки, поэтому нам не подходили ни простой трехслойный алгоритм (он работает быстро, но выдает решения длиной в сотню ходов), ни оптимальный алгоритм (решения короткие, но процесс просчета на Raspberry Pi занимал бы вечность). В результате мы остановились на великолепном «двухфазном» алгоритме немецкого математика Herbert Kociemba. Он способен выдавать субоптимальные решения (в среднем 20 ходов), укладываясь при этом в разумное время.

На сайте автора можно найти реализацию алгоритма на Java. Первым делом я перевел этот код на Python. Это было совсем не сложно, поскольку большая часть программы — это математические операции и перебор вариантов. Однако, я не учел, что алгоритм требует действительно много ресурсов. Нахождение решения при первом запуске заняло более минуты (!) на моем ноутбуке.

Под PyPy с включенным JIT решение заняло 1 секунду на ноутбуке, но на Raspberry Pi все еще требовало порядка минуты. После нескольких попыток ускорить работу питоновской программы (numpy, multiprocessing), я решил все же переписать алгоритм на C. Теперь решение занимает 1-2 секунды даже на Raspberry.

Обе реализации алгоритма я выложил на GitHub.

Управление машиной

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

Помимо основной программы, я сделал интерактивный шелл, который сэкономил мне кучу времени при отладке. В целом, в этой части не было ничего необычного с точки зрения программирования. Для отладки сканирования я генерировал результаты в виде картинок.

Сканирование и распознавание цветов

До этого момента все было интересно, но не сложно. Спустя две недели после начала работы, машина уже могла собирать кубик из заданного состояния. Оставалось только научиться считывать начальную конфигурацию кубика при помощи сканера. У нас уже была «рабочая» программа для Arduino, так что мы не ожидали никаких сюрпризов. Тем не менее, эта часть проекта оказалась самой сложной, и отняла у нас еще 2 месяца трудов.

Показания фоторезисторов

Как я писал выше, мы начали со схемы сканера с конденсаторами. Погрешность такого подхода была ужасающей, поэтому для получения юзабельных значений пришлось делать замеры несколько раз, а затем избавляться от выбросов. После этого мы получили что-то вроде этого (это результат сканирования собранного кубика в темной комнате):

Как видно, результат далек от идеала. Во-первых, значения для одного и того же цвета на разных позициях различны, поскольку фоторезисторы и светодиоды «смотрят» в немного разных направлениях. Во-вторых, некоторые цвета находятся очень близко друг к другу в цветовом пространстве, а порой и вовсе диапазоны значений пересекаются (например, оранжевый и красный иногда дают одинаковые значения). И, наконец, показания очень сильно зависят от внешнего освещения.

Наглядно погрешность сканера на конденсаторах можно увидеть на следующей диаграмме (а вообще, есть интерактивная версия здесь):

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

Как я уже говорил, сканер на конденсаторах заработал, но был очень медленным. Когда мы заменили его другим, со встроенной Arduino, показания стали гораздо «кучнее» (интерактивная версия тут):

Калибровка и кластеризация показаний

Теперь, когда у нас были «сырые» RGB-показания с фоторезисторов, нужно было собственно идентифицировать цвета, чтобы подать конфигурацию кубика на вход алгоритму сборки. Здесь сразу напрашивались два различных подхода: использование цветовых интервалов и алгоритма кластеризации.

Первый подход — это решение «в лоб»: можно было экспериментальным путем определить интервалы значений для каждой стороны кубика (по сути, разбить пространство цвета на непересекающиеся области), и затем просто объединять значения по принадлежности определенному интервалу. При этом, каждую из 9 возможных позиций на грани кубика следует рассматривать отдельно. Такой метод очень просто запрограммировать, но у него есть два существенных недостатка. Во-первых, он привязывает нас к конкретным цветам, а значит мы сможем собирать только строго определенный кубик Рубика. А во-вторых, интервалы возможных значений очень сильно зависят от внешнего освещения. Более того, мы обнаружили, что, в зависимости от внешнего освещения, одно и то же показание может отвечать различным цветам.

Второй подход требует предварительной калибровки значений, чтобы один и тот же цвет давал одинаковые результаты во всех 9 позициях на грани кубика. В этом случае мы можем использовать алгоритм кластеризации для объединения значений в 6 групп. При этом нам не важно, в какие именно цвета раскрашен кубик, лишь бы они были различными. К сожалению, этот метод тоже пришлось «забраковать» из-за вероятностной природы алгоритмов кластеризации: они могут выдать «хороший» результат, но не гарантируют его точность.

Борьба с внешним освещением

Даже с хорошим алгоритмом кластеризации сканирование часто заканчивалось неудачей из-за внешних условий. Алгоритм, откалиброванный в темной комнате, не справлялся с задачей в дневных условиях, и наоборот. Более того, если внешнее освещение было очень ярким (прямой солнечный свет), сканер вообще переставал работать, так как влияние светодиодов становилось едва заметным. Вилберт проделал очень кропотливую работу над изоляцией сканера от внешнего освещения. Пришлось пройти 3 итерации: каждый раз мы думали, что этого будет достаточно, и каждый раз обнаруживалась очередная щель, через которую внешнее освещение попадало на фоторезистор.

Заключение

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

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

Источник