Electronic Theses and Dissertation

ABSTRAK
Puzzle 15 adalah salah satu puzzle yang pernah populer. Puzzle ini terdiri dari 4 4
grid yang dilabelkan secara acak dengan 1; 2; : : : ; 15 dimana ada sebuah grid yang
dibiarkan tanpa label (disebut blank). Permainan ini dimainkan dengan menggeser
sembarang grid yang berdekatan dengan blank sehingga labelnya bertukar. Tujuan
dari permainan ini adalah: diberikan sembarang posisi (pelabelan) awal dan posisi
akhir, dapatkah posisi akhir dicapai dari posisi awal dengan melakukan sejumlah
hingga pergeseran? Dalam tulisan ini akan dijelaskan bagaimana memodelkan
permainan Puzzle 15 kedalam grup permutasi. Kemudian akan dicari karakterisasi
keterselesaiannya. Karakterisasi yang didapatkan juga menyimpulkan bahwa jika
posisi akhir ditetapkan, maka ada tepat setengah (yaitu 16!=2) dari keseluruhan kemungkinan
posisi awal yang dapat dibawa ke posisi akhir.
Kata Kunci: Puzzle 15, grup permutasi, karakterisasi ketrselesaian.
ABSTRACT
The so-called 15-Puzzle is one of favorite puzzles that are well known to public at the
earlier time. It consists of 44 grids that are labeled randomly by 1; 2; : : : ; 15 where
there is a distinguished grid (called blank) with no label associated to it. By a move in
this puzzle we mean sliding any grids that are adjacent to the blank so that its labels
are exchanged. The purpose of the game is: given any initial position (labelling) and
any target position, can the target position reacheble from the initial by ?nite number
of moves? We will determine a characterization for the solvability of 15-Puzzle by
interprets it into theory of permutation groups. The obtained characterization also
tell us that if the target position is ?xed, then there are exactly half of the initial
positions that can be moved to the target position.
Keywords: 15-Puzzle, permutation groups, solvability characterization.

Tidak Tersedia Deskripsi