8 puzzle with a algorithm

[kazkuzzer007]

excuse me, I want to make an application 8 puzzle with a algorithm such as the following video
http://www.yourepeat.com/watch/?v=LkRuKHwElbk
is there anything that can teach me?

[Taywin]

Well, you need to learn...

1)A* search algorithm
2)Javascript

That's it. First you need to understand how to do the search to get the result using A* algorithm. Then you write script in Javascript to follow the A* search step-by-step. ;)

[kazkuzzer007]

ok, I was already familiar with the algorithm, and now I am confused implementing the program

[Taywin]

To apply the algorithm to the game, you need to think that a move of each tile is a step in the search tree. You need to keep all step (and arbitrary distance value) you have gone so far in the memory. If the next step is causing a cycle in the tree, you stop and prone the tree. Keep going each step until you hit the goal. If you can't hit the goal, it is impossible to solve. ;)

[kazkuzzer007]

Do you have an example?

[Taywin]

Hmm... Nope. It is simply a though of how to do it. But for example, if you want to apply A* algorithm to the game, you need to construct a path tree of the game. First, create the stage of the game as a node of the tree. Then move one tile and check if it creates a cycle. If not, add it to the tree (starting A* search) as a node and apply weight to it. If it did create a cycle, stop and retrack to where you have not explored yet. Then keep going until you either solve it or no solution.

Speaking of weight, you need to define that yourself...

[kazkuzzer007]

ok thank you
I have not mastered javascript, but I could php, so I made it with php with code like this:

<?php  
    $GoalState = array(0,0,0,0,0,0,0,0,0);
    $CurrentState = array(0,0,0,0,0,0,0,0,0);
    $ChildState = array(0,0,0,0,0,0,0,0,0);
    function GetGoalState($initialstate, $goalstate){
        $total = 0;
        $GoalStateGanjil = array(1,2,3,8,0,4,7,6,5);
        $GoalStateGenap = array(0,1,2,3,4,5,6,7,8);
        for($i=0; $i<8; $i++){
            for($j=$i+1; $j<9; $j++){
                if($initialstate[$j] < $initialstate[$i] && $initialstate[$j] != 0)
                    $total = $total + 1;    
            }
        }
        if($total % 2 == 1){
            for($i=0; $i<9; $i++){
                $goalstate[$i] = $GoalStateGanjil[$i];
            }
        }else{
            for($i=0; $i<9; $i++){
                $goalstate[$i] = $GoalStateGenap[$i];
            }
        }
    }
    function PrintState($state){
        for($i=0; $i<9; $i++){
            if($i % 3 == 0)
                echo "<br>";
            echo " ".$state[$i];
        }
        echo "<br>";
    }
    function CopyState($from, $to){
        for($i=0; $i<9; $i++){
            $to[$i] = $from[$i];
        }
    }
    function SameState($currentstate, $goalstate){
        for($i=0; $i<9; $i++){
            if($currentstate[$i] != $goalstate[$i]){
                return false;
                break;
            }
        }
        return true;
    }
    function GetKotakKosong($state){
        $index = 0;
        for($i=0; $i<9; $i++){
            if($state[$i] == 0)
                $index = $i;
        }
        return $index;
    }
    function MoveUp($state){
        $index = GetKotakKosong(array(2,8,3,1,6,4,7,5,0));
        if($index > 2){     
            $state[$index] = $state[$index-3];
            $state[$index-3] = $state[$index-3] - $state[$index];
        }
    }
    function MoveDown($state){
        $index = GetKotakKosong(array(2,8,3,1,6,4,7,5,0));
        if($index < 6){
            $state[$index] = $state[$index+3];
            $state[$index+3] = $state[$index+3] - $state[$index];
        }
    }
    function MoveLeft($state){
        $index = GetKotakKosong(array(2,8,3,1,6,4,7,5,0));
        if($index % 3 > 0){
            $state[$index] = $state[$index-1];
            $state[$index-1] = $state[$index-1] - $state[$index];
        }
    }
    function MoveRight($state){
        $index = GetKotakKosong(array(2,8,3,1,6,4,7,5,0));
        if($index % 3 < 2){
            $state[$index] = $state[$index+1];
            $state[$index+1] = $state[$index+1] - $state[$index];
        }
    }
    function MatchTile($currentstate, $goalstate){
        $match = 0;
        for($i=0; $i<9; $i++){
            if($currentstate[$i] != 0 && $currentstate[$i] == $goalstate[$i])
                $match++;
        }
        return $match;
    }
    function GetTheBestMove($heuristic){
        $index = 0;
        $max = $heuristic[0];
        for($i=0; $i<4; $i++){
            if($heuristic[i] > $max){
                $max = $heuristic[$i];
                $index = $i;
            }
        }
        return $index;
    }
    $InitialState = array(2,8,3,1,6,4,7,5,0);
    GetGoalState($InitialState,$GoalState);
    echo "<br>Init State<br>----------";       
    PrintState($InitialState);
    echo "<br>Goal State<br>----------";
    PrintState($GoalState);
    echo "<br>Searching<br>---------";            
    CopyState($InitialState,$CurrentState);
    $level = 0;
    while(!SameState($CurrentState,$GoalState)){
        PrintState($CurrentState);
        $ChildState = array(2,8,3,1,6,4,7,0,5);
        $Heuristic = array(0,0,0,0);
        $level++;
        MoveUp(array(2,8,3,1,6,4,7,5,0));
        if(!SameState($ChildState,$CurrentState)){
            $Heuristic[0] = MatchTile($ChildState,$GoalState) + $level;
            MoveDown($ChildState);
        }
        MoveDown(array(2,8,3,1,6,4,7,5,0));
        if(!SameState($ChildState,$CurrentState)){
            $Heuristic[1] = MatchTile($ChildState,$GoalState) + $level;
            MoveUp($ChildState);
        }
        MoveLeft(array(2,8,3,1,6,4,7,5,0));
        if(!SameState($ChildState,$CurrentState)){
            $Heuristic[2] = MatchTile($ChildState,$GoalState) + $level;
            MoveRight($ChildState);
        }
        MoveRight(array(2,8,3,1,6,4,7,5,0));
        if(!SameState($ChildState,$CurrentState)){
            $Heuristic[3] = MatchTile($ChildState,$GoalState) + $level;
            MoveLeft($ChildState);
        }
        switch(GetTheBestMove($Heuristic)){
            case 0 : MoveUp($CurrentState); break;
            case 1 : MoveDown($CurrentState); break;
            case 2 : MoveLeft($CurrentState); break;
            case 3 : MoveRight($CurrentState); break;
        }       
    }
    echo "\n Solved with %i steps, %f seconds...".$level;

