Seminar Tugas Akhir

Agung Hargiantoro
g54090039

Pemodelan 8-Puzzle Menggunakan Integer Linear Programming

8-puzzle adalah puzzle versi ukuran yang lebih kecil dari 15-puzzle, yaitu salah satu jenis permainan teka-teki yang ditemukan oleh Noyes Palmer Chapman yang merupakan seorang kepala kantor pos di Canastota, New York pada awal 1874. Permainan ini bertujuan untuk menyusun blok-blok yang memiliki angka 1 sampai 8 dalam suatu bidang persegi yang memiliki ruang untuk 9 blok dengan satu ruang kosong yang tersedia. Permainan dilakukan dengan menggeser salah satu blok ke ruang kosong yang tersedia sehingga mengubah urutan angka-angka yang terdapat pada blok sampai pada akhirnya urutannya sesuai dengan yang diharapkan (angka-angkanya berurutan dari 1 sampai 8 dengan ruang kosong di pojok kanan bawah). Pada tahun 1870-an Sam Loyd menimbulkan kegemparan di Amerika Serikat, Inggris dan Eropa dengan menawarkan hadiah $ 1000 untuk siapa saja yang dapat menyelesaikan puzzle miliknya, yaitu 15-puzzle dengan angka berurutan 1 sampai 13 tetapi angka 14 dan 15 ditukar. Banyak yang telah meneliti puzzle tersebut, salah satunya Johnson & Story (1879) yang membuktikan bahwa tidak ada solusi untuk puzzle Sam Loyd tersebut (Archer 1999). Hal ini mendorong banyak orang untuk meneliti berbagai hal mengenai 15-puzzle dengan berbagai metode. Salah satu hal menarik adalah bahwa adanya kondisi awal tertentu pada puzzle ini yang tidak memiliki solusi dan salah satunya dijelaskan oleh Aaron F. Archer dalam A Modern Treatment of 15-Puzzle dan tentunya pada 8-puzzle juga terdapat suatu susunan awal yang tidak dapat mencapai susunan solusi. Dalam makalah ini akan digunakan integer linear programming untuk diterapkan pada permainan 8-puzzle sehingga dapat ditentukan langkah-langkah yang akan diambil sehingga puzzle ini dapat diselesaikan.