8Puzzle Generator

Kok 8Puzzle terus…? :D. Hehehe, mumpung lagi panas, jadi maklum yah…

Objektif permainan 8Puzzle adalah menyusun 9 cell dari keadaan awal (disebut initial state) menjadi susunan akhirnya (goal state). Nah, kalau di permainan nyatanya, permainan ini selalu solvable (dapat dipecahkan), walaupun susunan cell (tile)-nya diacak-acak. Tapi, kalau untuk program yang kita bebas untuk menentukan initial state dan/atau goal statenya, problem bisa saja tidak terpecahkan. Sehingga kalau kita buat algoritma untuk memecahkan 8puzzle, perlu ada testset yang benar-benar bisa dipecahkan.

Saya mencoba membuat program 8puzzle generator untuk membangkitkan testset untuk menguji algoritma yang diimplementasikan di program 8puzzle. Sederhana saja sih. Programnya bisa didownload di sini (untuk Windows) dan di sini (untuk Linux). Belum ada option untuk mengubah goalstatenya. Jadi, menjalankannya langsung dari konsole (Linux/Windows) dengan “./gen8puzzle” atau “gen8puzzle.exe

File yang dihasilkan adalah test_state.h, yang berisi kumpulan initial state dan goal state. Dari yang berkemungkinan tersulit sampai yang termudah adalah sebagai berikut:

/* 8 Puzzle test state */
/* generated by ./gen8puzzle */

/*Tiles*/
typedef struct state {
    int init[10];
    int goal[10];
} TSTATE; 