The code I created from c ++ code like this:

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int GoalState[9], CurrentState[9], ChildState[9] = {0,0,0,0,0,0,0,0,0};
void GetGoalState(int initialstate[], int goalstate[]){
    int i, j, total = 0;
    int GoalStateGanjil[] = {1,2,3,8,0,4,7,6,5};
    int GoalStateGenap[] = {0,1,2,3,4,5,6,7,8};
    for(i=0; i<8; i++){
        for(j=i+1; j<9; j++){
            if(initialstate[j] < initialstate[i] && initialstate[j] != 0)
                total = total + 1;  
        }
    }
    if(total % 2 == 1){
        for(i=0; i<9; i++){
            goalstate[i] = GoalStateGanjil[i];
        }
    }else{
        for(i=0; i<9; i++){
            goalstate[i] = GoalStateGenap[i];
        }
    }
}
void PrintState(int state[]){
    for(int i=0; i<9; i++){
        if(i % 3 == 0)
            cout << endl;
        cout << " " << state[i];
    }
    cout << endl;
}
void CopyState(int from[], int to[]){
    for(int i=0; i<9; i++){
        to[i] = from[i];
    }
}
bool SameState(int currentstate[], int goalstate[]){
    for(int i=0; i<9; i++){
        if(currentstate[i] != goalstate[i]){
            return false;
            break;
        }
    }
    return true;
}
int GetKotakKosong(int state[]){
    int index = 0;
    for(int i=0; i<9; i++){
        if(state[i] == 0)
            index = i;
    }
    return index;
}
void MoveUp(int state[]){
    int index = GetKotakKosong(state);
    if(index > 2){      
        state[index] = state[index-3];
        state[index-3] = state[index-3] - state[index];
    }
}
void MoveDown(int state[]){
    int index = GetKotakKosong(state);
    if(index < 6){
        state[index] = state[index+3];
        state[index+3] = state[index+3] - state[index];
    }
}
void MoveLeft(int state[]){
    int index = GetKotakKosong(state);
    if(index % 3 > 0){
        state[index] = state[index-1];
        state[index-1] = state[index-1] - state[index];
    }
}
void MoveRight(int state[]){
    int index = GetKotakKosong(state);
    if(index % 3 < 2){
        state[index] = state[index+1];
        state[index+1] = state[index+1] - state[index];
    }
}
int MatchTile(int currentstate[], int goalstate[]){
    int match = 0;
    for(int i=0; i<9; i++){
        if(currentstate[i] != 0 && currentstate[i] == goalstate[i])
            match++;
    }
    return match;
}
int GetTheBestMove(int heuristic[]){
    int index = 0;
    int max = heuristic[0];
    for(int i=0; i<4; i++){
        if(heuristic[i] > max){
            max = heuristic[i];
            index = i;
        }
    }
    return index;
}
int main(int argc, char** argv) {
    int InitialState[] = {2,8,3,1,6,4,7,0,5};
    GetGoalState(InitialState,GoalState);
    cout << "\nInit State\n" << "----------";        
    PrintState(InitialState);
    cout << "\nGoal State\n" << "----------";
    PrintState(GoalState);
    cout << "\nSearching\n" << "---------";         
    CopyState(InitialState,CurrentState);
    int level = 0;
    clock_t t;
    t = clock();
    while(!SameState(CurrentState,GoalState)){
        PrintState(CurrentState);
        CopyState(CurrentState,ChildState);
        int Heuristic[] = {0,0,0,0};
        level++;
        MoveUp(ChildState);
        if(!SameState(ChildState,CurrentState)){
            Heuristic[0] = MatchTile(ChildState,GoalState) + level;
            MoveDown(ChildState);
        }
        MoveDown(ChildState);
        if(!SameState(ChildState,CurrentState)){
            Heuristic[1] = MatchTile(ChildState,GoalState) + level;
            MoveUp(ChildState);
        }
        MoveLeft(ChildState);
        if(!SameState(ChildState,CurrentState)){
            Heuristic[2] = MatchTile(ChildState,GoalState) + level;
            MoveRight(ChildState);
        }
        MoveRight(ChildState);
        if(!SameState(ChildState,CurrentState)){
            Heuristic[3] = MatchTile(ChildState,GoalState) + level;
            MoveLeft(ChildState);
        }
        switch(GetTheBestMove(Heuristic)){
            case 0 : MoveUp(CurrentState); break;
            case 1 : MoveDown(CurrentState); break;
            case 2 : MoveLeft(CurrentState); break;
            case 3 : MoveRight(CurrentState); break;
        }       
    }
    PrintState(CurrentState);
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC;
    printf("\n Solved with %i steps, %f seconds...",level,time_taken);
    getchar();
    return 0;
}

