ASTAR

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Runtime.InteropServices;
using System.Drawing;
using System.Text;

namespace A
{
    internal class AStar
    {
        private readonly HashSet<GameBoard> _closed = new HashSet<GameBoard>();
        private readonly HashSet<GameBoard> _open = new HashSet<GameBoard>();
        private GameBoard _startBoard;
        private GameBoard _goal;
        private readonly Dictionary<GameBoard, int> _gScore = new Dictionary<GameBoard, int>();
        private readonly Dictionary<GameBoard, int> _fScore = new Dictionary<GameBoard, int>();
        private readonly Dictionary<GameBoard, KeyValuePair<GameBoard, GameBoard.MoveDirection>> _cameFrom = new Dictionary<GameBoard, KeyValuePair<GameBoard, GameBoard.MoveDirection>>(); // node, parent
        private readonly PriorityQueue<GameBoard, int> _sortedFScore = new PriorityQueue<GameBoard, int>(Comparer<int>.Create((a, b) =>
            a > b ? -1 : a < b ? 1 : 0));

        public List<KeyValuePair<GameBoard, GameBoard.MoveDirection>> Search(GameBoard startBoard, GameBoard goal)
        {
            InitSearch(startBoard, goal);
            while (_open.Count > 0)
            {
                GameBoard current = LowestFScoreInOpen();
                if (current.Equals(_goal))
                {
                    return ReconstructPath(current);
                }

                _open.Remove(current);
                _closed.Add(current);

                foreach (GameBoard.MoveDirection direction in Enum.GetValues(typeof(GameBoard.MoveDirection)))
                {
                    GameBoard neighbor = current.MoveAndCopy(direction);

                    if (neighbor == null) continue;  // invalid direction
                    if(_closed.Contains(neighbor)) continue;

                    int tentativeScore = _gScore[current] + 1;
                    if (!_open.Contains(neighbor))
                    {
                        _open.Add(neighbor);
                    }
                    else if (tentativeScore >= _gScore[neighbor])
                    {
                        continue; // already in _open and this is not a better path
                    }

                    // best path so far
                    _cameFrom[neighbor] = new KeyValuePair<GameBoard, GameBoard.MoveDirection>(current, direction);
                    _gScore[neighbor] = tentativeScore;
                    int fscore = tentativeScore + Heuristic(neighbor);
                    _fScore[neighbor] = fscore;
                    _sortedFScore.Enqueue(new PriorityQueueItem<GameBoard, int>(neighbor, fscore));
                }
            }

            return null; // no path found
        }


        private int Heuristic(GameBoard gameBoard)
        {
            return Manhaten(gameBoard);
        }

        private int Manhaten(GameBoard gameBoard)
        {
            int sum = 0;
            for (int i = 0; i < gameBoard.Board.GetLength(0); i++)
            {
                for (int j = 0; j < gameBoard.Board.GetLength(1); j++)
                {
                    if (gameBoard.Board[i, j] == 0) continue;
                    Point locationOfValueInGoal = ValueGoalLocation(gameBoard, gameBoard.Board[i, j]);
                    int distance = Math.Abs(locationOfValueInGoal.X - i) + Math.Abs(locationOfValueInGoal.Y - j);
                    sum += distance;
                }
            }

            return sum;
        }

        private Point ValueGoalLocation(GameBoard gameBoard, int pointValue)
        {
            for (int i = 0; i < gameBoard.Board.GetLength(0); i++)
            {
                for (int j = 0; j < gameBoard.Board.GetLength(1); j++)
                {
                    if (_goal.Board[i, j] == pointValue)
                    {
                        return new Point(i, j);
                    }
                }
            }

            throw new ArgumentException("Didn't find the value in goal");
        }

        private GameBoard LowestFScoreInOpen()
        {
            var min = _open.First();
            PriorityQueueItem<GameBoard, int> minFScore = default(PriorityQueueItem<GameBoard, int>);
            if (_sortedFScore.Count > 0)
            {
                for (int i = 0; i < _open.Count; i++)
                {
                    minFScore = _sortedFScore.Peek();
                    if (_open.Contains(minFScore.Value))
                    {
                        break;
                    }
                    _sortedFScore.Dequeue();
                }

                foreach (var board in _open)
                {

                    if (minFScore.Priority == _fScore[board])
                    {
                        min = board;
                        break;
                    }
                }
            }
            else
            {
                foreach (var board in _open)
                {

                    if (_fScore[board] < _fScore[min])
                    {
                        min = board;
                    }
                }
            }

            return min;
        }

