Source code in the csharp programming language

using System;
using System.Collections.Generic;
using System.Linq;

public class Puzzle15Solver
{
    public static void Main(string[] args)
    {
        List<int> start = new List<int> { 15, 14, 1, 6, 9, 11, 4, 12, 0, 10, 7, 3, 13, 8, 5, 2 };
        int zeroIndex = 8;
        Puzzle initial = new Puzzle(start, new List<string>(), zeroIndex, 0);
        Queue<Puzzle> openSet = new PriorityQueue<Puzzle>((p1, p2) => p1.Heuristic().CompareTo(p2.Heuristic()));
        HashSet<Puzzle> closedSet = new HashSet<Puzzle>();
        openSet.Enqueue(initial);
        Console.WriteLine("Solving the 15 puzzle:");
        initial.Display();

        while (solution == null)
        {
            Search(openSet, closedSet);
        }

        Console.WriteLine(string.Join("", solution.Moves));
        Console.WriteLine("Number of steps: " + solution.Moves.Count);
        Console.WriteLine("Number of puzzle states checked: " + closedSet.Count);
    }

    private static void Search(Queue<Puzzle> openSet, HashSet<Puzzle> closedSet)
    {
        Puzzle current = openSet.Dequeue();
        closedSet.Add(current);
        int zeroIndex = current.ZeroIndex;
        int row = zeroIndex / 4;
        int column = zeroIndex % 4;

        if (column > 0)
        {
            Puzzle nextPuzzle = current.Clone();
            nextPuzzle.MakeMove(Move.Left);
            EvaluateNextPuzzle(openSet, closedSet, nextPuzzle);
        }
        if (column < 3)
        {
            Puzzle nextPuzzle = current.Clone();
            nextPuzzle.MakeMove(Move.Right);
            EvaluateNextPuzzle(openSet, closedSet, nextPuzzle);
        }
        if (row > 0)
        {
            Puzzle nextPuzzle = current.Clone();
            nextPuzzle.MakeMove(Move.Up);
            EvaluateNextPuzzle(openSet, closedSet, nextPuzzle);
        }
        if (row < 3)
        {
            Puzzle nextPuzzle = current.Clone();
            nextPuzzle.MakeMove(Move.Down);
            EvaluateNextPuzzle(openSet, closedSet, nextPuzzle);
        }
    }

    private static void EvaluateNextPuzzle(Queue<Puzzle> openSet, HashSet<Puzzle> closedSet, Puzzle nextPuzzle)
    {
        if (!closedSet.Contains(nextPuzzle))
        {
            openSet.Enqueue(nextPuzzle);
            if (nextPuzzle.Tiles.SequenceEqual(Puzzle.GOAL))
            {
                solution = nextPuzzle;
            }
        }
    }

    public enum Move
    {
        Left("L", -1),
        Right("R", +1),
        Up("U", -4),
        Down("D", +4);

        private Move(string symbol, int step)
        {
            Symbol = symbol;
            Step = step;
        }

        public string Symbol { get; private set; }
        public int Step { get; private set; }
    }

    public class Puzzle
    {
        public Puzzle(List<int> tiles, List<string> moves, int zeroIndex, int searchDepth)
        {
            Tiles = tiles;
            Moves = moves;
            ZeroIndex = zeroIndex;
            SearchDepth = searchDepth;
        }

        public void MakeMove(Move move)
        {
            int temp = Tiles[ZeroIndex + move.Step];
            Tiles[ZeroIndex + move.Step] = 0;
            Tiles[ZeroIndex] = temp;

            ZeroIndex += move.Step;
            Moves.Add(move.Symbol);

            if (!closedSet.Contains(this))
            {
                if (Tiles.SequenceEqual(Puzzle.GOAL))
                {
                    solution = this;
                }
                else
                {
                    openSet.Enqueue(this);
                }
            }
        }

        public int Heuristic()
        {
            int distance = 0;
          for (int i = 0; i < Tiles.Count; i++)
        {
            int tile = Tiles[i];
            if (tile > 0)
            {
                distance += Math.Abs((i / 4) - ((tile - 1) / 4)) + Math.Abs((i % 4) - ((tile - 1) % 4));
            }
        }
        return distance + SearchDepth;
    }

        public Puzzle Clone()
        {
            return new Puzzle(new List<int>(Tiles), new List<string>(Moves), ZeroIndex, SearchDepth + 1);
        }

        public void Display()
        {
            for (int i = 0; i < Tiles.Count; i++)
            {
                Console.Write(String.Format("{0}{1,2}{2}", (i % 4 == 0) ? "[" : "", Tiles[i], (i % 4 == 3) ? "]\n" : " "));
            }
            Console.WriteLine();
        }

        public override bool Equals(object obj)
        {
            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }
            Puzzle other = (Puzzle)obj;
            return Tiles.SequenceEqual(other.Tiles);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int hash = 17;
                hash = hash * 23 + Tiles.GetHashCode();
                hash = hash * 23 + ZeroIndex;
                return hash;
            }
        }

        public List<int> Tiles { get; private set; }
        public List<string> Moves { get; private set; }
        public int ZeroIndex { get; private set; }
        public int SearchDepth { get; private set; }

        private static readonly List<int> GOAL = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };
    }

    private static Puzzle solution;
}