Simple Expert System on Prolog “Rubik’s Cube Puzzle”

@Mo2nCha’09 et all

1. What is a Rubik’s cube and what’s the problem? ( Apa sih kubus Rubik dan apa yang menjadi masalahnya?)

Rubik’s cube is a simple looking puzzle. It is a cube with nine tiles on each face. In its solved state each of the sides is made up of tiles of the same color, with a different color for each side. Each of the tiles is actually part of a small cube, or cubie. Each face of the cube (made up of nine cubies) can be rotated. The mechanical genius of the puzzle is that the same cubie can be rotated from multiple sides. A corner cubie can move with three sides, and edge cubie moves with two sides. Figure below shows a cube in the initial solved state, and after the right side was rotated 90 degrees clockwise. Then the problem is to take a cube whose sides have been randomly rotated and figure out how to get it back to the initial solved state. The scrambled cube might look like that of figure below.

The problem is, there are an astronomical number of possible ways to try to unscramble the cube, not very many of which lead to the solved state. To reach a solution using a blind search algorithm is not feasible, even on the largest machines. A human expert can unscramble the cube in well less than a minute. The difficulty with solving the cube revolves around the fact that if you move one cubie, you have to move seven other cubies as well (the center one doesn’t really go anywhere). This is not a big problem in the early stages of unscrambling the cube, but once a number of tiles are positioned correctly, new rotations tend to destroy the solved parts of the cube. The experienced cube solver knows of complex sequences of moves which can be used to manipulate a small portion of the cube without disturbing the other portions of the cube. For example a 14 move sequence can be used to twist two corner pieces without disturbing any other pieces.It is important to realize there are actually two different senses of solving the cube. One assumes the problem solver has no previous knowledge of the cube. The other assumes the individual is an expert familiar with all of the intricacies of the cube. In the first case, the person solving the cube must be able to discover the need for complex sequences of moves and then discover the actual sequences. The program does not have anywhere near the level of “intelligence” necessary to solve the cube in this sense.In the second case the person is armed with full knowledge of many complex sequences of moves which can be brought to bear on rearranging various parts of the cube. The problem here is to be able to quickly determine which sequences to apply given a particular scrambled cube. This is the type of “expertise” which is contained in the Rubik’s cube program. In the following sections we will look at how the cube is represented, what is done by searching, what is done with heuristics, how the heuristics are coded, how the cube is manipulated, and how it is displayed.

As we could say in Bahasa, permasalahan yang ada pada kubus rubik adalah bagaimana mengacak sebuah rubik kubus yang teratur dengan memutar 90 derajat searah jarum jam menjadi sebuah susunan kubus yang acak, kemudian dari posisi dan susunan yang acak tersebut dikembalikan kepada susunan semula (teratur), seorang ahli puzzle kubus bisa saja memecahkan masalah tersebut hanya dalam hitungan menit, tapi buat orang awam mencari susunan yang tepat untuk satu sisi kubus bisa memecah formasi sisi lainnya, dalam asumsi penyelesaiannya ada dua tipe asumsi orang yang dapat menyelesaikan, satu adalah seorang yang awam tentang puzzle kubus yang kedua memang seorang tersebut sudah ahli didalamnya. Sekarang bagaimana menggunakan aplikasi Prolog agar urutan penyelesaiannya bisa cepat, meskipun sebuah program tidak memiliki indera tertentu untuk menyelesaikan puzzle ini.

2. Modelling Rubik’s Cube

The Standard cube has 5.7 cm ribs, Puzzle has 26 miniature cubes on the surface. Center of each cube surface is the main box position has remained a central mechanism. With structure, the small cubes can be played. The remaining 21 pieces of the cube that can be changed its position while the other 6 as The main axis is fixed but still can rotated. Normal Rubik’s cube (3x3x3) has (8! × 38-1) × (12! × 212-1) / 2 = 43.252.003.274.489.856.000 different positions (permutations). Based on the size of the position all cubes can be solved with 27 steps or less. If every permutation attempted 1 by one it will take 261 years light. And if the surface of the cube of each permutasinya spread will be proportional with 256 times the size of the earth In fact there are (8! × 38) × (12! × 212) = 519.024.039.293.878.272.000 possibilities compilation of each piece to build this cube, but 1 in 12 that can be achieved. This is because there are no steps to do sequence so as to exchange a pair of or rotate pieces contained in the corner. Rubik’s cube can be represented as a finite state machine and receive language like any other machine. Language accepted composed of strings of each step. Even so, many of the assumptions the status of this machine enormous. This causes the process status of the search space is very difficult to do except that most likely removed at the time of checking. This machine can be modeled with a focus to the small boxes that build koyal big. Small boxes are also a finite state machines that accept languages certain. All slices of the language accepted by setipa small box is the language accepted by a large box.

