15-Puzzle Solver

Sebuah program dalam bahasa python untuk menyelesaikan permainan 15-puzzle dengan menggunakan algoritma Branch and Bound

General Info
Technologies Used
Usage
Running
Project Status
Acknowledgements
Contact

General Information

Program ini akan menampilkan langkah langkah penyelesaian 15-puzzles. Langkah langkah tersebut diperoleh dengan menggunakan algoritma Branch and Bound. Nilai bound tiap simpul adalah penjumlahan cost yang diperlukan untuk sampai suatu simpul x dari akar, dengan taksiran cost simpul x untuk sampai ke goal. Taksiran cost yang digunakan adalah jumlah ubin tidak kosong yang tidak berada pada tempat sesuai susunan akhir (goal state)

Technologies Used

Python - version 3.9.1

Usage

clone repository github ini dengan mengetikkan di CMD

git clone https://github.com/3sulton/Tucil3_13520033.git

akan muncul folder Tucil3_13520033. Arahkan path pada cmd ke dalam folder src tersebut dengan menuliskan cd Tucil3_13520033/src

Running

setelah cmd berada di dalam folder src, ketik command berikut

    py main.py

Pengguna dapat memilih untuk mendapatkan puzzle secara random atau dapat menggunakan puzzle sendiri

Please enter the method to generate puzzle:
1. Random
2. Manual from file
Your choice:

Apabila memilih untuk memasukkan puzzle sendiri, buat sebuat file berisi puzzle dengan nomor 1 - 15, slot kosong ditulis dengan huruf x. Contoh:

masukkan file puzzle tersebut ke dalam folder tests
misalkan kita akan menjalankan file puzzle matriks2.txt yang berada di dalam folder tests

Please enter the method to generate puzzle:
1. Random
2. Manual from file
Your choice: 2
1. Run all the file in the tests folder
2. Run a specific file
Your choice: 2
Please enter the file name: matriks2.txt

program akan menampilkan solusi dari persoalan apabila puzzle dapat dipecahkan

====================================
Your puzzle:
+----+----+----+----+
| 01 | 02 | 03 | 04 |
+----+----+----+----+
| 05 | 06 |    | 08 |
+----+----+----+----+
| 09 | 10 | 07 | 11 |
+----+----+----+----+
| 13 | 14 | 15 | 12 |
+----+----+----+----+
====================================
Puzzle Parity:
01 : 0
02 : 0
03 : 0
04 : 0
05 : 0
06 : 0
07 : 0
08 : 1
09 : 1
10 : 1
11 : 0
12 : 0
13 : 1
14 : 1
15 : 1
16 : 9
------------------------------------
sum of kurang: 15
X: 1
sum of kurang + X: 16
====================================

Puzzle can be solved
Start solving...

====================================
Solution found
+----+----+----+----+
| 01 | 02 | 03 | 04 |
+----+----+----+----+
| 05 | 06 |    | 08 |
+----+----+----+----+
| 09 | 10 | 07 | 11 |
+----+----+----+----+
| 13 | 14 | 15 | 12 |
+----+----+----+----+
+----+----+----+----+
| 01 | 02 | 03 | 04 |
+----+----+----+----+
| 05 | 06 | 07 | 08 |
+----+----+----+----+
| 09 | 10 |    | 11 |
+----+----+----+----+
| 13 | 14 | 15 | 12 |
+----+----+----+----+
+----+----+----+----+
| 01 | 02 | 03 | 04 |
+----+----+----+----+
| 05 | 06 | 07 | 08 |
+----+----+----+----+
| 09 | 10 | 11 |    |
+----+----+----+----+
| 13 | 14 | 15 | 12 |
+----+----+----+----+
+----+----+----+----+
| 01 | 02 | 03 | 04 |
+----+----+----+----+
| 05 | 06 | 07 | 08 |
+----+----+----+----+
| 09 | 10 | 11 | 12 |
+----+----+----+----+
| 13 | 14 | 15 |    |
+----+----+----+----+
====================================
--- 0.01699972152709961 seconds ---
Arised Node: 10

Project Status

Project is: complete

Acknowledgements

Pustaka ini dibuat untuk memenuhi Tugas Kecil 3 IF2211 Strategi Algoritma
Proyek ini didasarkan pada dokumen ini untuk pemeriksaan reachable puzzle dan artikel ini untuk pendekatan algoritma branch and bound
Many thanks to Pak Rinaldi Munir selaku pengajar K03 IF2211 Strategi Algoritma

Contact

Created by @3sulton - 13520033 / Tri Sulton Adila

3sulton/Tucil3_13520033