8 Puzzle: Python Code and C++ Code

 

Problem definition:

An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The object is to move to squares around into different positions and having the numbers displayed in the "goal state".

Given an initial state of 8-puzzle game and a final state of to be reached, find the most cost-effective path to reach the final state from initial state.

Initial state:

5 4 _

6 1 8

7 3 2

Final state:

1 2 3

8 _ 4

7 3 5

 

Solution 8 Puzzle:

 

The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal state.

Rules of solving puzzle

Instead of moving the tiles in the empty space we can visualize moving the empty space in place of the tile. The empty space can only move in four directions (Movement of empty space)

1.      Up 

2.      Down 

3.      Right or

4.      Left

The empty space cannot move diagonally and can take only one step at a time. All possible move of an Empty tile

o- Position total possible moves are (2), x - position total possible moves are (3) and 

#-position total possible moves are (4)

Let's solve the problem without Heuristic Search that is Uninformed Search or Blind Search ( Breadth First Search and Depth First Search)

If we solve this problem with depth first search, then it will go to depth instead of exploring layer wise nodes.

Time complexity: In worst case time complexity in BFS is O(b^d) know as order of b raise to power d.  In this particular case it is (3^20). 

b-branch factor

d-depth factor

Let's solve the problem with Heuristic Search that is Informed Search (A* , Best First Search (Greedy Search))

To solve the problem with Heuristic search or informed search we have to calculate Heuristic values of each node to calculate cost function. (f=g+h)

See the initial state and goal state carefully all values except (4,5 and 8) are at their respective places. so, the heuristic value for first node is 3.(Three values are misplaced to reach the goal). And let's take actual cost (g) according to depth.

Because of quick solution time complexity is less than that of Uninformed search but optimal solution not possible. 

 

Python Code:

 

import random

import math

 

_goal_state = [[1,2,3],

               [8,0,4],

               [7,6,5]]

 

def index(item, seq):

    """Helper function that returns -1 for non-found index value of a seq"""

    if item in seq:

        return seq.index(item)

    else:

        return -1

 

class EightPuzzle:

 

    def __init__(self):

        # heuristic value

        self._hval = 0

        # search depth of current instance

        self._depth = 0

        # parent node in search path

        self._parent = None

        self.adj_matrix = []

        for i in range(3):

            self.adj_matrix.append(_goal_state[i][:])

 

    def __eq__(self, other):

        if self.__class__ != other.__class__:

            return False

        else:

            return self.adj_matrix == other.adj_matrix

 

    def __str__(self):

        res = ''

        for row in range(3):

            res += ' '.join(map(str, self.adj_matrix[row]))

            res += '\r\n'

        return res

 

    def _clone(self):

        p = EightPuzzle()

        for i in range(3):

            p.adj_matrix[i] = self.adj_matrix[i][:]

        return p

 

    def _get_legal_moves(self):

        """Returns list of tuples with which the free space may

        be swapped"""

        # get row and column of the empty piece

        row, col = self.find(0)

        free = []

       

        # find which pieces can move there

        if row > 0:

            free.append((row - 1, col))

        if col > 0:

            free.append((row, col - 1))

        if row < 2:

            free.append((row + 1, col))

        if col < 2:

            free.append((row, col + 1))

 

        return free

 

    def _generate_moves(self):

        free = self._get_legal_moves()

        zero = self.find(0)

 

        def swap_and_clone(a, b):

            p = self._clone()

            p.swap(a,b)

            p._depth = self._depth + 1

            p._parent = self

            return p

 

        return map(lambda pair: swap_and_clone(zero, pair), free)

 

    def _generate_solution_path(self, path):

        if self._parent == None:

            return path

        else:

            path.append(self)

            return self._parent._generate_solution_path(path)

 

    def solve(self, h):

        """Performs A* search for goal state.

        h(puzzle) - heuristic function, returns an integer

        """

        def is_solved(puzzle):

            return puzzle.adj_matrix == _goal_state

 

        openl = [self]

        closedl = []

        move_count = 0

        while len(openl) > 0:

            x = openl.pop(0)

            move_count += 1

            if (is_solved(x)):

                if len(closedl) > 0:

                    return x._generate_solution_path([]), move_count

                else:

                    return [x]

 

            succ = x._generate_moves()

            idx_open = idx_closed = -1

            for move in succ:

                # have we already seen this node?

                idx_open = index(move, openl)

                idx_closed = index(move, closedl)

                hval = h(move)

                fval = hval + move._depth

 

                if idx_closed == -1 and idx_open == -1:

                    move._hval = hval

                    openl.append(move)

                elif idx_open > -1:

                    copy = openl[idx_open]

                    if fval < copy._hval + copy._depth:

                        # copy move's values over existing

                        copy._hval = hval

                        copy._parent = move._parent

                        copy._depth = move._depth

                elif idx_closed > -1:

                    copy = closedl[idx_closed]

                    if fval < copy._hval + copy._depth:

                        move._hval = hval

                        closedl.remove(copy)

                        openl.append(move)

 

            closedl.append(x)

            openl = sorted(openl, key=lambda p: p._hval + p._depth)

 

        # if finished state not found, return failure

        return [], 0

 

    def shuffle(self, step_count):

        for i in range(step_count):

            row, col = self.find(0)

            free = self._get_legal_moves()

            target = random.choice(free)

            self.swap((row, col), target)           

            row, col = target

 

    def find(self, value):

        """returns the row, col coordinates of the specified value

           in the graph"""

        if value < 0 or value > 8:

            raise Exception("value out of range")

 

        for row in range(3):

            for col in range(3):

                if self.adj_matrix[row][col] == value:

                    return row, col

   

    def peek(self, row, col):

        """returns the value at the specified row and column"""

        return self.adj_matrix[row][col]

 

    def poke(self, row, col, value):

        """sets the value at the specified row and column"""

        self.adj_matrix[row][col] = value

 

    def swap(self, pos_a, pos_b):

        """swaps values at the specified coordinates"""

        temp = self.peek(*pos_a)

        self.poke(pos_a[0], pos_a[1], self.peek(*pos_b))

        self.poke(pos_b[0], pos_b[1], temp)

 

 