TSTATE std_state[] = {
{{4,7,8,1,6,5,3,9,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #0 gn=25, hn=19*/
{{5,9,6,7,2,3,4,1,8,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #1 gn=25, hn=19*/
{{4,5,8,7,6,3,2,9,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #2 gn=25, hn=19*/
{{6,9,7,1,2,5,4,3,8,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #3 gn=25, hn=19*/
{{4,1,6,9,8,7,3,5,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #4 gn=25, hn=19*/
{{5,2,1,4,9,7,3,8,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #5 gn=26, hn=18*/
{{5,2,1,4,7,6,3,8,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #6 gn=26, hn=18*/
{{7,4,9,8,5,6,3,2,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #7 gn=26, hn=18*/
{{7,5,4,8,9,6,3,2,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #8 gn=26, hn=18*/
{{3,2,7,5,9,8,6,4,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #9 gn=26, hn=18*/
{{6,2,9,3,8,7,4,1,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #10 gn=26, hn=16*/
{{6,2,7,3,1,8,9,4,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #11 gn=26, hn=16*/
{{4,7,3,5,8,1,2,6,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #12 gn=26, hn=16*/
{{9,4,3,5,7,8,2,6,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #13 gn=26, hn=16*/
{{9,2,6,5,4,1,7,3,8,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #14 gn=26, hn=16*/
{{5,2,7,8,4,1,3,9,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #15 gn=27, hn=17*/
{{5,9,2,8,4,7,3,6,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #16 gn=27, hn=17*/
{{5,2,7,3,8,4,6,9,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #17 gn=27, hn=17*/
{{2,9,7,5,8,4,3,6,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #18 gn=27, hn=17*/
{{8,5,7,9,2,4,3,6,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #19 gn=27, hn=17*/
{{4,6,3,5,8,9,7,2,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #20 gn=27, hn=15*/
{{1,6,7,3,8,9,4,2,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #21 gn=27, hn=15*/
{{1,6,8,9,4,7,3,2,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #22 gn=27, hn=15*/
{{5,6,3,9,4,1,7,2,8,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #23 gn=27, hn=15*/
{{5,9,3,4,6,8,7,1,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #24 gn=27, hn=15*/
{{8,7,9,4,6,5,1,2,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #25 gn=28, hn=14*/
{{7,6,5,4,2,3,8,1,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #26 gn=28, hn=14*/
{{9,5,4,7,6,8,1,2,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #27 gn=28, hn=14*/
{{7,6,5,1,2,8,9,3,4,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #28 gn=28, hn=14*/
{{3,1,9,4,8,7,5,2,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #29 gn=28, hn=14*/
{{4,8,1,5,9,7,3,2,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #30 gn=24, hn=20*/
{{4,8,9,5,7,1,3,2,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #31 gn=24, hn=20*/
{{4,1,7,5,6,2,9,3,8,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #32 gn=24, hn=20*/
{{5,6,2,3,9,1,4,8,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #33 gn=24, hn=20*/
{{5,6,2,3,1,7,4,8,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #34 gn=24, hn=20*/
{{7,6,5,8,3,4,1,9,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #35 gn=29, hn=13*/
{{7,9,6,8,5,4,1,2,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #36 gn=29, hn=13*/
{{7,6,5,8,1,4,2,9,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #37 gn=29, hn=13*/
{{6,9,5,8,7,4,1,2,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #38 gn=29, hn=13*/
{{4,2,1,9,3,8,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #39 gn=29, hn=13*/
{{9,2,1,4,3,8,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #40 gn=30, hn=12*/
{{3,2,1,4,5,8,9,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #41 gn=30, hn=12*/
{{3,2,9,4,1,8,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #42 gn=30, hn=12*/
{{3,2,1,4,7,8,5,6,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #43 gn=30, hn=12*/
{{7,6,5,8,3,4,1,2,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #44 gn=30, hn=12*/
{{6,9,8,4,5,1,3,7,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #45 gn=23, hn=21*/
{{6,4,8,9,7,1,3,5,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #46 gn=23, hn=21*/
{{4,8,6,7,5,9,3,2,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #47 gn=23, hn=21*/
{{4,8,6,9,7,1,3,5,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #48 gn=23, hn=21*/
{{5,9,7,4,1,2,3,8,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #49 gn=23, hn=21*/
{{6,7,8,5,4,1,3,9,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #50 gn=23, hn=23*/
{{6,7,8,3,5,1,4,9,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #51 gn=23, hn=23*/
{{6,8,7,9,5,1,4,3,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #52 gn=23, hn=23*/
{{6,7,8,9,5,2,4,3,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #53 gn=23, hn=23*/
{{4,5,8,6,7,2,3,9,1,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #54 gn=23, hn=23*/
{{4,6,8,5,9,1,3,7,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #55 gn=22, hn=22*/
{{4,7,8,6,9,1,3,5,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #56 gn=22, hn=22*/
{{6,7,8,4,9,1,5,3,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #57 gn=22, hn=22*/
{{6,7,8,5,4,1,9,3,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #58 gn=22, hn=22*/
{{6,7,8,3,9,1,4,5,2,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #59 gn=22, hn=22*/
{{3,1,2,4,8,9,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #60 gn=27, hn=11*/
{{3,2,1,4,8,9,5,7,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #61 gn=27, hn=11*/
{{2,3,1,9,4,8,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #62 gn=27, hn=11*/
{{3,2,1,9,4,8,6,5,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #63 gn=27, hn=11*/
{{7,9,4,8,6,5,1,2,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #64 gn=27, hn=11*/
{{3,2,9,4,6,8,7,1,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #65 gn=26, hn=10*/
{{1,7,3,4,2,8,5,6,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #66 gn=26, hn=10*/
{{9,2,1,4,6,8,7,3,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #67 gn=26, hn=10*/
{{1,5,3,4,2,8,9,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #68 gn=26, hn=10*/
{{1,6,9,5,8,4,7,2,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #69 gn=26, hn=10*/
{{7,9,5,8,2,4,1,6,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #70 gn=25, hn=9*/
{{7,2,5,8,6,4,1,9,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #71 gn=25, hn=9*/
{{3,2,1,8,4,9,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #72 gn=25, hn=9*/
{{3,2,1,9,8,4,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #73 gn=25, hn=9*/
{{7,2,5,8,9,4,1,6,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #74 gn=24, hn=8*/
{{3,2,1,8,9,4,5,6,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #75 gn=24, hn=8*/
{{2,9,5,8,6,4,1,7,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #76 gn=25, hn=9*/
{{1,6,3,4,9,8,7,2,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #77 gn=24, hn=8*/
{{8,3,2,1,9,5,6,7,4,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #78 gn=24, hn=8*/
{{2,1,4,7,9,3,8,5,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #79 gn=24, hn=8*/
{{1,6,3,4,2,8,7,9,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #80 gn=23, hn=7*/
{{1,9,3,4,6,8,7,2,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #81 gn=23, hn=7*/
{{1,6,3,9,4,8,7,2,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #82 gn=23, hn=7*/
{{1,6,3,4,8,9,7,2,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #83 gn=23, hn=7*/
{{1,2,5,6,8,4,7,9,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #84 gn=23, hn=7*/
{{3,1,9,8,2,5,7,6,4,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #85 gn=20, hn=6*/
{{1,2,4,8,6,3,5,7,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #86 gn=20, hn=6*/
{{9,3,1,7,2,4,8,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #87 gn=20, hn=6*/
{{8,2,3,1,6,4,9,5,7,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #88 gn=20, hn=6*/
{{2,1,9,8,4,5,7,6,3,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #89 gn=20, hn=6*/
{{1,9,3,7,2,5,8,6,4,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #90 gn=19, hn=5*/
{{8,2,4,1,6,3,7,9,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #91 gn=19, hn=5*/
{{2,1,3,8,4,9,6,7,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #92 gn=19, hn=5*/
{{1,3,2,9,8,4,7,5,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #93 gn=19, hn=5*/
{{1,9,4,8,2,3,6,7,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #94 gn=19, hn=5*/
{{1,2,3,7,9,5,8,6,4,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #95 gn=18, hn=4*/
{{8,2,4,1,9,3,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #96 gn=18, hn=4*/
{{2,1,3,8,9,4,6,7,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #97 gn=18, hn=4*/
{{1,3,2,8,9,4,7,5,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #98 gn=18, hn=4*/
{{2,1,3,8,9,5,7,6,4,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #99 gn=18, hn=4*/
{{1,9,2,8,4,3,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #100 gn=3, hn=3*/
{{1,2,3,8,4,5,7,9,6,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #101 gn=3, hn=3*/
{{2,9,3,1,8,4,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #102 gn=3, hn=3*/
{{1,2,3,7,8,4,6,9,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #103 gn=3, hn=3*/
{{1,3,4,8,2,9,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #104 gn=3, hn=3*/
{{1,2,9,8,4,3,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #105 gn=2, hn=2*/
{{1,2,3,8,4,5,7,6,9,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #106 gn=2, hn=2*/
{{9,2,3,1,8,4,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #107 gn=2, hn=2*/
{{1,2,3,7,8,4,9,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #108 gn=2, hn=2*/
{{1,3,9,8,2,4,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #109 gn=2, hn=2*/
{{1,2,3,8,4,9,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #110 gn=1, hn=1*/
{{1,2,3,9,8,4,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #111 gn=1, hn=1*/
{{1,9,3,8,2,4,7,6,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #112 gn=1, hn=1*/
{{1,2,3,8,6,4,7,9,5,0},{1,2,3,8,9,4,7,6,5,0}}, /* Test #113 gn=1, hn=1*/
};
/*End of test*/

Di program saya sih, dalam waktu kurang dari 1 detik, problem terpecahkan.

Untuk menggunakan file header tersebut dalam program 8puzzle untuk menguji algoritma yang diterapkan, contohnya adalah sebagai berikut

#include <stdio.h>
#include <stdlib.h>
#include "test_state.h"

int i, j;
char chr_tiles[] = " 12345678 "; /*Char print*/

for (i=0; i < (sizeof(std_state) / sizeof(std_state[0])) ; i++) {
     /*Init state*/
     for (j=0; j < 9; j++) {
        if ( (j%3) == 0 ) printf("\n");
		printf(" %c", chr_tiles[std_state[i].init[j]]);
     }
     printf("\n"); 

     /*Goal state*/
     for (j=0; j < 9; j++) {
        if ( (j%3) == 0 ) printf("\n");
		printf(" %c", chr_tiles[std_state[i].goal[j]]);
     }
     printf("\n"); 
}
Tag:

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: