KHAIRUNNISA NUR FITHRIANI Primary Author mixed material bibliography Banda Aceh FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SYIAH KUALA 2018 id Indonesia

Skripsi

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. COMPUTER SCIENCE 1 ELECTRONIC THESES AND DISSERTATION Universitas Syiah Kuala 51219 2018-12-13 09:38:25 2019-04-26 08:16:47 machine generated