Introduction

I'm Nyanyan, a hardware / software engineer whose hobby is the speed cube, which solves the Rubik's cube quickly. This time, I will explain Problem of Floppy Cube of PC Koshien 2014, and from there, Rubik's Cube etc. I will explain the ** general-purpose writing method ** of the program that solves the three-dimensional puzzle.

I'm currently building a (probably) the fastest robot in the world to solve a 2x2x2 Rubik's cube, and I used the knowledge I had cultivated to solve this problem. This knowledge is overkill for this issue, but I'm writing this article because I'd love to introduce it.

Problem overview

What is a floppy cube?

Image from iOS(10).jpg It's a puzzle like the one in the picture. Sometimes called "Rubik's Cube with only one step", that's right. The point is that there are four axes (up, down, left, and right) that can be aligned by rotating them 180 degrees. According to the English wiki (https://en.wikipedia.org/wiki/Floppy_Cube), the number of combinations is $ 192 $ (quite $ 4.3 \ times10 ^ {19} $ for a regular Rubik's cube). God's number (up to $ N $, which you can always get if you have a hand) is $ 8 $.

problem

The full text of the question is here The color state of each side of the floppy cube is given as a list of numbers, so please output how many hands you can align from this state. With a memory limit of $ 131072 $ KB and a time limit of $ 1 $ seconds, you will be given up to 30 puzzle states (that is, you must output answers within an average of $ 33 $ ms per puzzle).

The state of the puzzle is given by a list of numbers. This sequence is the number of puzzle stickers (colored) $ 30 $ ($ 9 $ on the front and back $ \ times 2 = 18 $, $ 3 $ on the sides $ \ times4 = 12 $ for a total of $ 30 $ ), Each color is represented by the number $ 1,2,3,4,5,6 $. Of the numbers that represent this color, $ 1,3 $ is the front / back color, and the others are the side colors.

Assuming that the array representing this color is $ p $, the correspondence between the numbers (starting with $ 0 $) and the faces of $ p $ is as shown in the figure below.

Here is the complete state in the sample case.

1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3

The input is given as follows:

Number of puzzles entered N(<=30)
Space-separated puzzle sequence sequence p_1
p_2
...
p_n

Let's solve the problem.

Intuitive but less versatile method

The first method you might think of is a straightforward simulation and breadth-first search. It's less versatile, but relatively easy to implement (although simulating rotation is very tedious).

Estimate the amount of calculation for one puzzle. The next move you can make for each state is to turn either up, down, left, or right by $ 180 $, so there are $ 4 $ (after that, we will devise this to further reduce the amount of calculation). And since you can get it by hand for up to $ 8 $, the amount of calculation is at most

O(4^8)=O(6.6\times10^4)

It will be. Even if 30 puzzle states are given, the amount of calculation will be $ O (2.0 \ times10 ^ 6) $, which seems to be in time.

Now, the troublesome part of this method is the implementation of actually moving the puzzle. This time, the operation of rotation is expressed by manipulating the input sequence $ p $ itself. This method is cumbersome and has no versatility, so I will use a different method later. Floppy cubes always use $ 180 $ degree rotation, so you can implement it by properly selecting and swapping the two stickers (sequence elements). The result of implementation is here (see the link for the code) .. I did AC for the time being. The execution time was $ 0.35 $ seconds and the memory usage was $ 14580 $ KB.

** Good points of this method ** 1, If you can implement without making a mistake about where and where to swap, the rest is just breadth-first search, so the idea is simple ** Bad points of this method **

