Given an 8-Puzzle which is essentially a jig-saw puzzle with numbers instead of images this program is meant to solve them using a tree. Starting with the initial puzzle state as the root of a tree each possible move is added to the tree as a child and tr

EightPuzzle.java

import java.util.LinkedList;
import java.util.Queue;
import java.util.SortedMap;
import java.util.TreeMap;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class Puzzle {

    public static void main(String[] args) {
        try {
            //Setup file input and output
            FileReader iFile = new FileReader("bin\\input_boards");
            BufferedReader in = new BufferedReader(iFile);
            FileWriter oFile = new FileWriter("bin\\output_sequences");
            BufferedWriter out = new BufferedWriter(oFile);

            //Initialize tree and solution
            String boardValue = "";
            String solution = "";
            TreeNode head = null;
            
            //For each line in input_boards
            while(in.ready()) {
                //Get the boardValue
                boardValue = in.readLine();
                //If the board is solvable and it is actually a board of proper length
                if(isSolvable(boardValue) == true && boardValue.length() == 9) {
                    //Print the board
                    System.out.println(boardValue);
                    //Run garbage collection to clean up after previous boards
                    System.gc();
                    //Create a new tree head
                    head = new TreeNode(boardValue, ' ', null);
                    
                    try {
                        //Start populating the tree
                        populateTree(head);
                        //The tree has been populated now so get the solution
                        solution = getPath(head);
                        //Print the solution backwards since we started from the solution
                        //and followed bread crumbs back to the head of the tree
                        for(int i = solution.length() - 1; i >= 0; i--) {
                            System.out.print(solution.charAt(i));
                            out.write(solution.charAt(i));
                        }
                        System.out.println();
                    out.write("\n");
                    } catch(java.lang.OutOfMemoryError e) {
                        //Oops we ran out of memory, make note of it and
                        //continue to next board
                        out.write("Out of Memory\n");
                        System.out.println("Out of Memory");
                    }
                } else {
                    //The board was unsolvable, make note and continue to next board
                    out.write("No Sequence Found\n");
                }
            }
            
            //Close both files
            out.close();
            in.close();
        } catch (FileNotFoundException e) {
            //Oops we can't find input_boards
            e.printStackTrace();
            System.out.println("Cannot find file.");
        } catch (IOException e) {
            //Oops permissions won't let us read//write from one of the files.
            System.out.println("Cannot read/write from/to file.");
        }
    }

    public static class TreeNode {
        public TreeNode child[] = new TreeNode[4];    //Children nodes, max of 4 moves if in the center of puzzle
        public String boardValue = "";                //Value of the board for current node.
        public char direction;                        //Direction moved to arrive at this node, used for printing path
        public TreeNode parent = null;                //Reference to the parent node for traversing the depth of the tree from bottom up

        public TreeNode(String boardValue, char direction, TreeNode parent) {
            this.boardValue = boardValue;
            this.direction = direction;
            this.parent = parent;
        }
    }

    public static boolean isSolvable(String boardValue) {
        return inversionCount(boardValue) % 2 == 0;
    }

    public static int inversionCount(String boardValue) {
        int inversions = 0;
            
        for(int i = 0; i < boardValue.length(); i++) {
            for(int j = i + 1; j < boardValue.length(); j++) {
                if(Character.getNumericValue(boardValue.charAt(i)) > Character.getNumericValue(boardValue.charAt(j)) && boardValue.charAt(i) != '9') {
                    inversions++;
                }
            }
        }
        
        return inversions;
    }

    public static int[] findBlank(String boardValue) {
        int[] position = new int[2];

        position[0] = boardValue.indexOf('9') / 3;
        position[1] = boardValue.indexOf('9') % 3;

        return position;
    }

    public static String moveBlank(String boardValue, int row, int col) {
        char temp;

        temp = boardValue.charAt(row * 3 + col);
        boardValue = boardValue.replace('9', ' ');
        boardValue = boardValue.replace(temp, '9');
        boardValue = boardValue.replace(' ', temp);
        return boardValue;
    }

    public static boolean checkBounds(int row, int col) {
        if (row < 3 && row >= 0 && col < 3 && col >= 0) {
            return true;
        } else {
            return false;
        }
    }

    public static char getDirection(int row, int col) {
        if (row == 1) {
            return 'D';
        }
        if (row == -1) {
            return 'U';
        }
        if (col == 1) {
            return 'R';
        }
        if (col == -1) {
            return 'L';
        }
        return ' ';
    }

    public static void populateTree(TreeNode currentNode) {
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        
        nodeQueue.add(currentNode);
        
        //Until we've generated all possible moves poll the queue.
        while(nodeQueue.isEmpty() == false) {
            currentNode = nodeQueue.poll();
            
            //If the currentNode is the solution then we're done.
            if(currentNode.boardValue.equals("123456789")) {
                return;
            }
            
            //Generate all possible moves from the current puzzle state.
            possibleMoves(currentNode, nodeQueue);

            //Add all of the moves we just generated to the queue.
            for(TreeNode child : currentNode.child) {
                if(child != null) {
                    nodeQueue.add(child);
                }
            }
        }
    }

    public static void possibleMoves(TreeNode currentNode, Queue<TreeNode> nodeQueue) {
        int[] blankPosition = findBlank(currentNode.boardValue);
        String boardValue;
        int currentMove = 0;
        boolean nodeExists = false;

        //Used to sort new puzzle states in order of how close it is to the solution
        SortedMap<Integer, TreeNode> nodeList = new TreeMap<Integer, TreeNode>();
        
        for (int row = -1; row < 2; row += 1) {
            for (int col = -1; col < 2; col += 1) {
                //We can't move diagonally so if one of row or col is non-zero the other must be 0
                if (Math.abs(row) != Math.abs(col)) {
                    //Make sure that the current position row and col represent is a valid position
                    if (checkBounds(blankPosition[0] + row, blankPosition[1] + col)) {
                        //Move the blank piece
                        boardValue = moveBlank(currentNode.boardValue, blankPosition[0] + row, blankPosition[1] + col);
                        //If we're not at the root of the tree
                        if(currentNode.parent != null) {
                            //Make sure we're not backtracking to the parent node.
                            if(currentNode.parent.boardValue != boardValue) {
                                //Look through the queue of all nodes generated so far
                                //Make sure we're not a duplicate
                                for(TreeNode node : nodeQueue) {
                                    if(node.boardValue.equals(boardValue)) {
                                        nodeExists = true;
                                        break;
                                    }
                                }
                                //If we're not a duplicate add it to nodeList for sorting
                                if(nodeExists == false) {
                                    //System.out.println(nodeQueue.size());
                                    nodeList.put(Integer.parseInt(boardValue), new TreeNode(boardValue, getDirection(row, col), currentNode));
                                }
                                //Reset nodeExists for next queue search
                                nodeExists = false;
                            }
                        } else {
                            //We're the head of the tree so just add all the children
                            nodeList.put(Integer.parseInt(boardValue), new TreeNode(boardValue, getDirection(row, col), currentNode));
                        }
                    }
                }
            }
        }
        
        //Add each child from the nodeList to the child array of the currentNode from smallest boardValue to greatest.
        for(int childIndex : nodeList.keySet()) {
            if(nodeList.get(childIndex) != null) {
                currentNode.child[currentMove] = nodeList.get(childIndex);
                currentMove++;
            }
        }

    }

    public static String getPath(TreeNode head) {
        Queue<TreeNode> nodeList = new LinkedList<TreeNode>();
        String solutionPath = "";
        TreeNode currentNode = null;
    
        nodeList.add(head);
        
        //While the queue isn't empty poll the queue
        while(nodeList.isEmpty() == false) {
            currentNode = nodeList.poll();
            
            //Make sure we don't try to check up null children
            if(currentNode != null) {
                //If we're at the solution then start back-tracking
                if(currentNode.boardValue.equals("123456789")) {
                    //Concatenate the direction of each node to solutionPath until we
                    //reach the head of the tree
                    while(currentNode.parent != null) {
                        solutionPath += currentNode.direction;
                        currentNode = currentNode.parent;
                    }
                    return solutionPath;
                }
                
                //We haven't found the solution yet so add all children to
                //the queue for the next loop
                for(TreeNode child : currentNode.child) {
                    nodeList.add(child);
                }
            }
        }
        //We never found a solution so return nothing.
        return "";
    }
}

