Electronic Theses and Dissertation

ABSTRAK
Puzzle mn 1 merupakan generalisasi dari Puzzle 15: Puzzle ini terdiri dari m  n
grid yang dilabelkan dengan 1; 2; : : : ;mn 1 dan sebuah grid tanpa label (disebut
blank). Dalam permainan ini, diberikan sembarang posisi awal (pelabelan dari se-
mua grid) dan sebuah posisi akhir, maka langkah demi langkah dilakukan agar posisi
akhir dapat dicapai dari posisi awal. Langkah yang dibolehkan hanyalah menggeser
sembarang grid yang berdekatan dengan blank sehingga labelnya bertukar. Tulisan
ini ingin membahas bila mana posisi akhir tidak dapat dicapai dari posisi awal. Ada
(mn)! kemungkinan untuk posisi awal. Akan dibuktikan bahwa adaminimal
1
2
(mn)!
yang membuat puzzle ini mustahil untuk diselesaikan. Sementara untuk setengah
posisi awal lainnya tidak dibahas apakah posisi-posisi awal itu dapat mencapai ke
posisi akhir.
Kata Kunci: Puzzle mn 1, grup permutasi, posisi mustahil
ABSTRACT
The mn 1 Puzzle is the generalization of 15 Puzzle that consist of m  n grids.
Each gridwas labeled by number 1; 2; : : : ;mn 1 and therewas an empty grid called
blank. In this game, given any initial position and a final position, we apply a finite
number of moves to the initial position so we can get a final position. A move is an
action of sliding any grid adjacent to the blank so that the label will be switched. In
this paper, we will talk about the situation when the final position cannot be achieve
from the initial position. There are mn! possibilities of the initial position, we will
prove that at least half of them cannot be solved. But we are not going to discuss
about either the other half of possibilities can be solved or not.
Keywords: mn 1 Puzzle, permutation group, impossible position

Tidak Tersedia Deskripsi