        public List<KeyValuePair<GameBoard, GameBoard.MoveDirection>> ReconstructPath(GameBoard current)
        {
            List<KeyValuePair<GameBoard, GameBoard.MoveDirection>> movesList = new List<KeyValuePair<GameBoard, GameBoard.MoveDirection>>();
            if (_cameFrom.Count == 0)
            {
                return movesList;
            }

            movesList.Add(_cameFrom[current]);
            while (_cameFrom.ContainsKey(current))
            {
                current = _cameFrom[current].Key;

                if (_cameFrom.ContainsKey(current))
                {
                    movesList.Add(_cameFrom[current]);
                }
            }
            movesList.Reverse(0, movesList.Count);
            return movesList;
        }

        private void InitSearch(GameBoard startBoard, GameBoard goal)
        {
            _closed.Clear();
            _open.Clear();
            _gScore.Clear();
            _fScore.Clear();
            this._startBoard = startBoard;
            this._goal = goal;
            _open.Add(_startBoard);
            _gScore[_startBoard] = 0;
            _fScore[_startBoard] = Heuristic(_startBoard);
        }

        public static void Main(string[] args)
        {
            GameBoard boardA = new GameBoard(new int[,]
            {
                {4, 7, 8},
                {6, 3, 2},
                {0, 5, 1},
            });

            GameBoard boardB = new GameBoard(new int[,]
            {
                {1, 4, 7},
                {2, 5, 8},
                {3, 6, 0},
            });

            GameBoard boardC = new GameBoard(new int[,]
            {
                {8, 3, 5},
                {1, 0, 2},
                {6, 7, 4},
            });

            GameBoard goal = new GameBoard(new int[,]
            {
                {1, 2, 3},
                {8, 0, 4},
                {7, 6, 5},
            });

            AStar aStar = new AStar();
            //Console.WriteLine("A");
            //SearchAndPrint(boardA, goal, aStar);
            //Console.WriteLine("B");
            //SearchAndPrint(boardB, goal, aStar);
            Console.WriteLine("C");
            SearchAndPrint(boardC, goal, aStar);
            Console.ReadKey();
        }

        private static void SearchAndPrint(GameBoard board, GameBoard goal, AStar aStar)
        {
            var sol = aStar.Search(board, goal);

            foreach (var boardDirectionPair in sol)
            {
                //boardDirectionPair.Key.PrintBoard();
                Console.WriteLine(GameBoard.EnumName(boardDirectionPair.Value));
                //Console.WriteLine();
            }
        }
    }




    //////////////////GameBoard.cs

      internal class GameBoard : IEqualityComparer<GameBoard>, IEquatable<GameBoard>
    {
        public enum MoveDirection
        {
            Up,
            Down,
            Left,
            Right,
        }

        private static readonly Dictionary<MoveDirection, string> DirectionsStrings = new Dictionary<MoveDirection, string>
        {
            {MoveDirection.Up, "^"},
            {MoveDirection.Down, "v"},
            {MoveDirection.Left, "<"},
            {MoveDirection.Right, ">"}
        };

        public static string EnumName(MoveDirection direction)
        {
            return DirectionsStrings[direction];
        }

        public int[,] Board { get; }
        private string _flatten;

        public GameBoard(int[,] board)
        {
            this.Board = board.Clone() as int[,];
            _flatten = FlattenToString(this);
        }

        public void PrintBoard()
        {
            for (int i = 0; i < Board.GetLength(0); i++)
            {
                Console.Write(" ");
                for (int j = 0; j < Board.GetLength(1); j++)
                {
                    Console.Write(Board[i,j]);
                    Console.Write(" ");
                }
                Console.WriteLine();
            }

            //Console.SetCursorPosition(0, 0);
        }

