15SlidePuzzle.cs

<Query Kind="Program">
  <Reference>&lt;RuntimeDirectory&gt;\System.dll</Reference>
  <Reference>&lt;RuntimeDirectory&gt;\System.Net.dll</Reference>
  <Reference>&lt;RuntimeDirectory&gt;\System.Net.Http.dll</Reference>
  <Reference>&lt;RuntimeDirectory&gt;\System.Web.dll</Reference>
  <NuGetReference>Microsoft.Net.Http</NuGetReference>
  <NuGetReference>Newtonsoft.Json</NuGetReference>
  <NuGetReference>Sendgrid</NuGetReference>
  <Namespace>Newtonsoft.Json</Namespace>
  <Namespace>Newtonsoft.Json.Bson</Namespace>
  <Namespace>Newtonsoft.Json.Converters</Namespace>
  <Namespace>Newtonsoft.Json.Linq</Namespace>
  <Namespace>Newtonsoft.Json.Schema</Namespace>
  <Namespace>Newtonsoft.Json.Serialization</Namespace>
  <Namespace>SendGrid.SmtpApi</Namespace>
  <Namespace>System.IO</Namespace>
  <Namespace>System.Net</Namespace>
  <Namespace>System.Web.Mail</Namespace>
</Query>
//using System;
//using System.Linq;
//using System.Collections.Generic;
//public static class Extension
//{
//	public static void ForEach<T>(this IEnumerable<T> e, Action<T, int> action)
//	{
//		var i = 0;
//		foreach (var element in e) action(element, i++);
//	}
//
//}
public class FifteenPuzzle
{
    public static void Main()
    {
        var inputs = Console.ReadLine().Split(' ').Select(int.Parse)
            .Concat(Console.ReadLine().Split(' ').Select(int.Parse))
            .Concat(Console.ReadLine().Split(' ').Select(int.Parse))
            .Concat(Console.ReadLine().Split(' ').Select(int.Parse))
            .Cast<int>()
            .ToArray();
        
        foreach (var max in Enumerable.Range(1, 45))
        {
            if (!Board.Move(new Board(inputs), 1, max))
                continue;
            Console.WriteLine(max);
            break;
        }
    }
}
public class Board
{
    public Node[] Nodes { get; set; }
    public HashSet<long> Hash { get; private set; }
    public Board(IEnumerable<int> inputs)
    {
        Nodes = inputs.Select((x, i) => new Node((i + 1) % 16, x))
            .ToArray();
        Hash = new HashSet<long>();
    }
    
    public Board() { }
    
//    public Board[] Move(int count, int max)
//    {
//        var empty = Nodes.First(x => x.Current == 0);
//        var children = empty.AdjacentNumbers
//            .Select(_ => Board.Clone(this))
//            .ToArray();
//        
//        empty.AdjacentNumbers
//            .ForEach((adj, i) =>
//            {
//                var board = children[i];
//                var left = board.Nodes.First(x => x.Current == 0);
//                var right = board.Nodes.First(x => x.CorrectNumber == adj);
//                
//                board.SwapCurrent(left, right);
//                
//                if (!hash.Add(board.GetHash()))
//                    children[i] = null;
//                else if (board.Nodes.Where(x => x.Current != 0).Sum(x => GetManhattanDistance(x.Current, x.CorrectNumber)) > max - count)
//                    children[i] = null;
//            });
//        
//        return children.Where(x => x != null).ToArray();
//    }
    public static bool Move(Board board, int count, int max)
    {
        if (board.Nodes.All(x => x.IsCorrect()))
            return true;
        var empty = board.Nodes.First(x => x.Current == 0);
        var children = empty.AdjacentNumbers
            .Select(_ => Board.Clone(board))
            .ToArray();
        
        empty.AdjacentNumbers
            .ForEach((adj, i) =>
            {
                var child = children[i];
                var left = child.Nodes.First(x => x.Current == 0);
                var right = child.Nodes.First(x => x.CorrectNumber == adj);
                
                child.SwapCurrent(left, right);
                
                if (!child.Hash.Add(child.GetHash()))
                    children[i] = null;
                else
                {
                    var distance = child.Nodes.Where(x => x.Current != 0).Sum(x => GetManhattanDistance(x.Current, x.CorrectNumber));
                    if (distance > max - count)
                        children[i] = null;
                }
            });
        children = children.Where(x => x != null).ToArray();
        
//        if (children.Any(x => x.Nodes.All(node => node.IsCorrect()))) return true;
        
        return children.Any(x => Board.Move(x, count + 1, max));
    }
    public void SwapCurrent(Node left, Node right)
    {
        var temp = left.Current;
        left.Current = right.Current;
        right.Current = temp;
    }
    
    private static Board Clone(Board board)
    {
        return new Board
        {
            Nodes = board.Nodes.Select(Node.Clone)
                .ToArray(),
            Hash = new HashSet<long>(board.Hash)
        };
    }
    
    public override string ToString()
    {
        return Nodes.Select(x => x.Current)
            .Select(x => x.ToString())
            .Aggregate((acc, x) => acc + " " + x);
    }
    public long GetHash()
    {
        var code = Nodes.Select(x => x.Current).Aggregate((accum, x) => accum * 10 + x);
        return code;
    }
    
    private static int GetManhattanDistance(int current, int correct)
    {
        var cu = current - 1;
        var co = correct == 0 ? 15 : correct - 1;
        var d = Math.Abs(cu / 4 - co / 4) + Math.Abs(cu % 4 - co % 4);
        return d;
    }
}
public class Node
{
    private static readonly Dictionary<int, int[]> adjacentNumbersDic =
        new Dictionary<int, int[]>
        {
            { 1, new [] { 2, 4 } },
            { 2, new [] { 1, 3, 6 } },
            { 3, new [] { 2, 4, 7 } },
            { 4, new [] { 3, 8 } },
            { 5, new [] { 1, 5, 9 } },
            { 6, new [] { 2, 5, 7, 10 } },
            { 7, new [] { 3, 6, 8, 11 } },
            { 8, new [] { 4, 7, 12 } },
            { 9, new [] { 5, 10, 13 } },
            { 10, new [] { 6, 9, 11, 14 } },
            { 11, new [] { 7, 10, 12, 15 } },
            { 12, new [] { 8, 11, 0 } },
            { 13, new [] { 9, 14 } },
            { 14, new [] { 10, 13, 15 } },
            { 15, new [] { 11, 14, 0 } },
            { 0, new [] { 12, 15 } },
        };
    public int CorrectNumber { get; private set; }    
    public int Current { get; set; }
    public int[] AdjacentNumbers { get; set; }
    public Node(int correct, int current)
    {
        CorrectNumber = correct;
        Current = current;
        AdjacentNumbers = adjacentNumbersDic[correct];
    }
    
    public static Node Clone(Node node)
    {
        return new Node(node.CorrectNumber, node.Current);
    }
    
    public bool IsCorrect() { return CorrectNumber == Current; }
}