def heur(puzzle, item_total_calc, total_calc):

    """

    Heuristic template that provides the current and target position for each number and the

    total function.

   

    Parameters:

    puzzle - the puzzle

    item_total_calc - takes 4 parameters: current row, target row, current col, target col.

    Returns int.

    total_calc - takes 1 parameter, the sum of item_total_calc over all entries, and returns int.

    This is the value of the heuristic function

    """

    t = 0

    for row in range(3):

        for col in range(3):

            val = puzzle.peek(row, col) - 1

            target_col = val % 3

            target_row = val / 3

 

            # account for 0 as blank

            if target_row < 0:

                target_row = 2

 

            t += item_total_calc(row, target_row, col, target_col)

 

    return total_calc(t)

 

#some heuristic functions, the best being the standard manhattan distance in this case, as it comes

#closest to maximizing the estimated distance while still being admissible.

 

def h_manhattan(puzzle):

    return heur(puzzle,

                lambda r, tr, c, tc: abs(tr - r) + abs(tc - c),

                lambda t : t)

 

def h_manhattan_lsq(puzzle):

    return heur(puzzle,

                lambda r, tr, c, tc: (abs(tr - r) + abs(tc - c))**2,

                lambda t: math.sqrt(t))

 

def h_linear(puzzle):

    return heur(puzzle,

                lambda r, tr, c, tc: math.sqrt(math.sqrt((tr - r)**2 + (tc - c)**2)),

                lambda t: t)

 

def h_linear_lsq(puzzle):

    return heur(puzzle,

                lambda r, tr, c, tc: (tr - r)**2 + (tc - c)**2,

                lambda t: math.sqrt(t))

 

def h_default(puzzle):

    return 0

 

def main():

    p = EightPuzzle()

    p.shuffle(20)

    print (p)

 

    path, count = p.solve(h_manhattan)

    path.reverse()

    for i in path:

        print (i)

 

    print ("Solved with Manhattan distance exploring", count, "states")

    path, count = p.solve(h_manhattan_lsq)

    print ("Solved with Manhattan least squares exploring", count, "states")

    path, count = p.solve(h_linear)

    print ("Solved with linear distance exploring", count, "states")

    path, count = p.solve(h_linear_lsq)

    print ("Solved with linear least squares exploring", count, "states")

#    path, count = p.solve(heur_default)

#    print "Solved with BFS-equivalent in", count, "moves"

 

if __name__ == "__main__":

    main()

 

 

Python Output:

 

  

C++ Code:

 

#include <bits/stdc++.h>

using namespace std;

#define N 3

 

// state space tree nodes

struct Node

{