        public GameBoard MoveAndCopy(MoveDirection direction)
        {
            GameBoard newGameBoard = new GameBoard(this.Board);
            bool movePossible = newGameBoard.Move(direction);
            newGameBoard._flatten = FlattenToString(newGameBoard);
            return movePossible ? newGameBoard : null;
        }

        private bool Move(MoveDirection direction)
        {
            Point  emptySpot = FindEmptySpot();
            int tmp;

            switch (direction)
            {
                case MoveDirection.Up:      // we swap with the one below the empty
                    if (Board.GetLength(0) <= emptySpot.X + 1)
                    {
                        return false; // move not possible
                    }

                    tmp = Board[emptySpot.X + 1, emptySpot.Y];
                    Board[emptySpot.X + 1, emptySpot.Y] = 0;
                    Board[emptySpot.X, emptySpot.Y] = tmp;
                    break;
                case MoveDirection.Down:    // we swap with the one above the empty
                    if (0 > emptySpot.X - 1)
                    {
                        return false; // move not possible
                    }

                    tmp = Board[emptySpot.X - 1, emptySpot.Y];
                    Board[emptySpot.X - 1, emptySpot.Y] = 0;
                    Board[emptySpot.X, emptySpot.Y] = tmp;
                    break;
                case MoveDirection.Right:
                    if (0 > emptySpot.Y - 1)
                    {
                        return false; // move not possible
                    }

                    tmp = Board[emptySpot.X, emptySpot.Y - 1];
                    Board[emptySpot.X, emptySpot.Y - 1] = 0;
                    Board[emptySpot.X, emptySpot.Y] = tmp;
                    break;
                case MoveDirection.Left:
                    if (Board.GetLength(1) <= emptySpot.Y + 1)
                    {
                        return false; // move not possible
                    }

                    tmp = Board[emptySpot.X, emptySpot.Y + 1];
                    Board[emptySpot.X, emptySpot.Y + 1] = 0;
                    Board[emptySpot.X, emptySpot.Y] = tmp;
                    break;
                default:
                    throw new ArgumentOutOfRangeException(nameof(direction), direction, null);
            }

            return true;
        }

        private Point FindEmptySpot()
        {
            for (int i = 0; i < this.Board.GetLength(0); i++)
            {
                for (int j = 0; j < Board.GetLength(1); j++)
                {
                    if (Board[i, j] == 0)
                    {
                        return new Point(i, j);
                    }
                }
            }

            throw new Exception("didn't find zero");
        }

        public bool Equals(GameBoard x, GameBoard y)
        {
            return Equals(x.Board, y.Board);
        }