but, php program that I created was an error. I hope you can help me

[Taywin]

Below is the direct translation from your c++. I changed certain variable name for less confusion.

The problem I am seeing is in all of the move functions. Please make sure how you assign values in an array. If you want to swap or keep certain value, assign the value in a temporary variable before overwritten it with another value.

Also, each of the function below does not check for type error. If the argument of a function is not the expected type, it will throw an error.

Another thing is that I limit the loop up to 1000 (level<1000) in the while loop just in case if you ever run into an infinite loop.

<!DOCTYPE HTML>
<html>
<head>
<script type="text/javascript">
// declare global variables
var goalState = new Array(9);
var currentState = new Array(9);
var childState = [0, 0, 0, 0, 0, 0, 0, 0, 0];

function getGoalState(initState) {  // no need to pass in global
  var i, j, total=0;
  var goalStateGanjil = [1, 2, 3, 8, 0, 4, 7, 6, 5];
  var goalStateGenap = [0, 1, 2, 3, 4, 5, 6, 7, 8];
  for (i=0; i<8; i++) {
    for (j=i+1; j<9; j++) {
      if(initState[j]<initState[i] && initState[j]!=0) {
        total += 1;
      }
    }
  }  // end for-loop i
  if (total%2 == 1) {
    for (i=0; i<9; i++) {
      goalState[i] = goalStateGanjil[i];
    }
  }
  else {
    for (i=0; i<9; i++) {
      goalState[i] = goalStateGenap[i];
    }
  }
}  // getGoalState

function printState(state) {  // modified
  console.log("["+state.join(", ")+"]");
}  // printState

function copyState(from, to) {
  for (var i=0; i<9; i++) {
    to[i] = from[i];
  }
}  // copyState

function sameState(cState, gState) {
  for (var i=0; i<9; i++) {
    if (cState[i] != gState[i]) {
      return false;
      // no need a break - unreachable statement
    }
  }
  return true;
}  // sameState

function getKotakKosong(state) {
  var index = 0;
  for (var i=0; i<9; i++) {
    if (state[i]==0) {
      index = i;
    }
  }
  return index;
}  // getKotakKosong

function moveUp(state) {
  var index = getKotakKosong(state);
  if (index>2) {
    state[index] = state[index-3];
    // the line below will ALWAYS be 0, are you sure????
    // don't you want to save previous value first????
    state[index-3] = state[index-3] - state[index];
  }
}  // moveUp

function moveDown(state) {
  var index = getKotakKosong(state);
  if (index<6) {
    state[index] = state[index+3];
    // the line below will ALWAYS be 0, are you sure????
    // don't you want to save previous value first????
    state[index+3] = state[index+3] - state[index];
  }
} // moveDown

function moveLeft(state) {
  var index = getKotakKosong(state);
  if (index%3 > 0) {
    state[index] = state[index-1];
    // the line below will ALWAYS be 0, are you sure????
    // don't you want to save previous value first????
    state[index-1] = state[index-1] - state[index];
  }
} // moveLeft