EightPuzzle.py

class TreeNode:
    child = []
    boardValue = ""
    direction = ""
    parent = None
    def __init__(self, boardValue, direction, parent):
        self.boardValue = boardValue
        self.direction = direction
        self.parent = parent
    

def isSolvable(boardValue):
    return inversionCount(boardValue) % 2 == 0
    
def inversionCount(boardValue):
    inversions = 0
    for i in xrange(0, len(boardValue)):
        for j in xrange(i, len(boardValue)):
            if int(boardValue[i]) > int(boardValue[j]) and boardValue[i] != '9':
                inversions += 1
    return inversions
    
def findBlank(boardValue):
    blank = boardValue.index('9')
    return (blank / 3, blank % 3)
    
def moveBlank(boardValue, row, col):
    src = row * 3 + col
    dest = boardValue.index('9')
    boardValue = list(boardValue)
    boardValue[src], boardValue[dest] = (boardValue[dest], boardValue[src])
    return ''.join(boardValue)
    
def checkBounds(row, col):
    return row < 3 and row >= 0 and col < 3 and col >= 0
    
def getDirection(row, col):
    dir = {(1,0): 'D', (-1,0): 'U', (0,1): 'R', (0,-1): 'L'}
    if (row,col) not in dir:
        return " "
    else:
        return dir[(row,col)]

