8-Puzzle Problem

You could have probably heard of this problem from your child Hood ❤. We will be given a scrambled puzzle in a board and we need to solve the puzzle by moving one piece at a given time. For more information you can head on to the following link to read about 8-puzzle and its bigger brother 15-puzzle problem.

Goal state of Eight Puzzle Problem

After Reading this post you may ask your computer to solve these kinds of puzzle on your Behalf. Before moving further let me also give you some more topics which can be used to solve these kinds of puzzle.

1. Graph Representations
2. Breadth first Search for a Graph
3. Depth first search for a Graph

Let us dive deep into puzzle solving.

Basic Informations

Puzzle solving and similar games are full of permutation and combinations. Probably you would have heard these terms in your mathematics classes. Understanding the probability is the basic key to solve mathematical puzzles and riddles.

For our 8-Puzzle problem the number of possible arrangements (Permutations) is 9! which is equal to 362880. But theres a twist in these permutations. Only Half of the permutations i.e., 181440 is actually solvable. The other permutations are unsolvable. Its time for you to think of the reason why the remaining permutations are unsolvable.

Goal state for 3 puzzle problem

The above puzzle is 3-puzzle problem (younger brother of 8 puzzle problem). The above diagram shows the goal state for 3 puzzle problem. As you may know that there are 6 permutations to arrange the puzzle. Here also only 6/2 i.e., 3 puzzle state are solvable. The reason is called as oddness. One such un solvable state is given below. You can read about that in this link. Let us Try to solve the problem for the remaining Permutations .

One of the three states which cannot be solved

State Representation

We will use a python Class object to represent the current state. The class object will also consist of the Parent (state from which this state is created) , Children (list of states reachable from current state) and the position of empty space (in our case 0).

class Node:
    def __init__(self, p):
        self.children=[]
        self.parent=None
        self.puzzle=p[:]
        self.x=0

Operations for a State

Now let us describe some operation which will be performed in a given state.

1. Testing For Goal

This is the basic function which can be used to check whether the current state is goal state or Not. The Function returns True if the current state is goal state else False for not a goal state. The self tries to means that we are referring the object from which the function is called.

def goaltest(self):
    isGoal=True
    for i in range(len(self.puzzle)):
        if i!=self.puzzle[i]:
            isGoal=False
            return isGoal
    return isGoal

2. Testing whether the puzzle is solvable

This function is used to check whether the given puzzle is solvable. It is determined by oddness rule that I mentioned earlier. If the given puzzle is oddness then it doesn’t have a solution and so the function returns True.

def isunsolvable(self):
    count=0
    for i in range(8):
        for j in range(i,9):
            if (self.puzzle[i] > self.puzzle[j] and              
                self.puzzle[j]!=0):
                count+=1
    if count%2==1:
        return True
    else:
        return False

one of the 181440 unsolvable 8 puzzle state

3. Move Blank spaces

This is the most basic operation of this class. It is used to move the empty space to the left. Before moving left we need to make sure that the move is possible i.e., the blank space is not in the first column. If we can make a move, then we can swap the position of empty space(denoted by self.x). Then we create a new object and add it to the child (list of nodes which can be visited) of current node. We also make the parent of the child node as the current node. Please make sure that you think of the above statement for a second before proceeding further 😆.

def movetoright(self):
    if ((self.x)%col < (col-1)):
        pc=self.puzzle[:]
        pc[self.x],pc[self.x+1]=pc[self.x+1],pc[self.x]
        child=Node(pc)
        self.children.append(child)
        child.parent=self

I have added only one Function of the four possible operations. Similarly you can also write the other functions. Now its time for calling these operations all together in a single step. Thats where the following function comes handy. Expand Node is a function which finds the position of empty space and makes all the possible move for the current node.

def expandNode(self):
    for i in range(len(self.puzzle)):
        if self.puzzle[i]==0:
            self.x=i
    self.movetoright()
    self.movedown()
    self.movetoleft()
    self.moveup()

And Finally the ‘Google it’..

We are in the final step of finding the solution for the given puzzle problem. ‘Google it’ term means that we are going to search. We are going to find the solution by constructing a graph as we reach each state and check whether its the goal state. This process can be done using any Graph search algorithm.

We are going to use Breadth first search which is a basic search which will search by levels (steps to solution) . We are going to use a set to store the visited states and a queue to implement our Breadth first search.

Don’t Be Afraid by the code below. If you take a keen look at it, it is as simple as ‘Hello world’ Program.

def breadthFirstSearch(self,root):
    openlist=[]
    visited=set()
    openlist.append(root)
    visited.add(tuple(root.puzzle))
    while(True):
        currentNode=openlist.pop(0)
        if currentNode.goaltest():
                pathtosolution= search.pathtrace(currentNode)
                print(len(visited))
                return pathtosolution
        currentNode.expandNode()
        for i in range(len(currentNode.children)):
            currentchild=currentNode.children[i]
            if (not (tuple(currentchild.puzzle) in visited)) :
                openlist.append(currentchild)
                visited.add(tuple(currentchild.puzzle))

The reason for using tuple of currentchild.puzzle is that we can only store a immutable value in a set. Thats the reason why we have converted a list into tuple before storing it in set.

Conclusion

Thanks for reading this post till the end. Hope you enjoyed reading the post. You can also have a look at the code from github .