Or in Bahasa we could say that : Kubus standar memiliki ukuran rusuk 5.7cm. Puzzle memiliki 26 miniatur kubus padapermukaannya. Kubus pusat dari setiap permukaannya adalah kotak utama yang posisinya sudah tetap sebagai mekanisme pusat. Dengan struktur tersebut, kubus-kubus kecil lainnya dapat diputar. Tersisa 21 potongan kubus yang dapat diubah posisinya sedangkan 6 lainnya sebagaisumbu utama yang tetap tetapi tetap dapat dirotasikan. Rubik’s cube normal (3x3x3) memiliki (8! × 38−1) × (12! × 212−1)/2 = 43.252.003.274.489.856.000 posisi berbeda(permutasi). Berdasarkan besarnya jmlah posisi tersebut, semua kubus dapat dipecahkan dengan 27 langkah atau kurang. Jika setiap permutasi dicoba 1 per satu maka akan membutuhkan waktu 261 tahun cahaya (aji gilee…selama itukah?!) Dan apabila permukaan kubus dari setiap permutasinya dibentangkan maka akan sebanding dengan 256 kali luas bumi Faktanya terdapat (8! × 38) × (12! × 212) = 519.024.039.293.878.272.000 kemungkinan penyusunan dari setiap potongan untuk membangun kubus ini, tapi 1 diantara 12 yang dapat dicapai. Hal ini dikarenakan tidak ada langkah yang dilakukan secara berurutan sehingga dapat menukar sepasang atau merotasikan potongan yang terdapat di pojok. Rubik’s cube dapat direpresentasikan sebagai mesin status terhingga dan menerima bahasa seperti mesin lainnya. Bahasa yang diterima tersusun atas string setiap langkah. Walau begitu, banyaknya status yang menjadi asumsi mesin ini sangatlah besar. Hal ini menyebabkan proses pencarian ruang statusnya sangat sulit dilakukan kecuali jika sebagian besar kemungkinan dihilangkan pada saat pengecekan.
Mesin ini dapat dimodelkan dengan fokus kepada kotak-kotak kecil yang membangun koyal besar. Kotak-kotak kecil tersebut juga merupakan mesin status berhingga yang menerima bahasa tertentu. Semua irisan dari bahasa yang diterima oleh setiap kotak kecil adalah bahasa yang diterima oleh kotak besar

The core of the program has to be the knowledge representation of the cube and its fundamental rotations. The cube lends itself to two obvious representation strategies. It can either be viewed simply as 54 tiles, or as 20 cubies (or pieces) each with either two or three tiles. Since much of the intelligence in the program is based on locating pieces and their positions on the cube, a representation which preserves the piece identity is preferred. However there are also brute force search predicates which need a representation which can be manipulated fast. For these predicates a simple flat structure of tiles is best. The next decision is whether to use flat Prolog data structures (terms) with each tile represented as an argument of the term, or lists with each element a tile. Lists are much better for any predicates which might want to search for specific pieces, but they are slower to manipulate as a single entity. Data structures are more difficult to tear apart argument by argument, but are much more efficient to handle as a whole. By using fixed length records, some Prologs use lists internally thus changing the performance trade-offs mentioned.

*the phrase  “hidden”  is the part that cant be viewed when we look the cube from the front

The tabel above mentioning about 4 basic types of pieces cube different. Corner cube, cube ribs, the middle cube (on each surface), and the center cube is not visible from the outside. As a convention, the middle cube hasa fixed position (though can be rotated). This meant that every other piece of the cube still can be moved without having to go move the cube center. In fact, the cube center always the same when direlasikan with others. Consider each cube was fixed can be symbolized as the direction. Each piece of the cube has 6 sides. If we move the pieces of the available cube
of the whole cube (), we can find 6 side of the cube and identify colors indicates the direction of what. This information can be used to define the status of a cube pieces with the following examples:

mc(Front,Top,Left,Hidden,Bot,Right) atau mc(F,T,L,H,B,R)

Where each argument has a meaning: green (g), white (w),  orange (o), yellow (Y), blue (b), red (r), none (n). Suppose Instantiation of the cube pieces first as mc (n, n, o, y, b, n). This means under the front-facing surfaces are considered no color (or “none”), the top also “None”, the left side of orange, part “Hidden” is yellow, bottom color blue, the right is “none”. (This initiation produce the first piece of the cube as position found). The result of all this is that we do not need to describe the status of the color on every surface: we can solve cube pieces as small cubes for later recorded orientation. For example, the first piece of cube can be positioned with the color orange as front. But we also need to know orientation to know their status. At side in front of orange, yellow sides will facing up, right, bottom or left. Within other words cut the cube has a total of 24 pieces status .

cube(X1, X2, X3, X4, ………., X53, X54).%this representing the cube structure