def populateTree(currentNode):
    nodeQueue = {}
    nodeQueue[int(currentNode.boardValue)] = currentNode
    while(len(nodeQueue) > 0):
        boardValue, currentNode = nodeQueue.popitem()
        if currentNode.boardValue == "123456789":
            return
        possibleMoves(nodeQueue, currentNode)
        for child in currentNode.child:
            nodeQueue[int(child.boardValue)] = child
        
def possibleMoves(nodeQueue, currentNode):
    blank = findBlank(currentNode.boardValue)
    
    possibleChildren = {}
    
    for row in xrange(-1, 2):
        for col in xrange(-1, 2):
            if abs(row) != abs(col):
                if checkBounds(blank[0] + row, blank[1] + col):
                    boardValue = moveBlank(currentNode.boardValue, blank[0] + row, blank[1] + col)
                    if currentNode.parent != None:
                        if currentNode.parent.boardValue != boardValue:
                            if int(boardValue) not in nodeQueue:
                                possibleChildren[int(boardValue)] = TreeNode(boardValue, getDirection(row, col), currentNode)
                    else:
                        possibleChildren[int(boardValue)] = TreeNode(boardValue, getDirection(row, col), currentNode)
    
    sortedChildren = possibleChildren.keys()
    sortedChildren.sort()
    for key in sortedChildren:
        currentNode.child.append(possibleChildren[key])
        
def getPath(head):
    nodeQueue = []
    nodeQueue.append(head)
    currentNode = None
    solutionPath = ""
    
    while(len(nodeQueue) > 0):
        currentNode = nodeQueue.pop(0)
        if currentNode.boardValue == "123456789":
            while(currentNode.parent != None):
                solutionPath += currentNode.direction
                currentNode = currentNode.parent
            return solutionPath
        else:
            if len(currentNode.child) > 0:
                nodeQueue.extend(currentNode.child)
    return ""

boardValue = "123456798"
if isSolvable(boardValue):
    print boardValue
    head = TreeNode(boardValue, " ", None)
    populateTree(head)
    solution = getPath(head)
    print solution