Game Puzzle 8 Blok adalah permainan sederhana yang terdiri dari susunan 9 buah kotak/persegi yang mana 8 kotak diantaranya berisikan angka dari 1 hingga 8, 1 kotak sisanya kosong. Kotak kosong ini digunakan untuk memindahkan 8 kotak atau blok-blok hingga mencapai urutan angka yang diinginkan. Mungkin untuk lebih jelasnya silahkan lihat gambar dibawah ini, gambar berikut ini adalah visualisasi permainan tersebut :
Ya seperti itulah, jadi teringat permainan itu di masa lalu ya?? 
Saat ini saya akan coba membuatnya dalam sebuah permainan komputer sederhana, kenapa sederhana, karena untuk bagian pertama ini saya ingin share dulu game versi text nya, atau versi DOS (Command Prompt). Untuk versi GUI nya akan menyusul di posting selanjutnya :).
Disini agar proses pencarian solusi optimal, saya menggunakan algoritma Simple Hill Climbing yang didukung dengan metode Manhattan Distance untuk mengetahui jumlah atau jarak paling minimum dari persoalan menuju posisi blok yang diinginkan. Untuk lebih jelasnya mengenai Manhattan Distance atau Simple Hill Climbing bisa dicari lebih lanjut di website lainnya :mrgreen:. Untuk hasil contoh jalannya program ini adalah sebagai berikut :
Yap, kira – kira seperti itu, dengan posisi awal dimana urutan angkanya tidak berurutan dan tujuan akhirnya adalah diharapkan angka berurutan menjadi 1,2,3,4,5,6,7 dan 8. Disana terdapat angka 0, itu dimaksudkan atau diibaratkan blok atau kotak yang kosong tadi. Oke, untuk source codenya, bisa dilihat dibawah ini :
public class Puzzle {
public static int initialState[] = { 1, 2, 3, 4, 8, 0, 7, 6, 5 };
public static int goalState[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
public static int resetValue = 0;
public static int tempHeuristic[] = { resetValue, resetValue, resetValue, resetValue };
public static int totalSolution = 0;
private static int checkIndex(int state[]){
int index = 0;
for (int i = 0; i < 9; i++) {
if (state[i] == 0) {
index = i;
}
}
return index;
}
public static void moveLeft(int state[]) {
int index0 = checkIndex(state);
if (index0 % 3 > 0) {
int temp = state[index0];
state[index0] = state[index0-1];
state[index0-1] = temp;
}
}
public static void moveRight(int state[]) {
int index0 = checkIndex(state);
if (index0 % 3 < 2) {
int temp = state[index0];
state[index0] = state[index0+1];
state[index0+1] = temp;
}
}
public static void moveUp(int state[]) {
int index0 = checkIndex(state);
if (index0 > 2) {
int temp = state[index0];
state[index0] = state[index0-3];
state[index0-3] = temp;
}
}
public static void moveDown(int state[]) {
int index0 = checkIndex(state);
if (index0 < 6) {
int temp = state[index0];
state[index0] = state[index0+3];
state[index0+3] = temp;
}
}
public static int hasSameElement(int array1[], int array2[]) {
int temp = 1;
for (int i = 0; i < 9; i++) {
if (array1[i] != array2[i]) {
temp = 0;
}
}
return temp;
}
public static int sideHeuristic(int side, int currentState[], int goalState[]) {
int temp = 0;
int match = 0;
switch (side) {
case 1:
match = 0;
for (int i = 0; i < 2; i++) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 2:
match = 0;
for (int i = 2; i < 9; i=i+3) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 3:
match = 0;
for (int i = 6; i < 9; i++) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 4:
match = 0;
for (int i = 0; i < 7; i=i+3) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 5:
match = 0;
for (int i = 1; i < 8; i=i+3) {
if (currentState[i] == goalState[i]) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 5;
}
break;
case 6:
match = 0;
for (int i = 3; i < 6; i++) {
if (currentState[i] == goalState[i]) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 5;
}
break;
}
return temp;
}
public static int getCol(int val) {
return ((val/3)+1);
}
public static int getRow(int val) {
return ((val%3)+1);
}
public static int stepCounter(int condition1, int condition2) {
int temp1 = getCol(condition1)-getCol(condition2);
if (temp1 < 0) {
temp1 = (temp1 * -1) * 2;
}
int temp2 = getRow(condition1)-getRow(condition2);
if (temp2 < 0) {
temp2 = (temp2 * -1) * 2;
}
return (((temp1 + temp2) * -1) + 4);
}
public static int manhattanHeuristic(int currentState[], int goalState[]) {
int temp = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (currentState[i] != 0) {
if (currentState[i] == goalState[j]) {
temp = temp + stepCounter(i, j);
}
}
}
}
return temp;
}
public static int heuristicValue(int currentState[], int goalState[]) {
return sideHeuristic(1, currentState, goalState) +
sideHeuristic(2, currentState, goalState) + sideHeuristic(3, currentState, goalState) +
sideHeuristic(4, currentState, goalState) + sideHeuristic(5, currentState, goalState) +
sideHeuristic(6, currentState, goalState) + manhattanHeuristic(currentState, goalState);
}
public static void copyArray(int array1[], int array2[]) {
for (int i = 0; i < 9; i++) {
array2[i] = array1[i];
}
}
public static int getTheBestIndex(int arrayHeuristic[]) {
int temp = 0;
int tempValue = arrayHeuristic[0];
for (int i = 0; i < 4; i++) {
if (arrayHeuristic[i] > tempValue) {
tempValue = arrayHeuristic[i];
temp = i;
}
}
return temp;
}
public static void printState(int state[]) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.print("\n");
}
System.out.print(state[i]);
System.out.print(" ");
}
System.out.print("\n");
}
public static void main(String[] args) {
int currentState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
copyArray(initialState, currentState);
int childState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
while (hasSameElement(currentState, goalState) == 0) {
printState(currentState);
copyArray(currentState, childState);
moveUp(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[0] = 0;
} else {
tempHeuristic[0] = heuristicValue(childState, goalState);
moveDown(childState);
}
moveLeft(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[1] = 0;
} else {
tempHeuristic[1] = heuristicValue(childState, goalState);
moveRight(childState);
}
moveRight(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[2] = 0;
} else {
tempHeuristic[2] = heuristicValue(childState, goalState);
moveLeft(childState);
}
moveDown(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[3] = 0;
} else {
tempHeuristic[3] = heuristicValue(childState, goalState);
moveUp(childState);
}
int tempIndex = getTheBestIndex(tempHeuristic);
switch (tempIndex) {
case 0:
moveUp(currentState);
break;
case 1:
moveLeft(currentState);
break;
case 2:
moveRight(currentState);
break;
case 3:
moveDown(currentState);
break;
}
totalSolution++;
}
printState(currentState);
System.out.print("\nSolusi Total = " + totalSolution + " langkah");
}
}
public class Puzzle {
public static int initialState[] = { 1, 2, 3, 4, 8, 0, 7, 6, 5 };
public static int goalState[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
public static int resetValue = 0;
public static int tempHeuristic[] = { resetValue, resetValue, resetValue, resetValue };
public static int totalSolution = 0;
private static int checkIndex(int state[]){
int index = 0;
for (int i = 0; i < 9; i++) {
if (state[i] == 0) {
index = i;
}
}
return index;
}
public static void moveLeft(int state[]) {
int index0 = checkIndex(state);
if (index0 % 3 > 0) {
int temp = state[index0];
state[index0] = state[index0-1];
state[index0-1] = temp;
}
}
public static void moveRight(int state[]) {
int index0 = checkIndex(state);
if (index0 % 3 < 2) {
int temp = state[index0];
state[index0] = state[index0+1];
state[index0+1] = temp;
}
}
public static void moveUp(int state[]) {
int index0 = checkIndex(state);
if (index0 > 2) {
int temp = state[index0];
state[index0] = state[index0-3];
state[index0-3] = temp;
}
}
public static void moveDown(int state[]) {
int index0 = checkIndex(state);
if (index0 < 6) {
int temp = state[index0];
state[index0] = state[index0+3];
state[index0+3] = temp;
}
}
public static int hasSameElement(int array1[], int array2[]) {
int temp = 1;
for (int i = 0; i < 9; i++) {
if (array1[i] != array2[i]) {
temp = 0;
}
}
return temp;
}
public static int sideHeuristic(int side, int currentState[], int goalState[]) {
int temp = 0;
int match = 0;
switch (side) {
case 1:
match = 0;
for (int i = 0; i < 2; i++) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 2:
match = 0;
for (int i = 2; i < 9; i=i+3) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 3:
match = 0;
for (int i = 6; i < 9; i++) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 4:
match = 0;
for (int i = 0; i < 7; i=i+3) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 5:
match = 0;
for (int i = 1; i < 8; i=i+3) {
if (currentState[i] == goalState[i]) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 5;
}
break;
case 6:
match = 0;
for (int i = 3; i < 6; i++) {
if (currentState[i] == goalState[i]) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 5;
}
break;
}
return temp;
}
public static int getCol(int val) {
return ((val/3)+1);
}
public static int getRow(int val) {
return ((val%3)+1);
}
public static int stepCounter(int condition1, int condition2) {
int temp1 = getCol(condition1)-getCol(condition2);
if (temp1 < 0) {
temp1 = (temp1 * -1) * 2;
}
int temp2 = getRow(condition1)-getRow(condition2);
if (temp2 < 0) {
temp2 = (temp2 * -1) * 2;
}
return (((temp1 + temp2) * -1) + 4);
}
public static int manhattanHeuristic(int currentState[], int goalState[]) {
int temp = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (currentState[i] != 0) {
if (currentState[i] == goalState[j]) {
temp = temp + stepCounter(i, j);
}
}
}
}
return temp;
}
public static int heuristicValue(int currentState[], int goalState[]) {
return sideHeuristic(1, currentState, goalState) +
sideHeuristic(2, currentState, goalState) + sideHeuristic(3, currentState, goalState) +
sideHeuristic(4, currentState, goalState) + sideHeuristic(5, currentState, goalState) +
sideHeuristic(6, currentState, goalState) + manhattanHeuristic(currentState, goalState);
}
public static void copyArray(int array1[], int array2[]) {
for (int i = 0; i < 9; i++) {
array2[i] = array1[i];
}
}
public static int getTheBestIndex(int arrayHeuristic[]) {
int temp = 0;
int tempValue = arrayHeuristic[0];
for (int i = 0; i < 4; i++) {
if (arrayHeuristic[i] > tempValue) {
tempValue = arrayHeuristic[i];
temp = i;
}
}
return temp;
}
public static void printState(int state[]) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.print("\n");
}
System.out.print(state[i]);
System.out.print(" ");
}
System.out.print("\n");
}
public static void main(String[] args) {
int currentState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
copyArray(initialState, currentState);
int childState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
while (hasSameElement(currentState, goalState) == 0) {
printState(currentState);
copyArray(currentState, childState);
moveUp(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[0] = 0;
} else {
tempHeuristic[0] = heuristicValue(childState, goalState);
moveDown(childState);
}
moveLeft(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[1] = 0;
} else {
tempHeuristic[1] = heuristicValue(childState, goalState);
moveRight(childState);
}
moveRight(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[2] = 0;
} else {
tempHeuristic[2] = heuristicValue(childState, goalState);
moveLeft(childState);
}
moveDown(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[3] = 0;
} else {
tempHeuristic[3] = heuristicValue(childState, goalState);
moveUp(childState);
}
int tempIndex = getTheBestIndex(tempHeuristic);
switch (tempIndex) {
case 0:
moveUp(currentState);
break;
case 1:
moveLeft(currentState);
break;
case 2:
moveRight(currentState);
break;
case 3:
moveDown(currentState);
break;
}
totalSolution++;
}
printState(currentState);
System.out.print("\nSolusi Total = " + totalSolution + " langkah");
}
}
public class Puzzle {
public static int initialState[] = { 1, 2, 3, 4, 8, 0, 7, 6, 5 };
public static int goalState[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
public static int resetValue = 0;
public static int tempHeuristic[] = { resetValue, resetValue, resetValue, resetValue };
public static int totalSolution = 0;
private static int checkIndex(int state[]){
int index = 0;
for (int i = 0; i < 9; i++) {
if (state[i] == 0) {
index = i;
}
}
return index;
}
public static void moveLeft(int state[]) {
int index0 = checkIndex(state);
if (index0 % 3 > 0) {
int temp = state[index0];
state[index0] = state[index0-1];
state[index0-1] = temp;
}
}
public static void moveRight(int state[]) {
int index0 = checkIndex(state);
if (index0 % 3 < 2) {
int temp = state[index0];
state[index0] = state[index0+1];
state[index0+1] = temp;
}
}
public static void moveUp(int state[]) {
int index0 = checkIndex(state);
if (index0 > 2) {
int temp = state[index0];
state[index0] = state[index0-3];
state[index0-3] = temp;
}
}
public static void moveDown(int state[]) {
int index0 = checkIndex(state);
if (index0 < 6) {
int temp = state[index0];
state[index0] = state[index0+3];
state[index0+3] = temp;
}
}
public static int hasSameElement(int array1[], int array2[]) {
int temp = 1;
for (int i = 0; i < 9; i++) {
if (array1[i] != array2[i]) {
temp = 0;
}
}
return temp;
}
public static int sideHeuristic(int side, int currentState[], int goalState[]) {
int temp = 0;
int match = 0;
switch (side) {
case 1:
match = 0;
for (int i = 0; i < 2; i++) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 2:
match = 0;
for (int i = 2; i < 9; i=i+3) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 3:
match = 0;
for (int i = 6; i < 9; i++) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 4:
match = 0;
for (int i = 0; i < 7; i=i+3) {
if (currentState[i] == goalState[i] && currentState[i] != 0) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 40;
}
break;
case 5:
match = 0;
for (int i = 1; i < 8; i=i+3) {
if (currentState[i] == goalState[i]) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 5;
}
break;
case 6:
match = 0;
for (int i = 3; i < 6; i++) {
if (currentState[i] == goalState[i]) {
match++;
}
}
if (match == 1) {
temp = temp + 1;
} else if (match == 2) {
temp = temp + 5;
} else if (match == 3) {
temp = temp + 5;
}
break;
}
return temp;
}
public static int getCol(int val) {
return ((val/3)+1);
}
public static int getRow(int val) {
return ((val%3)+1);
}
public static int stepCounter(int condition1, int condition2) {
int temp1 = getCol(condition1)-getCol(condition2);
if (temp1 < 0) {
temp1 = (temp1 * -1) * 2;
}
int temp2 = getRow(condition1)-getRow(condition2);
if (temp2 < 0) {
temp2 = (temp2 * -1) * 2;
}
return (((temp1 + temp2) * -1) + 4);
}
public static int manhattanHeuristic(int currentState[], int goalState[]) {
int temp = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (currentState[i] != 0) {
if (currentState[i] == goalState[j]) {
temp = temp + stepCounter(i, j);
}
}
}
}
return temp;
}
public static int heuristicValue(int currentState[], int goalState[]) {
return sideHeuristic(1, currentState, goalState) +
sideHeuristic(2, currentState, goalState) + sideHeuristic(3, currentState, goalState) +
sideHeuristic(4, currentState, goalState) + sideHeuristic(5, currentState, goalState) +
sideHeuristic(6, currentState, goalState) + manhattanHeuristic(currentState, goalState);
}
public static void copyArray(int array1[], int array2[]) {
for (int i = 0; i < 9; i++) {
array2[i] = array1[i];
}
}
public static int getTheBestIndex(int arrayHeuristic[]) {
int temp = 0;
int tempValue = arrayHeuristic[0];
for (int i = 0; i < 4; i++) {
if (arrayHeuristic[i] > tempValue) {
tempValue = arrayHeuristic[i];
temp = i;
}
}
return temp;
}
public static void printState(int state[]) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.print("\n");
}
System.out.print(state[i]);
System.out.print(" ");
}
System.out.print("\n");
}
public static void main(String[] args) {
int currentState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
copyArray(initialState, currentState);
int childState[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
while (hasSameElement(currentState, goalState) == 0) {
printState(currentState);
copyArray(currentState, childState);
moveUp(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[0] = 0;
} else {
tempHeuristic[0] = heuristicValue(childState, goalState);
moveDown(childState);
}
moveLeft(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[1] = 0;
} else {
tempHeuristic[1] = heuristicValue(childState, goalState);
moveRight(childState);
}
moveRight(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[2] = 0;
} else {
tempHeuristic[2] = heuristicValue(childState, goalState);
moveLeft(childState);
}
moveDown(childState);
if (hasSameElement(childState, currentState) == 1) {
tempHeuristic[3] = 0;
} else {
tempHeuristic[3] = heuristicValue(childState, goalState);
moveUp(childState);
}
int tempIndex = getTheBestIndex(tempHeuristic);
switch (tempIndex) {
case 0:
moveUp(currentState);
break;
case 1:
moveLeft(currentState);
break;
case 2:
moveRight(currentState);
break;
case 3:
moveDown(currentState);
break;
}
totalSolution++;
}
printState(currentState);
System.out.print("\nSolusi Total = " + totalSolution + " langkah");
}
}
Oh ya, hampir lupa… program ini saya buat menggunakan bahasa pemrograman Java. Terserah jika ingin pakai Netbeans, Eclipse atau jCreator untuk IDE-nya. Oke sekian, semoga bisa bermanfaat
Pingback: Contoh Game/Permainan Puzzle 8 Blok (GUI) Menggunakan Java | ayo belajar sama - sama ...
gan itu kan algoritma hil climbing ada masalah sama plateau, ridge sama local maxima itu gimana gan
punya agan kayanya lancar bener
coba buktikan aja ndiri dengan download source nya
kalo ane kaga salah
agan pake backtracking sama openlist & closedlist punyanya Best First Search
CMIIW
gan, bisa minta penjelasan programnya gk?
Thankyou gan, it works! ijin buat project kecerdasan buatan yo
silahkan,,, monggo dimanfaatkan gan
gan pas ane ubah inisialstatenya kenapa loopingnya ga berhenti ya?
gan , algoritma ini bisa digunakan pada pencarian text gak?