[p(X1), p(X2), …p(X7, X8, X9), …p(X31, X32), p(X33, X34), …]. %where each X represents a tile, or by the list, where each p(..) represents a piece. A piece might have one, two, or three arguments depending on whether or not it is a center piece, edge piece, or corner piece.

goalstate( cube(‘F’, ‘R’, ‘U’, ‘B’, …………)). % The tiles are each represented by an uppercase letter representing the side of the cube the tile should reside on. These are front, back, top, bottom, right, and left. (The display routine maps the sides to colors.) Quotes are used to indicate the tiles are constants, not variables. Using the constants, the solved state (or goal state of the program) is stored as the Prolog fact goalstate/1

Having decided on two representations, it is necessary to quickly change from one to the other. Unification has exactly the power we need to easily transform between one notation of the cube and the other. A predicate pieces takes the flat structure and converts it to a list.

pieces( cube(X1, X2, ……. X54), [p(X1), ……p(X7, X8, X9), …..]).

If Z is a variable containing a cube in structure notation, then the query: ?- pieces(Z, Y). %Will bind the variable Y to the same cube in list notation. It can also be used the other way.

The following query can be used to get the goal state in list notation in the variable PieceState:

?- goalstate(FlatState), pieces(FlatState, PieceState).
FlatState = cube(‘F’, ‘R’, ‘U’, ‘B’, ……).
PieceState = [p(‘F’), p(‘R’), ….p(‘R’, ‘U’),….p(‘B’, ‘R’, ‘F’), ….]. % The first goal unifies FlatState with the initial cube we saw earlier. pieces/2 is then used to generate PieceState from FlatState.

3. Rotation (Perputaran)

Unification also gives us the most efficient way to rotate a cube. Each rotation is represented by a predicate which maps one arrangement of tiles, to another. The first argument is the name of the rotation, while the second and third arguments represent a clockwise turn of the side. For example, the rotation of the upper side is represented by:

mov(u, cube(X1, …X6, X7, X8, X9, …),
cube(X1, …X6, X20, X19, X21, …))

We can apply this rotation to the top of the goal cube:

?- goalstate(State), mov(u, State, NewState).

The variable NewState would now have a solved cube with the upper side rotated clockwise.

Since these can be used in either direction, we can write a higher level predicate that will make either type of move based on a sign attached to the move.

move(+M, OldState, NewState):-
mov(M, OldState, NewState).

move(-M, OldState, NewState):-
mov(M, NewState, OldState).

Having now built the basic rotations, it is necessary to represent the complex sequences of moves necessary to unscramble the cube. In this case the list notation is the best way to go. For example, a sequence which rotates three corner pieces is represented by:

seq(tc3, [+r, -u, -l, +u, -r, -u, +l, +u]).

The sequence can be applied to a cube using a recursive list predicate, move_list/3:

move_list([], X, X).

move_list( [Move|T], X, Z):-
move(Move, X, Y),
move_list(T, Y, Z).

At this point we have a very efficient representation of the cube and a means of rotating it. We next need to apply some expertise to the search for a solution.

4. Advanced Rules

The most obvious rule for solving Rubik’s cube is to attack it one piece at a time. The placing of pieces in the solved cube is done in stages. In Black & Taylor’s book they recognize six different stages which build the cube up from the left side to the right. Some examples of stages are: put the left side edge pieces in place, and put the right side corner pieces in place. Each stage has from one to four pieces that need placement. One of the advantages of writing expert systems directly in a programming language such as Prolog, is that it is possible to structure the heuristics in an efficient, customized fashion. That is what is done in this program.

The particular knowledge necessary to solve each stage is stored in predicates, which are then used by another predicate, stage/1, to set up and solve each stage. Each stage has a plan of pieces it tries to solve for. These are stored in the predicate pln/2. It contains the stage number and a list of pieces. For example, stage 5 looks for the four edge pieces on the right side:

pln(5, [p(‘R’, ‘U’), p(‘F’, ‘R’), p(‘R’, ‘D’), p(‘B’, ‘R’)]).

Each stage will also use a search routine which tries various combinations of rotations to position a particular target piece. Different rotations are useful for different stages, and these too are stored in predicates similar to pln/2. The predicate is cnd/2 which contains the candidate rotations for the stage.

For example, the first stage (left edge pieces) can be solved using just the simple rotations of the right, upper, and front faces. The last stage (right corner pieces) requires the use of powerful sequences which exchange and twist corner pieces without disturbing the rest of the cube. These have names such as corner-twister 3 and tri-corner 1. They are selected from Black and Taylor’s book. These two examples are represented:

cnd(1, [r, u, f]).

cnd(6, [u, tc1, tc3, ct1, ct3]).

The stage/1 predicate drives each of the stages. It basically initializes the stage, and then calls a general purpose routine to improve the cube’s state. The initialization of the stage includes setting up the data structures that hold the plan for the stage and the candidate moves. Stage also reorients the cube for the stage to take advantage of symmetries and/or make for better displays.