        public bool Equals(int[,] x, int[,] y)
        {
            for (int i = 0; i < x.GetLength(0); i++)
            {
                for (int j = 0; j < x.GetLength(1); j++)
                {
                    if (x[i, j] != y[i, j])
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        public int GetHashCode(GameBoard obj)
        {
            return obj._flatten.GetHashCode();
        }

        private static string FlattenToString(GameBoard obj)
        {
            StringBuilder str = new StringBuilder(obj.Board.Length);
            for (int i = 0; i < obj.Board.GetLength(0); i++)
            {
                for (int j = 0; j < obj.Board.GetLength(1); j++)
                {
                    str.Append(obj.Board[i, j]);
                }
            }
            return str.ToString();
        }

        public override int GetHashCode()
        {
            return Board.GetHashCode();
        }

        public bool Equals(GameBoard other)
        {
            if (ReferenceEquals(null, other)) return false;
            if (ReferenceEquals(this, other)) return true;
            return Equals(Board, other.Board);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != this.GetType()) return false;
            return Equals((GameBoard) obj);
        }
    }



// PriorityQueue.cs
//
// Jim Mischel

     [Serializable]
    [ComVisible(false)]
    public struct PriorityQueueItem<TValue, TPriority>
    {
        private TValue _value;
        public TValue Value
        {
            get { return _value; }
        }

        private TPriority _priority;
        public TPriority Priority
        {
            get { return _priority; }
        }

        internal PriorityQueueItem(TValue val, TPriority pri)
        {
            this._value = val;
            this._priority = pri;
        }
    }

    [Serializable]
    [ComVisible(false)]
    public class PriorityQueue<TValue, TPriority> : ICollection,
        IEnumerable<PriorityQueueItem<TValue, TPriority>>
    {
        private PriorityQueueItem<TValue, TPriority>[] items;

        private const Int32 DefaultCapacity = 16;
        private Int32 capacity;
        private Int32 numItems;

        private Comparison<TPriority> compareFunc;

        /// <summary>
        /// Initializes a new instance of the PriorityQueue class that is empty,
        /// has the default initial capacity, and uses the default IComparer.
        /// </summary>
        public PriorityQueue()
            : this(DefaultCapacity, Comparer<TPriority>.Default)
        {
        }

        public PriorityQueue(Int32 initialCapacity)
            : this(initialCapacity, Comparer<TPriority>.Default)
        {
        }

        public PriorityQueue(IComparer<TPriority> comparer)
            : this(DefaultCapacity, comparer)
        {
        }

        public PriorityQueue(int initialCapacity, IComparer<TPriority> comparer)
        {
            Init(initialCapacity, new Comparison<TPriority>(comparer.Compare));
        }

        public PriorityQueue(Comparison<TPriority> comparison)
            : this(DefaultCapacity, comparison)
        {
        }

        public PriorityQueue(int initialCapacity, Comparison<TPriority> comparison)
        {
            Init(initialCapacity, comparison);
        }

        private void Init(int initialCapacity, Comparison<TPriority> comparison)
        {
            numItems = 0;
            compareFunc = comparison;
            SetCapacity(initialCapacity);
        }

        public int Count
        {
            get { return numItems; }
        }

        public int Capacity
        {
            get { return items.Length; }
            set { SetCapacity(value); }
        }

        private void SetCapacity(int newCapacity)
        {
            int newCap = newCapacity;
            if (newCap < DefaultCapacity)
                newCap = DefaultCapacity;

            // throw exception if newCapacity < NumItems
            if (newCap < numItems)
                throw new ArgumentOutOfRangeException("newCapacity", "New capacity is less than Count");

            this.capacity = newCap;
            if (items == null)
            {
                items = new PriorityQueueItem<TValue, TPriority>[newCap];
                return;
            }

            // Resize the array.
            Array.Resize<PriorityQueueItem<TValue, TPriority>>(ref items, newCap);
        }

        public void Enqueue(PriorityQueueItem<TValue, TPriority> newItem)
        {
            if (numItems == capacity)
            {
                // need to increase capacity
                // grow by 50 percent
                SetCapacity((3 * Capacity) / 2);
            }

            int i = numItems;
            ++numItems;
            while ((i > 0) && (compareFunc(items[(i - 1) / 2].Priority, newItem.Priority) < 0))
            {
                items[i] = items[(i - 1) / 2];
                i = (i - 1) / 2;
            }
            items[i] = newItem;
            //if (!VerifyQueue())
            //{
            //    Console.WriteLine("ERROR: Queue out of order!");
            //}
        }

        public void Enqueue(TValue value, TPriority priority)
        {
            Enqueue(new PriorityQueueItem<TValue, TPriority>(value, priority));
        }

        private PriorityQueueItem<TValue, TPriority> RemoveAt(Int32 index)
        {
            PriorityQueueItem<TValue, TPriority> o = items[index];
            --numItems;
            // move the last item to fill the hole
            PriorityQueueItem<TValue, TPriority> tmp = items[numItems];
            // If you forget to clear this, you have a potential memory leak.
            items[numItems] = default(PriorityQueueItem<TValue, TPriority>);
            if (numItems > 0 && index != numItems)
            {
                // If the new item is greater than its parent, bubble up.
                int i = index;
                int parent = (i - 1) / 2;
                while (compareFunc(tmp.Priority, items[parent].Priority) > 0)
                {
                    items[i] = items[parent];
                    i = parent;
                    parent = (i - 1) / 2;
                }

                // if i == index, then we didn't move the item up
                if (i == index)
                {
                    // bubble down ...
                    while (i < (numItems) / 2)
                    {
                        int j = (2 * i) + 1;
                        if ((j < numItems - 1) && (compareFunc(items[j].Priority, items[j + 1].Priority) < 0))
                        {
                            ++j;
                        }
                        if (compareFunc(items[j].Priority, tmp.Priority) <= 0)
                        {
                            break;
                        }
                        items[i] = items[j];
                        i = j;
                    }
                }
                // Be sure to store the item in its place.
                items[i] = tmp;
            }
            //if (!VerifyQueue())
            //{
            //    Console.WriteLine("ERROR: Queue out of order!");
            //}
            return o;
        }

        // Function to check that the queue is coherent.
        public bool VerifyQueue()
        {
            int i = 0;
            while (i < numItems / 2)
            {
                int leftChild = (2 * i) + 1;
                int rightChild = leftChild + 1;
                if (compareFunc(items[i].Priority, items[leftChild].Priority) < 0)
                {
                    return false;
                }
                if (rightChild < numItems && compareFunc(items[i].Priority, items[rightChild].Priority) < 0)
                {
                    return false;
                }
                ++i;
            }
            return true;
        }

        public PriorityQueueItem<TValue, TPriority> Dequeue()
        {
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty");
            return RemoveAt(0);
        }

        /// <summary>
        /// Removes the item with the specified value from the queue.
        /// The passed equality comparison is used.
        /// </summary>
        /// <param name="item">The item to be removed.</param>
        /// <param name="comp">An object that implements the IEqualityComparer interface
        /// for the type of item in the collection.</param>
        public void Remove(TValue item, IEqualityComparer comparer)
        {
            // need to find the PriorityQueueItem that has the Data value of o
            for (int index = 0; index < numItems; ++index)
            {
                if (comparer.Equals(item, items[index].Value))
                {
                    RemoveAt(index);
                    return;
                }
            }
            throw new ApplicationException("The specified itemm is not in the queue.");
        }

        /// <summary>
        /// Removes the item with the specified value from the queue.
        /// The default type comparison function is used.
        /// </summary>
        /// <param name="item">The item to be removed.</param>
        public void Remove(TValue item)
        {
            Remove(item, EqualityComparer<TValue>.Default);
        }

        public PriorityQueueItem<TValue, TPriority> Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty");
            return items[0];
        }

        // Clear
        public void Clear()
        {
            for (int i = 0; i < numItems; ++i)
            {
                items[i] = default(PriorityQueueItem<TValue, TPriority>);
            }
            numItems = 0;
            TrimExcess();
        }

        /// <summary>
        /// Set the capacity to the actual number of items, if the current
        /// number of items is less than 90 percent of the current capacity.
        /// </summary>
        public void TrimExcess()
        {
            if (numItems < (float)0.9 * capacity)
            {
                SetCapacity(numItems);
            }
        }

        // Contains
        public  bool Contains(TValue o)
        {
            foreach (PriorityQueueItem<TValue, TPriority> x in items)
            {
                if (x.Value.Equals(o))
                    return true;
            }
            return false;
        }

        public void CopyTo(PriorityQueueItem<TValue, TPriority>[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "arrayIndex is less than 0.");
            if (array.Rank > 1)
                throw new ArgumentException("array is multidimensional.");
            if (numItems == 0)
                return;
            if (arrayIndex >= array.Length)
                throw new ArgumentException("arrayIndex is equal to or greater than the length of the array.");
            if (numItems > (array.Length - arrayIndex))
                throw new ArgumentException("The number of elements in the source ICollection is greater than the available space from arrayIndex to the end of the destination array.");

            for (int i = 0; i < numItems; i++)
            {
                array[arrayIndex + i] = items[i];
            }
        }

        #region ICollection Members

        public void CopyTo(Array array, int index)
        {
            this.CopyTo((PriorityQueueItem<TValue, TPriority>[])array, index);
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get { return items.SyncRoot; }
        }

        #endregion

        #region IEnumerable<PriorityQueueItem<TValue,TPriority>> Members

        public IEnumerator<PriorityQueueItem<TValue, TPriority>> GetEnumerator()
        {
            for (int i = 0; i < numItems; i++)
            {
                yield return items[i];
            }
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }

}