The implementation of where and where to swap is non-essential and lazy (I made a mistake too)
Since it is breadth-first search, it uses memory as it is.
Not versatile (writing a program to solve a normal Rubik's cube this way makes the implementation of rotation very sluggish)

Intuitive method improvements

Now, let's improve the previous program. In fact, this program can easily reduce the amount of calculation.

** Do not turn the same hand that you turned just before ** ** For example, just before turning up, down and then not turning up ** ** If you don't get it in 7 moves, the answer will always be 8 (because you will get it in 8 moves) **

By implementing these three, the amount of calculation can be reduced. Let's specifically estimate the amount of calculation for one puzzle. Consider the case of maximum (8 hands). (* It is not mathematically strict. Actually, the amount of calculation is likely to increase slightly)

O(4\times3^6-2\times5\times3^4)=O(2.1\times10^3)

Since the amount of calculation of the previous program was $ O (6.6 \ times10 ^ 4) $, it was possible to reduce it considerably.

The result I tried is here. The execution time was $ 0.08 $ seconds and the memory was $ 6704 $ KB. Time and memory have improved considerably (although the code above is AC).

Think of a generic method

Overview

Although it is amakudari, there is a general method of writing puzzles as follows (those who like Rubik's cube may know).

Think about ** parts ** instead of stickers
Focus on the ** position ** and ** orientation ** of the parts
Since the puzzle is composed of parts of several shapes, ** consider the above method for each shape of the parts **

Let's think concretely with this floppy cube. There are three types of floppy cubes with stickers (colored): "corners", "edges", and "centers". Let's think a little more about each.

corner It moves when it is rotated. The direction (front and back) changes when rotated

** Edge ** It does not move even if it is rotated (because it rotates around the edge part) The direction (front and back) changes when rotated

Center Does not move even if rotated The direction does not change even if it is rotated

Considering these facts, we can see that the following three types of information are all that is needed to represent the state of the puzzle.

Positions of each of the four corner parts (CP = Corner Permutation)
Orientation of each of the four corner parts (CO = Corner Orientation)
Orientation of each of the four edge parts (EO = Edge Orientation)

** Addendum Although strict proof has not been made, it seems that CO will be automatically aligned if CP is aligned. In the article, I will leave it as it is written in consideration of CO, but I will also post a submission link that does not consider CO as an additional note. ** **

In the actual rotation process, the array is tampered with according to the following rules.

position Numbers (names) from 0 to 4 are assigned to the positions of the corner parts (upper left, upper right, lower right, lower left). Number the corner parts themselves from 0 to 4. For example, the i-th element cp [i] of the CP array cp means that the part at location i is named cp [i].

direction Number the corner / edge parts from 0 to 4 respectively. For example, 0 when the parts are facing the front side (the direction they are facing when aligned), and 1 when the parts are facing the back side. For example, if the i-th element co [i] of the CO array is 0, the part at location i is facing up, and if it is 1, it is facing back.

Implementation

It's easier to use classes because each puzzle state is represented by multiple arrays. Also, by setting the number assigned to the position of the part, for example, clockwise, you do not have to manually figure out where to move when writing the rotation process. The disadvantage of this method is that it is a bit cumbersome to convert the color information of each sticker entered into three arrays: CP, CO and EO.

result

The code I wrote and the execution result are here. The execution time was $ 0.12 $ seconds and the memory usage was $ 6860 $ KB.

** Addendum AC was done even for programs that do not consider CO. The submission link is here. The execution time was $ 0.09 $ seconds and the memory usage was $ 6767 $ KB. ** **

Reduce the amount of calculation-pruning

Here, let's use the versatility that is the advantage of the general-purpose code mentioned earlier to perform pre-computation, and use it to prun and reduce the amount of calculation.

Pruning is achieved by terminating the search when it is known that the number of gods is not within 8 moves. Specifically, for each state of CP, CO, and EO, pre-calculate how many hands can be used to prepare only CP for CP, only CO for CO, and only EO for EO. And during the breadth-first search,

** Number of steps taken so far + Maximum number of steps required to align CP, CO, and EO independently **

Is calculated, and when this exceeds the divine number of 8 moves, further search for this node (state) is terminated.

The submission result that implements this is here. The execution time was $ 0.16 $ seconds and the memory usage was $ 6804 $ KB. ** Addendum AC was done even for programs that do not consider CO. The submission link is here. The execution time was $ 0.13 $ seconds and the memory usage was $ 6544 $ KB. ** **

This pruning method performs pre-calculation and calculates the unique number of each of the CP, CO, and EO sequences in each search, so like this time.

The number of next moves that can be turned from one node (state) is small
Maximum search depth (that is, God's number) is shallow (small)

Sometimes there is not much benefit. This time, the execution time has increased a little. However, this pruning has immeasurable benefits when trying to solve puzzles that are more complex than floppy cubes.

Reduce memory usage-IDA *

What we're talking about here is how to deal with the ridiculous memory usage of using breadth-first search when solving some other puzzle that isn't a floppy cube. As an example, when I did a breadth-first search with a 2x2x2 Rubik's cube, the program I wrote ate about 4GB of memory.

What comes out here is a search method called IDA *. For details, the article here is detailed and recommended. I will quote a part from this article.

In a nutshell, IDA * is "repeat a depth-first search (DFS) with a limited maximum depth, increasing the depth." The mechanism of IDA * is to forget the node once searched. If you forget the node, you can free up memory, right?

In IDA *, if a depth-first search is performed up to a depth of $ N-1 $ and no solution is found, the maximum depth is increased to $ N $ and the search is restarted from the beginning. By doing this,

The returned result is always the shortest effort (the shortest procedure can be output with a little tweaking of the implementation)
Very low memory usage

There is a benefit.

However, for nodes (states) with shallow depth, the same search is repeated many times, so the amount of calculation increases slightly. However, since the state of the puzzle increases as an exponential function with respect to the depth, the increase in the amount of calculation is not so large. Let's specifically estimate the amount of calculation in this case. Suppose you are in a puzzle with 7 hands. When breadth-first search was performed, the amount of calculation was about $ O (2.1 \ times10 ^ 3) $ when pruning was ignored. And in IDA *

O(\Sigma_{i=1}^7 (4\times3^{i-1}-2\times(i-2)\times\mathrm{floor}(3^{i-3})))=O(3.3\times10^3)

is. There is not much difference in comparison.

The result of implementation is here. The execution time is $ 0.09 $ seconds, which is faster than the previous program. Memory usage was reduced to $ 6044 $ KB, down from $ 6544 $ KB for breadth-first search. ** Addendum AC was done even for programs that do not consider CO. The submission link is here. The execution time was $ 0.07 $ seconds and the memory usage was $ 6036 $ KB. ** **

Summary

Thank you for reading this far. In particular, the method introduced in the latter half is a very general method, but it is too overkill for floppy cubes. By all means, write a program that solves 2x2 and 3x3 Rubik's cubes using this method, and experience the versatility of this method. For 2x2, I wrote Let's make a robot that solves the Rubik's cube! 2 Algorithms, 3x3 is 7y2n's [Let's write a program to solve the Rubik's cube (Part 2: IDA * search)](https: / We recommend the article /qiita.com/7y2n/items/24785b985e9c30862014).

How to make a program to solve Rubik's Cube starting from PC Koshien 2014 Floppy Cube