Authors
Ryohei
Miyadera
Munetoshi Sakaguchi
Daisuke Minematsu |
Ryota
Kawazoe
Toshiro Miura
-
Kwansei Gakuin High School |
 I.
Introduction 
 The Back
and Front Puzzle is a flat version of Rubik's
Cube. Although this is a very simple game compared
to Rubik's Cube, this game is very interesting
in its own way. This game was first introduced by Shigeo
Takagi in Takagi [1]. In this game the front
is colored with red and the back, with yellow.
 Shigeo
Takagi treated the b/f puzzle as if it is a game
you can pick up and rotate like Rubik's Cube. Therefore
two arrangements in graph 1 opposite can be
seen identical, because you can get one from another just
by picking up and rotate horizontally.
We use a different approach. We fix our puzzle on a paper or screen.
Therefore we treat two arrangements shown in the drawing opposite as two different
ones, but our approach can lead to beautiful results that you will see later.
We studied the b/f puzzle as a problem of graph theory,
and found a very beautiful patterns in the puzzle. Takagi studied the game with
3 rows and 3 columns, but first we are going to study the case of 3 rows and
2 columns. Later we are going to study the case of 4 rows. The difference of
the number of rows and columns turned out to be very important factor in the
puzzle.
II.
The case of 2x3 cells
 We
only use five rotations for these arrangements. We name
these rotations R1, R2, R3, R4 and R5.
Example
1: The following pictures show you how
these rotation occur.
Example
2: (a) If you start with  and
use R1, then you get  .
As shown below.
(b)
After that if you use R4, then you get  .
See picture below.
Example
3: If you start with ,
how many arrangements are there that you can get by using
these five rotations? Here you can use rotations as many
times as you want.
Answer:
You can get the arrangements in diagram (2) below.
diagram
(2)
Example
4: It is a good way to use the theory of graphs to
study the b/f puzzle. We denote each arrangement
by a red vertex.
If you can get an arrangement from another arrangement
using only one rotation, then we connect the two vertexes
corresponding to these two arrangements with a blue
line.
For example, look at the vertex 5 and 9. It is easy to see that by
rotation R3, we get arrangement 9 from arrangement 5. Therefore we connect them
with a blue line. In the similar way we can connect other vertexes, and get graph
(3).
When we made graph (3), we chose vertexes with fewer lines
and located them on the first column and the last column. We located
vertexes with more lines in the middle of graph (3) below.
graph
(3)
A
Hamiltonian path is a path between two vertexes of a graph
that visits each vertex exactly once. Can
you find a Hamiltonian path of the above graph?
Answer:
A Hamiltonina path is {1, 2, 7, 4, 3, 5, 9, 13, 14, 11,
16, 15, 10, 8, 12, 6}. It is not difficult to check this
using the above graph.
Perhaps it is easier to see the Hamiltonian path in the list of pictures. Please
see diagram (4) below. The rotations you are going
to use are R1, R5, R4, R3, R5, R3, R5, R1, R4, R5, R3, R5, R2, R1 and R2.
Problem
1: If you start with ,
how many arrangements are there that you can get by using
the five rotations. You can use rotations as many times
as you want.
Answer
to problem 1: If you start with ,
then there are 24 arrangement that you can get by using
the five rotations. It is not difficult to check the
answer once you get one. The order of arrangement in
the following table looks a little bit strange, but this
order is best fit to the structure of the b/f puzzle.
You will see this fact later.
diagram
(5)
Problem
2: Can you make a graph using diagram (5) above?
Can you find a Hamiltonian path?
Answer
to problem 2: See graph (6) below.
graph
(6)
The
following sequence is a Hamiltonian path. It is not difficult
to check this solution {2, 6, 3, 7, 9, 10, 13, 17, 21,
22, 18, 14, 20, 24, 23, 19, 15, 11, 16, 12, 8, 4, 5, 1}.
III.
The case of 2x4 cells
In
the previous section we studied the puzzle with 2 columns
and 3 rows. In this section we are going to study the puzzle
with 2 columns and 4 rows.
 This
time we have 6 rotations.
Example
5: (a) If you start with  and
use R1, then you get  .
(b)
After that if you use R5, then you get  .
Problem
3: If you start with ,
how many arrangements are there that you can get by using
the five rotations. You can use rotations as many times
as you want.
Answer
to problem 3: It is not difficult to get
all the 36 arrangements, but it needs some time to make
a good table with these arrangements. If you get a good
table, then it will make it easier to make a beautiful
graph with it. The strategy is the same. It is better
to locate vertexes with fewer lines in the first and
the last columns.
diagram
(7)
Problem
4: (a) Can you make a beautiful graph using diagram
(7)?
(b) Can you find a Hamiltonian path?
Answer
to problem 4 (a): It is not difficult to make a beautiful
graph (8) using diagram (7). It is better to locate
vertexes with a lot of lines in the middle part of graph,
and vertexes with fewer lines in the first column and
the last columns.
graph
(8)
Answer
to problem 4 (b): It is not easy to find a Hamiltonian
path. To tell you the truth it took Ryohei Miyadera who
is one of the author of this article 6 hours to find
a Hamiltonian path, but it was quite an experience and
gave him a lot of joy when he found one. Perhaps there
are many people who are a lot better than he is in finding
things. If you can use a good software like Mathematica,
it will take only a few minutes to find one.
{2, 6, 3, 7, 9, 17, 10, 18, 30, 20, 32, 33, 25, 13, 21, 15, 27, 35,
28, 36, 29, 19, 31, 34, 26, 14, 22, 16, 24, 11, 23, 12, 8, 4, 5, 1} is a Hamiltonian
path. Once you have an answer, it won't be difficult to check it.
Remark:
We used Mathematica and
the programs in S. Skiena and S. Pemmaraju [1] to make
graphs and diagrams of this article.
References
|
Follow
us on Facebook | 
Report any
error, misspelling or dead link
Come
contattarci | 
Comment
nous contacter