         // stores the parent node of the current node

         // helps in tracing path when the answer is found

         Node* parent;

 

         // stores matrix

         int mat[N][N];

 

         // stores blank tile coordinates

         int x, y;

 

         // stores the number of misplaced tiles

         int cost;

 

         // stores the number of moves so far

         int level;

};

 

// Function to print N x N matrix

int printMatrix(int mat[N][N])

{

         for (int i = 0; i < N; i++)

         {

                 for (int j = 0; j < N; j++)

                          printf("%d ", mat[i][j]);

                 printf("\n");

         }

}

 

// Function to allocate a new node

Node* newNode(int mat[N][N], int x, int y, int newX,

                          int newY, int level, Node* parent)

{

         Node* node = new Node;

 

         // set pointer for path to root

         node->parent = parent;

 

         // copy data from parent node to current node

         memcpy(node->mat, mat, sizeof node->mat);

 

         // move tile by 1 position

         swap(node->mat[x][y], node->mat[newX][newY]);

 

         // set number of misplaced tiles

         node->cost = INT_MAX;

 

         // set number of moves so far

         node->level = level;

 

         // update new blank tile cordinates

         node->x = newX;

         node->y = newY;

 

         return node;

}

 

// bottom, left, top, right

int row[] = { 1, 0, -1, 0 };

int col[] = { 0, -1, 0, 1 };

 

// Function to calculate the number of misplaced tiles

// ie. number of non-blank tiles not in their goal position

int calculateCost(int initial[N][N], int final[N][N])

{

         int count = 0;

         for (int i = 0; i < N; i++)

         for (int j = 0; j < N; j++)

                 if (initial[i][j] && initial[i][j] != final[i][j])

                 count++;

         return count;

}

 

// Function to check if (x, y) is a valid matrix cordinate

int isSafe(int x, int y)

{

         return (x >= 0 && x < N && y >= 0 && y < N);

}

 

// print path from root node to destination node

void printPath(Node* root)

{

         if (root == NULL)

                 return;

         printPath(root->parent);

         printMatrix(root->mat);

 

         printf("\n");

}

 

// Comparison object to be used to order the heap

struct comp

{

         bool operator()(const Node* lhs, const Node* rhs) const

         {

                 return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);

         }

};

 

// Function to solve N*N - 1 puzzle algorithm using

// Branch and Bound. x and y are blank tile coordinates

// in initial state

void solve(int initial[N][N], int x, int y,

                 int final[N][N])

{

         // Create a priority queue to store live nodes of

         // search tree;

         priority_queue<Node*, std::vector<Node*>, comp> pq;

 

         // create a root node and calculate its cost

         Node* root = newNode(initial, x, y, x, y, 0, NULL);

         root->cost = calculateCost(initial, final);

 

         // Add root to list of live nodes;

         pq.push(root);

 

         // Finds a live node with least cost,

         // add its childrens to list of live nodes and

         // finally deletes it from the list.

         while (!pq.empty())

         {

                 // Find a live node with least estimated cost

                 Node* min = pq.top();

 

                 // The found node is deleted from the list of

                 // live nodes

                 pq.pop();

 

                 // if min is an answer node

                 if (min->cost == 0)

                 {

                          // print the path from root to destination;

                          printPath(min);

                          return;

                 }

 

                 // do for each child of min

                 // max 4 children for a node

                 for (int i = 0; i < 4; i++)

                 {

                          if (isSafe(min->x + row[i], min->y + col[i]))

                          {

                                   // create a child node and calculate

                                   // its cost

                                   Node* child = newNode(min->mat, min->x,

                                                             min->y, min->x + row[i],

                                                             min->y + col[i],

                                                             min->level + 1, min);

                                   child->cost = calculateCost(child->mat, final);

 

                                   // Add child to list of live nodes

                                   pq.push(child);

                          }

                 }

         }

}

 

// Driver code

int main()

{

         // Initial configuration

         // Value 0 is used for empty space

         int initial[N][N] =

         {

                 {1, 2, 3},

                 {5, 6, 0},

                 {7, 8, 4}

         };

 

         // Solvable Final configuration

         // Value 0 is used for empty space

         int final[N][N] =

         {

                 {1, 2, 3},

                 {8, 0, 4},

                 {7, 6, 5}

         };

 

         // Blank tile coordinates in initial

         // configuration

         int x = 1, y = 2;

 

         solve(initial, x, y, final);

 

         return 0;

}