FI2HW02.java (Fifteen game: minimum moves left calculator)

import java.io.*;
import java.util.*;

class FI12HW02

    {

    private static HashSet<SearchNode> nodes; // Configuration nodes set

    // Main method

    public static void main(String[] args) throws Exception
        {
        System.out.println(solve());
        }

    // Solving method (main), builds the structure and calls auxiliary method. Time: Unknown

    public static int solve() throws IOException
        {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        StringTokenizer st = new StringTokenizer(line);
        String nextToken = st.nextToken();
        int[][] puzzle = new int[4][4];
        for(int i = 0; i < 4; i++) // Building the initial matrix
            {
            for(int j = 0; j < 4; j++)
                {
                puzzle[i][j] = Integer.parseInt(nextToken);
                if(st.hasMoreTokens()) nextToken = st.nextToken();
                }
            line = br.readLine();
            if(line != null) st = new StringTokenizer(line);
            if(st.hasMoreTokens()) nextToken = st.nextToken();
            }
        SearchNode first = new SearchNode(puzzle, 0, null); // Initializes first node in sequence to initial configuration
        nodes = new HashSet<SearchNode>(20, 0.5f);
        return minDistance(first); // Calculates the minimum number of moves necessary
        }

    // Calculates minimum moves. Time: Unknown

    private static int minDistance(SearchNode n)
        {
        if(n.isFinal()) return n.moves;
        int[][] up = moveUp(n.config);
        int[][] down = moveDown(n.config);
        int[][] left = moveLeft(n.config);
        int[][] right = moveRight(n.config);
        if((n.previous == null || !n.previous.notMoved(up)) && !n.notMoved(up)) nodes.add(new SearchNode(up, n.moves + 1, n));
        if((n.previous == null || !n.previous.notMoved(down)) && !n.notMoved(down)) nodes.add(new SearchNode(down, n.moves + 1, n));
        if((n.previous == null || !n.previous.notMoved(left)) && !n.notMoved(left)) nodes.add(new SearchNode(left, n.moves + 1, n));
        if((n.previous == null || !n.previous.notMoved(right)) && !n.notMoved(right)) nodes.add(new SearchNode(right, n.moves + 1, n));
        SearchNode next = removeMin();
        return minDistance(next);
        }

    // Takes an input configuration and returns the node containing the following configuration, moving up the first free square. Time: O(n^2)

    private static int[][] moveUp(int[][] m)
        {
        int[][] out = new int[4][4];
        boolean substituted = false;
        int switchedRow = -1;
        int switchedColumn = -1;
        for(int i = 0; i < 4; i++)
            {
            for(int j = 0; j < 4; j++)
                {
                if(m[i][j] == 0 && !substituted && i < 3)
                    {
                    out[i][j] = m[i + 1][j];
                    out[i + 1][j] = 0;
                    substituted = true;
                    switchedRow = i + 1;
                    switchedColumn = j;
                    }
                else
                    {
                    if(i != switchedRow || j != switchedColumn)
                        out[i][j] = m[i][j];
                    }
                }
            }
        return out;
        }

    // Takes an input configuration and returns the node containing the following configuration, moving down the first free square. Time: O(n^2)

    private static int[][] moveDown(int[][] m)
        {
        int[][] out = new int[4][4];
        boolean substituted = false;
        int switchedRow = -1;
        int switchedColumn = -1;
        for(int i = 0; i < 4; i++)
            {
            for(int j = 0; j < 4; j++)
                {
                if(m[i][j] == 0 && !substituted && i > 0)
                    {
                    out[i][j] = m[i - 1][j];
                    out[i - 1][j] = 0;
                    substituted = true;
                    switchedRow = i - 1;
                    switchedColumn = j;
                    }
                else
                    {
                    if(i != switchedRow || j != switchedColumn)
                        out[i][j] = m[i][j];
                    }
                }
            }
        return out;
        }

    // Takes an input configuration and returns the node containing the following configuration, moving left the first free square. Time: O(n^2)

    private static int[][] moveLeft(int[][] m)
        {
        int[][] out = new int[4][4];
        boolean substituted = false;
        int switchedRow = -1;
        int switchedColumn = -1;
        for(int i = 0; i < 4; i++)
            {
            for(int j = 0; j < 4; j++)
                {
                if(m[i][j] == 0 && !substituted && j < 3)
                    {
                    out[i][j] = m[i][j + 1];
                    out[i][j + 1] = 0;
                    substituted = true;
                    switchedRow = i;
                    switchedColumn = j + 1;
                    }
                else
                    {
                    if(i != switchedRow || j != switchedColumn)
                        out[i][j] = m[i][j];
                    }
                }
            }
        return out;
        }

    // Takes an input configuration and returns the node containing the following configuration, moving right the first free square. Time: O(n^2)

    private static int[][] moveRight(int[][] m)
        {
        int[][] out = new int[4][4];
        boolean substituted = false;
        int switchedRow = -1;
        int switchedColumn = -1;
        for(int i = 0; i < 4; i++)
            {
            for(int j = 0; j < 4; j++)
                {
                if(m[i][j] == 0 && !substituted && j > 0)
                    {
                    out[i][j] = m[i][j - 1];
                    out[i][j - 1] = 0;
                    substituted = true;
                    switchedRow = i;
                    switchedColumn = j - 1;
                    }
                else
                    {
                    if(i != switchedRow || j != switchedColumn)
                        out[i][j] = m[i][j];
                    }
                }
            }
        return out;
        }

    // Removes and returns the minimum distance node in the list. Time: O(n)

    private static SearchNode removeMin()
        {
        SearchNode out = null;
        int manhMin = Integer.MAX_VALUE;
        Iterator<SearchNode> it = nodes.iterator();
        while(it.hasNext())
            {
            SearchNode n = (SearchNode)it.next();
            if(n.manhattan + n.moves < manhMin)
                {
                out = n;
                manhMin = n.manhattan + n.moves;
                }
            }
        nodes.remove(out);
        return out;
        }

    // SearchNode class

    static class SearchNode
        {

        int[][] config;
        int moves;
        SearchNode previous;
        int manhattan;

        SearchNode(int[][] config, int moves, SearchNode previous)
            {
            this.config = config;
            this.moves = moves;
            this.previous = previous;
            manhattan = manhattanDistance();
            }

        // Checks if the given configuration is final. Time: O(1)

        boolean isFinal()
            {
            return (config[0][0] == 1 && config[0][1] == 2 && config[0][2] == 3 && config[0][3] == 4 &&
                    config[1][0] == 5 && config[1][1] == 6 && config[1][2] == 7 && config[1][3] == 8 &&
                    config[2][0] == 9 && config[2][1] == 10 && config[2][2] == 11 && config[2][3] == 12 &&
                    config[3][0] == 13 && config[3][1] == 14 && config[3][2] == 15 && config[3][3] == 0);
            }

        // Checks if the given node has the same configuration as the current node. Time: O(1)

        boolean notMoved(int[][] m)
            {
            return (config[0][0] == m[0][0] && config[0][1] == m[0][1] && config[0][2] == m[0][2] && config[0][3] == m[0][3] &&
                    config[1][0] == m[1][0] && config[1][1] == m[1][1] && config[1][2] == m[1][2] && config[1][3] == m[1][3] &&
                    config[2][0] == m[2][0] && config[2][1] == m[2][1] && config[2][2] == m[2][2] && config[2][3] == m[2][3] &&
                    config[3][0] == m[3][0] && config[3][1] == m[3][1] && config[3][2] == m[3][2] && config[3][3] == m[3][3]);
            }

        // Calculates the current node's Manhattan distance. Time: O(n^2)

        int manhattanDistance()
            {
            int manh = 0;
            for(int i = 0; i < 4; i++)
                {
                for(int j = 0; j < 4; j++)
                    {
                    if(config[i][j] == 1)
                        manh = manh + Math.abs(i) + Math.abs(j);
                    else if(config[i][j] == 2)
                        manh = manh + Math.abs(i) + Math.abs(j - 1);
                    else if(config[i][j] == 3)
                        manh = manh + Math.abs(i) + Math.abs(j - 2);
                    else if(config[i][j] == 4)
                        manh = manh + Math.abs(i) + Math.abs(j - 3);
                    else if(config[i][j] == 5)
                        manh = manh + Math.abs(i - 1) + Math.abs(j);
                    else if(config[i][j] == 6)
                        manh = manh + Math.abs(i - 1) + Math.abs(j - 1);
                    else if(config[i][j] == 7)
                        manh = manh + Math.abs(i - 1) + Math.abs(j - 2);
                    else if(config[i][j] == 8)
                        manh = manh + Math.abs(i - 1) + Math.abs(j - 3);
                    else if(config[i][j] == 9)
                        manh = manh + Math.abs(i - 2) + Math.abs(j);
                    else if(config[i][j] == 10)
                        manh = manh + Math.abs(i - 2) + Math.abs(j - 1);
                    else if(config[i][j] == 11)
                        manh = manh + Math.abs(i - 2) + Math.abs(j - 2);
                    else if(config[i][j] == 12)
                        manh = manh + Math.abs(i - 2) + Math.abs(j - 3);
                    else if(config[i][j] == 13)
                        manh = manh + Math.abs(i - 3) + Math.abs(j);
                    else if(config[i][j] == 14)
                        manh = manh + Math.abs(i - 3) + Math.abs(j - 1);
                    else if(config[i][j] == 15)
                        manh = manh + Math.abs(i - 3) + Math.abs(j - 2);
                    else;
                    }
                }
            return manh;
            }

        }

    }