코드에서 루빅스 큐브를 어떻게 표현 하시겠습니까?

코드에서 루빅스 큐브를 어떻게 표현 하시겠습니까?

---

루빅스 큐브를 풀기위한 소프트웨어를 개발하고 있다면 큐브를 어떻게 표현 하시겠습니까?

---

이 ACM 논문 은 루빅스 큐브를 표현하는 데 사용 된 여러 가지 대안을 설명하고 서로 비교합니다. 슬프게도 전체 텍스트를 얻을 수있는 계정이 없지만 설명에 다음과 같이 나와 있습니다.

Rubik 's Cube의 7 가지 대체 표현이 제시되고 비교됩니다 : 3 자리 정수의 3x3x3 배열; 리터럴의 6x3x3 배열; 5x12 리터럴 행렬; ll-by-ll 희소 리터럴 행렬; 54 개 요소 벡터; 4 차원 배열; 3x3x3 중첩 배열입니다. APL 기능은 방향 이동 및 1/4 회전과 큐브를 해결하는 데 유용한 여러 도구에 대해 제공됩니다.

또한이 RubiksCube.java 파일에는 섹션 회전을위한 관련 코드와 함께 매우 깔끔한 표현이 포함되어 있습니다 (실제 코드를 찾는 경우). 셀 및면 배열을 사용합니다.

---

한 가지 방법은 시각적 인 모습에 집중하는 것입니다.

큐브에는 6 개의면이 있고 각면은 3x3 정사각형 배열입니다. 그래서

Color[][][] rubik = new Color[6][3][3];

그런 다음 각 이동은 특정 색상 사각형 세트를 순열하는 방법입니다.

---

최적화를 피하십시오. 객체 지향으로 만드십시오. 내가 사용한 의사 코드 클래스 개요는 다음과 같습니다.

class Square
    + name : string
    + accronym : string

class Row
    + left_square : square
    + center_square : square
    + right_square : square

class Face
    + top_row : list of 3 square
    + center_row : list of 3 square
    + bottom_row : list of 3 square

    + rotate(counter_clockwise : boolean) : nothing

class Cube
    + back_face : face
    + left_face : face
    + top_face : face
    + right_face : face
    + front_face : face
    + bottom_face : face

    - rotate_face(cube_face : face, counter_clockwise : boolean) : nothing

사용되는 메모리의 양은 매우 적고 처리량이 적기 때문에 최적화가 완전히 필요하지 않습니다. 특히 코드 사용성을 희생 할 때 더욱 그렇습니다.

---

큐브를 나타내는 흥미로운 방법은 소프트웨어 "Cube Explorer"에서 사용됩니다. 많은 영리한 수학을 사용하여 그 방법은 5 개의 정수만을 사용하여 큐브를 나타낼 수 있습니다. 저자는 그의 웹 사이트 에서 그의 프로그램 뒤에있는 수학을 설명합니다 . 저자에 따르면 표현은 빠른 솔버를 구현하는 데 적합합니다.

---

이를 수행하는 방법에는 여러 가지가 있습니다. 어떤 방법은 다른 것보다 메모리를 더 효율적으로 사용합니다.

사람들이 3 x 3 x 3 배열의 입방체를 사용하는 것을 보았습니다. 입방체는 색 정보를 저장해야합니다 (예, 그 중심 물체는 사용되지 않습니다). 사람들이 6 개의 배열을 사용하는 것을 보았습니다. 각 배열은 3 x 3의 입방체 배열입니다. 3 x 18 배열의 입방체를 보았습니다. 많은 가능성이 있습니다.

아마도 더 큰 관심사는 다양한 변환을 표현하는 방법입니다. 물리적 큐브의 단일면 회전 (모든 큐브 이동은 본질적으로 단일면의 회 전임)은 많은 입방체 개체를 교체하여 표현해야합니다.

당신의 선택은 당신이 작성하는 어떤 응용 프로그램에 대해서도 의미가있는 것이어야합니다. 큐브 만 렌더링하는 것일 수 있습니다. UI가 없을 수도 있습니다. 큐브를 풀 수 있습니다.

3 x 18 배열을 선택합니다.

---

중요한 20 개의 큐비가 있습니다. 한 가지 방법은 20 개 문자열의 배열입니다. 문자열은 색상을 나타내는 2 개 또는 3 개의 문자를 포함합니다. 한 번의 이동은 7 개의 큐비에 영향을 미칩니다. 따라서 6면 각각에 대해 리매 퍼가 필요합니다.

참고 :이 솔루션은 흰색 중앙에있는 로고 스티커의 방향을 기억하지 못합니다.

그건 그렇고, 나는 누군가가 소프트웨어 루빅스 큐브를 한 번, 아마도 15 년 전에 도왔지만 우리가 그것을 어떻게 표현했는지 기억이 나지 않습니다.

---

큐브를 세 개의 수평 연결 목록과 교차하는 세 개의 수직 원형 연결 목록으로 상상할 수 있습니다.

큐브의 특정 행이 회전 할 때마다 해당 포인터 만 회전합니다.

다음과 같이 표시됩니다.

struct cubeLinkedListNode {
    cubedLinkedListNode* nextVertical;
    cubedLinkedListNode* lastVertical;
    cubedLinkedListNode* nextHorizontal;
    cubedLinkedListNode* lastHorizontal;
    enum color;
}

실제로 2 개의 '마지막'포인터가 필요하지 않을 수 있습니다.

[C로이 작업을 수행했지만 cubeLinkedListNode에 대한 간단한 클래스를 사용하여 Java 또는 C #에서 수행 할 수 있으며 각 클래스는 다른 노드에 대한 참조를 보유합니다. ]

6 개의 연동 순환 연결 목록이 있음을 기억하십시오. 3 세로 3 가로.

각 회전에 대해 해당 순환 연결 목록을 반복하여 회전하는 원과 연결하는 원의 링크를 순차적으로 이동합니다.

Something like that, at least...

---

The short answer is that it depends on how you're going to solve the cube. If your solver is going to use a human method like the layer-by-layer approach or the Fridrich method then the underlying data structure won't make much of a difference. A computer can solve a cube using a human method in negligible time (well under a second) even in the slowest of programming languages. But if you are going to solve the cube using a more computationally intensive method such as Thistlethwaite's 52-move algorithm, Reid's 29-move algorithm, or Korf's 20-move algorithm, then the data structure and programming language are of utmost importance.

I implemented a Rubik's Cube program that renders the cube using OpenGL, and it has two different types of solvers built in (Thistlethwaite and Korf). The solver has to generate billions of moves and compare each cube state billions of times, so the underlying structure has to be fast. I tried the following structures:

1. A three-dimensional array of chars, 6x3x3. The color of a face is indexed like cube[SIDE][ROW][COL]. This was intuitive, but slow.
2. A single array of 54 chars. This is faster than (1), and the row and stride are calculated manually (trivial).
3. 6 64-bit integers. This method is essentially a bitboard, and is significantly faster than methods (1) and (2). Twisting can be done using bit-wise operations, and face comparisons can be done using masks and 64-bit integer comparison.
4. An array of corner cubies and a separate array of edge cubies. The elements of each array contain a cubie index (0-11 for edges; 0-7 for corners) and an orientation (0 or 1 for edges; 0, 1, or 2 for corners). This is ideal when your solver involves pattern databases.

Expanding on method (3) above, each face of the cube is made up of 9 stickers, but the center is stationary so only 8 need to be stored. And there are 6 colors, so each color fits in a byte. Given these color definitions:

enum class COLOR : uchar {WHITE, GREEN, RED, BLUE, ORANGE, YELLOW};

A face might look like this, stored in a single 64-bit integer:

00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001

Which is decoded as:

WGR
G B
WYO

An advantage of using this structure is that the rolq and rorq bit-wise operators can be used to move a face. Rolling by 16 bits effects a 90-degree rotation; rolling by 32 bits gives a 180-degree turn. The adjacent pieces need to be up-kept manually--i.e. after rotating the top face, the top layer of the front, left, back, and right faces need to be moved, too. Turning faces in this manner is really fast. For example, rolling

00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001

by 16 bits yields

00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101

Decoded, that looks like this:

WGW
Y G
OBR

Another advantage is that comparing cube states can in some instances be done using some clever bit masks and standard integer comparisons. That can be a pretty big speed-up for a solver.

Anyway, my implementation is on github: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0 See Model/RubiksCubeModel.{h,cpp}.

Expanding on method (4) above, some of the algorithms for programmatically solving the Rubik's Cube use an iterative deepening depth-first search with A*, using pattern databases as a heuristic. For example, Korf's algorithm utilizes three pattern databases: one stores the index and orientation of the 8 corner cubies; one stores the index and orientation of 6 of the 12 edge pieces; the last stores the index and orientation of the other 6 edges. When using pattern databases, a fast approach is to store the cube as a set of indexes and orientations.

Arbitrarily defining a convention, the edge cubies could be indexed as follows.

0  1  2  3  4  5  6  7  8  9  10 11 // Index.
UB UR UF UL FR FL BL BR DF DL DB DR // Position (up-back, ..., down-right).
RY RG RW RB WG WB YB YG OW OB OY OG // Colors (red-yellow, ..., orange-green).

So the red-yellow edge cubie is at index 0, and the white-green edge cubie is at index 4. Likewise, the corner cubies might be indexed like so:

0   1   2   3   4   5   6   7
ULB URB URF ULF DLF DLB DRB DRF
RBY RGY RGW RBW OBW OBY OGY OGW

So the red-blue-yellow corner cubie is at index 0, and the orange-green-yellow corner cubie is at index 6.

The orientation of each cubie needs to be kept as well. An edge piece can be in one of two orientations (oriented or flipped), while a corner piece can be in three different orientations (oriented, rotated once, or rotated twice). More details about the orientation of pieces can be found here: http://cube.crider.co.uk/zz.php?p=eoline#eo_detection With this model, rotating a face means updating indexes and orientations. This representation is the most difficult because it's hard for a human (for me at least) to look at a big blob of index and orientation numbers and verify their correctness. That being said, this model is significantly faster than dynamically calculating indexes and orientations using one of the other models described above, and so it's the best choice when using pattern databases. You can seen an implementation of this model here: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model (see RubiksCubeIndexModel.{h,cpp}).

As mentioned, the program also renders the cube. I used a different structure for that part. I defined a "cubie" class, which is a six squares with 1, 2, or 3 colored faces for center, edge, and corner pieces, respectively. The Rubik's Cube is then composed of 26 cubies. The faces are rotated using quaternions. The code for the cubies and cube is here: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model/WorldObject

If you're interested in my Rubik's Cube solver program, there's a high-level overview video on YouTube: https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be

---

The others well addressed describing the physical cube, but regarding the state of the cube... I would try using an array of vector transformations to describe the changes of the cube. That way you could keep the history of the rubiks cube as changes are made. And I wonder if you could multiply the vectors into a transformation matrix to find the simplest solution?

---

As a permutation of the 48 faces which can move. The basic rotations are also permutations, and permutations can be composed, they form a group.

In a program such a permutation would be represented by an array of 48 elements containing numbers 0 to 47. The colors corresponding to the numbers are fixed, so a visual representation can be computed from the permutation, and vice versa.

ReferenceURL : https://stackoverflow.com/questions/500221/how-would-you-represent-a-rubiks-cube-in-code