function moveRight(state) {
  var index = getKotakKosong(state);
  if (index%3 < 2) {
    state[index] = state[index+1];
    // the line below will ALWAYS be 0, are you sure????
    // don't you want to save previous value first????
    state[index+1] = state[index+1] - state[index];
  }
}  // moveRight

function matchTile(cState, gState) {
  var match = 0;
  for (var i=0; i<9; i++) {
    if (cState[i]!=0 && cState[i]==gState[i]) {
      match += 1;
    }
  }
  return match;
}  // matchTile

function getTheBestMove(h) {
  var index = 0;
  var max = h[0];
  for (var i=0; i<4; i++) {
    if (h[i]>max) {
      max = h[i];
      index = i;
    }
  }
  return index;
}  // getTheBestMove

</script>
</head>

<body>
  <script type="text/javascript">
  // imitate main() function in c++
  var initialState = [2, 8, 3, 1, 6, 4, 7, 0, 5];
  getGoalState(initialState);
  console.log("Init State\n--------");
  printState(initialState);
  console.log("Goal State\n--------");
  printState(goalState);
  console.log("Searching\n--------");
  copyState(initialState, currentState);
  var level = 0;
  var t = Date.now()
  while (!sameState(currentState, goalState) && level<1000) {
    printState(currentState);
    copyState(currentState, childState);
    var heuristic = [0, 0, 0, 0];
    level += 1;
    moveUp(childState);
    if (!sameState(childState, currentState)) {
      heuristic[0] = matchTile(childState, goalState) + level;
      moveDown(childState);
    }
    moveDown(childState);
    if (!sameState(childState, currentState)) {
      heuristic[1] = matchTile(childState, goalState) + level;
      moveUp(childState);
    }
    moveLeft(childState);
    if (!sameState(childState, currentState)) {
      heuristic[2] = matchTile(childState, goalState) + level;
      moveRight(childState);
    }
    moveRight(childState);
    if (!sameState(childState, currentState)) {
      heuristic[3] = matchTile(childState, goalState) + level;
      moveLeft(childState);
    }
    switch(getTheBestMove(heuristic)) {
      case 0 : moveUp(currentState); break;
      case 1 : moveDown(currentState); break;
      case 2 : moveLeft(currentState); break;
      case 3 : moveRight(currentState); break;
    }
  }  // while(!sameState)
  printState(currentState);
  t = Date.now() - t;
  console.log("Sovled with "+level+" steps, "+(t/1000)+" seconds...");
 </script>
</body>
</html>

[kazkuzzer007]

thanks before, I've tried the code you provided but no output is displayed

[Taywin]

The output is in the "console" which is not the same as other language console. In each browser, there should be JavaScript Log or something. If you want the output to be display on the page, add the potion inside the <body> tag, add function displayOnDisplay() inside the <head> tag, and also update the line with console.log(...) with a call to function displayOnDisplay() below...

<body>
  ...
  <div id="display">
  </div>
</body>

// function
function displayOnDisplay(elId, msg) {
  var el = document.getElementById(elId);
  if (el) {
    el.innerHTML = el.innerHTML+"<br>"+msg
  }
}

// replace console.log() as...
displayOnDisplay("display", AndWhateverMessageInTheCode);

PS: You should choose a browser to work on Javascript. I would recommend either Firefox or Chrome. Firefox has add-on named "Firebug" which is a great tool to debug JavaScript. Chrome has its built-in functionality. Internet Explorer has its own version of built-in debugger but it is more difficult to work with (plus its error message sometimes misleads you!).

[kazkuzzer007]

I do not understand your point, because I am too new to javascript

[Taywin]

OK, I will give you an example...

In C++, console means the command window (in Windows) or terminal (in Linux or Mac). When you write out to console (cout), the content will be displaed on the console/terminal window.

In Javascript, console means javascript console which is similar to a log window. Usually, all browsers today have it, but you have to open it from the browser menu or it will remain hidden. The way I suggested is that instead of display the content on console, you would display the content on the web page which is where the Javascript resides. In order to do so, you either create a new HTML element and add to the page, or you create an HTML element (preferrable a 'div' tag) in the page before hand and add content to the element.

So what I said in my previous post is that you need to add an element 'div' to your current page display and gives its id as display (<div id="display"></div>), but the element has no content inside (and will be added later once the script runs). Add a new function displayOnDisplay(elId, msg), as I showed you, inside the existing script tag you already have. And then change all the console.log(...) to displayOnDisplay("display", WhateverMessageYouNeedToDisplay). Don't forget to change all \n to <br> because the new line character is not displayed as new line in the web page display but <br> is. For example, console.log("Init State\n------"); to displayOnDisplay("display", "Init State<br>------");. Hope this help.

[kazkuzzer007]

thank you very much, it is very helpful