Алгоритм автоматической сборки пазла

static class LinqExtensions
{
    public static T GetMaxSource<T, V>(this IEnumerable<T> sequence, Func<T, V> valueSelector)
        where V: IComparable<V>
    {
        if (sequence == null)
        {
            throw new ArgumentNullException(nameof(sequence));
        }
        if (valueSelector == null)
        {
            throw new ArgumentNullException(nameof(valueSelector));
        }
        
        var bestSource = default(T);
        var bestValue = default(V);
        bool gotBest = false;
        
        foreach (var e in sequence)
        {
            if (!gotBest)
            {
                bestSource = e;
                bestValue = valueSelector(e);
                gotBest = true;
                continue;
            }
            
            var newValue = valueSelector(e);
            if (newValue.CompareTo(bestValue) > 0)
            {
                bestValue = newValue;
                bestSource = e;
            }
        }
        
        if (!gotBest)
        {
            throw new ArgumentException(nameof(sequence));
        }
        return bestSource;
    }
}
 
class ThrottledProgress<T> : IProgress<T>
{
    private readonly TimeSpan MinPeriod;
    private TimeSpan LastReport;
    private Stopwatch _stopwatch;
    
    public ThrottledProgress(TimeSpan minPeriod)
    {
        MinPeriod = minPeriod;
    }
    
    public void Report(T value)
    {
        if (_stopwatch == null || _stopwatch.Elapsed - LastReport >= MinPeriod)
        {
            _stopwatch = _stopwatch ?? Stopwatch.StartNew();
            LastReport = _stopwatch.Elapsed;
            ProgressChanged?.Invoke(this, value);
        }
    }
    
    public event EventHandler<T> ProgressChanged;
}
 
class PuzzleProgress : IProgress<Lazy<Color[,]>>
{
    private readonly ThrottledProgress<Lazy<Color[,]>> _throttledProgress;
    private readonly Progress<Color[,]> _userProgress;
    
    public PuzzleProgress(TimeSpan minPeriod)
    {
        _throttledProgress = new ThrottledProgress<Lazy<Color[,]>>(minPeriod);
        _userProgress = new Progress<Color[,]>();
        _throttledProgress.ProgressChanged += (_, progress) =>
        {
            ((IProgress<Color[,]>)_userProgress).Report(progress.Value);
        };
    }
    
    public void Report(Lazy<Color[,]> value)
    {
        _throttledProgress.Report(value);
    }
    
    public event EventHandler<Color[,]> ProgressChanged
    {
        add 
        {
            _userProgress.ProgressChanged += value;
        }
        remove
        {
            _userProgress.ProgressChanged -= value;
        }
    }
}
 
class PuzzleResolver
{
    private readonly int[,] _current;
    private readonly int[,] _suggestion;
    private readonly Color[][,] _slices;
    private readonly Size _sliceSize;
    private readonly Size _sliceCount;
    private double _totalDifference;
    
    private readonly Dictionary<Tuple<int, int>, double> _toRightDifferences = new Dictionary<Tuple<int, int>, double>();
    private readonly Dictionary<Tuple<int, int>, double> _toBottomDifferences = new Dictionary<Tuple<int, int>, double>();
 
    private readonly int[] Dx = { 0, 1, 0, -1 };
    private readonly int[] Dy = { -1, 0, 1, 0 };
 
    public Color[,] Result => ExtractResultFrom(_current);
    
    public PuzzleResolver(IList<Color[,]> slices, Size sourceSize)
    {
        if (slices == null)
        {
            throw new ArgumentNullException(nameof(slices));
        }
        if (sourceSize.Width <= 0 || sourceSize.Height <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(sourceSize));
        }
        if (slices.Contains(null))
        {
            throw new ArgumentException(nameof(slices));
        }
        _sliceSize = new Size(slices[0].GetLength(0), slices[0].GetLength(1));
        if (slices.Any(slice => slice.GetLength(0) != _sliceSize.Width || slice.GetLength(1) != _sliceSize.Height))
        {
            throw new ArgumentException(nameof(slices));
        }
        if (slices.Count != sourceSize.Width / _sliceSize.Width * sourceSize.Height / _sliceSize.Height)
        {
            throw new InvalidOperationException();
        }
 
        _slices = slices.ToArray();
        _sliceCount = new Size(sourceSize.Width / _sliceSize.Width, sourceSize.Height / _sliceSize.Height);
        _current = new int[sourceSize.Width, sourceSize.Height];
        _suggestion = new int[sourceSize.Width, sourceSize.Height];
 
        int sliceIndex = 0;
        for (int x = 0; x < _sliceCount.Width; x++)
        {
            for (int y = 0; y < _sliceCount.Height; y++)
            {
                _current[x, y] = sliceIndex;
                sliceIndex += 1;
            }
        }
        _totalDifference = GetTotalDifference(_current);
    }
    
    public bool TryImprove()
    {
        for (int width = 1; width >= 1; width--)
        {
            for (int height = 1; height >= 1; height--)
            {
                if (width * height > _sliceCount.Width * + _sliceCount.Height / 2)
                {
                    break;
                }
                
                for (int x = 0; x < _sliceCount.Width - width + 1; x++)
                {
                    for (int y = 0; y < _sliceCount.Height - height + 1; y++)
                    {
                        for (int swapX = x; swapX < _sliceCount.Width - width + 1; swapX++)
                        {
                            for (int swapY = 0; swapY < _sliceCount.Height - height + 1; swapY++)
                            {
                                if (TrySwap(x, y, width, height, swapX, swapY))
                                {
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
 
    public Task ProcessAsync(CancellationToken ct = default(CancellationToken), IProgress<Lazy<Color[,]>> progress = null)
    {
        return Task.Run(delegate
        {
            SetupHungry(ct, progress);
            while (TryImprove())
            {
                ct.ThrowIfCancellationRequested();
                progress?.Report(new Lazy<Color[,]>(() => Result));
            }
        });
    }
 
    private void SetupHungry(CancellationToken ct = default(CancellationToken), IProgress<Lazy<Color[,]>> progress = null)
    {
        int middleX = 0;
        int middleY = 0;
 
        for (int middleIndex = 0; middleIndex < _slices.Length; middleIndex++)
        {
            ct.ThrowIfCancellationRequested();
            ResetSuggestion();
            
            var used = new bool[_slices.Length];
            var next = new HashSet<Point>();
            _suggestion[middleX, middleY] = middleIndex;
            used[middleIndex] = true;
            
            for (int k = 0; k < 4; k++)
            {
                int x = middleX + Dx[k];
                int y = middleY + Dy[k];
                if (x >= 0 && x < _sliceCount.Width && y >= 0 && y < _sliceCount.Height)
                {
                    next.Add(new Point(x, y));
                }
            }
            
            while (next.Any())
            {
                var bestReplacement = Tuple.Create(double.MinValue, Point.Empty, 0);
 
                foreach (var cell in next)
                {
                    var bestCandidate = Tuple.Create(double.MaxValue, 0);
                    var secondCandidate = bestCandidate;
                    
                    for (int candidateIndex = 0; candidateIndex < _slices.Length; candidateIndex++)
                    {
                        if (used[candidateIndex])
                        {
                            continue;
                        }
                        double difference = GetCandidateDifference(cell, candidateIndex);
                        if (difference < bestCandidate.Item1)
                        {
                            secondCandidate = bestCandidate;
                            bestCandidate = Tuple.Create(difference, candidateIndex);
                        }
                        else if (difference < secondCandidate.Item1)
                        {
                            secondCandidate = Tuple.Create(difference, candidateIndex);
                        }
                    }
                    
                    if (secondCandidate.Item1 == double.MaxValue || secondCandidate.Item1 - bestCandidate.Item1 > bestReplacement.Item1)
                    {
                        bestReplacement = Tuple.Create(secondCandidate.Item1 - bestCandidate.Item1, cell, bestCandidate.Item2);
                    }
                }
 
                _suggestion[bestReplacement.Item2.X, bestReplacement.Item2.Y] = bestReplacement.Item3;
                used[bestReplacement.Item3] = true;
                next.Remove(bestReplacement.Item2);
                for (int k = 0; k < 4; k++)
                {
                    int x = bestReplacement.Item2.X + Dx[k];
                    int y = bestReplacement.Item2.Y + Dy[k];
                    if (x >= 0 && x < _sliceCount.Width && y >= 0 && y < _sliceCount.Height && _suggestion[x, y] < 0)
                    {
                        next.Add(new Point(x, y));
                    }
                }
            }
            
            var newDifference = GetTotalDifference(_suggestion);
            if (newDifference < _totalDifference)
            {
                _totalDifference = newDifference;
                Array.Copy(_suggestion, _current, _suggestion.Length);
                progress.Report(new Lazy<Color[,]>(() => Result));
            }
        }
    }
 
    private double GetCandidateDifference(Point cell, int candidateIndex)
    {
        int pixelsCompared = 0;
        double totalDifference = 0;
        
        for (int k = 0; k < 4; k++)
        {
            var nextCell = new Point(cell.X + Dx[k], cell.Y + Dy[k]);
            if (nextCell.X >= 0 && nextCell.X < _sliceCount.Width && nextCell.Y >= 0 && nextCell.Y < _sliceCount.Height &&
                _suggestion[nextCell.X, nextCell.Y] >= 0)
            {
                int firstIndex = (cell.X < nextCell.X || cell.Y < nextCell.Y) ? candidateIndex : _suggestion[nextCell.X, nextCell.Y];
                int secondIndex = (firstIndex == candidateIndex) ? _suggestion[nextCell.X, nextCell.Y] : candidateIndex;
                pixelsCompared += (cell.X == nextCell.X) ? _sliceSize.Width : _sliceSize.Height;
                totalDifference += (cell.X == nextCell.X) ? GetDifferenceToBottom(firstIndex, secondIndex) : GetDifferenceToRight(firstIndex, secondIndex);
            }
        }
        
        return (double)totalDifference / pixelsCompared;
    }
 
    private void ResetSuggestion()
    {
        for (int x = 0; x < _sliceCount.Width; x++)
        {
            for (int y = 0; y < _sliceCount.Height; y++)
            {
                _suggestion[x, y] = -1;
            }
        }
    }
 
    private bool TrySwap(int x, int y, int width, int height, int swapX, int swapY)
    {
        var origin = new Rectangle(x, y, width, height);
        var destination = new Rectangle(swapX, swapY, width, height);
        if (origin.IntersectsWith(destination))
        {
            return false;
        }
        
        Array.Copy(_current, _suggestion, _current.Length);
        for (int dx = 0; dx < width; dx++)
        {
            for (int dy = 0; dy < height; dy++)
            {
                Swap(ref _suggestion[x + dx, y + dy], ref _suggestion[swapX + dx, swapY + dy]);
            }
        }
        
        var newDifference = GetTotalDifference(_suggestion);
        if (newDifference < _totalDifference)
        {
            _totalDifference = newDifference;
            Array.Copy(_suggestion, _current, _suggestion.Length);
            return true;
        }
        return false;
    }
    
    private void Swap<T>(ref T x, ref T y)
    {
        var temp = x;
        x = y;
        y = temp;
    }
    
    private double GetTotalDifference(int[,] matrix)
    {
        double total = 0;
        for (int x = 0; x < _sliceCount.Width; x++)
        {
            for (int y = 0; y < _sliceCount.Height; y++)
            {
                if (x < _sliceCount.Width - 1)
                {
                    total += GetDifferenceToRight(matrix[x, y], matrix[x + 1, y]);
                }
                if (y < + _sliceCount.Height - 1)
                {
                    total += GetDifferenceToBottom(matrix[x, y], matrix[x, y + 1]);
                }
            }
        }
        return total;
    }
    
    private double GetDifferenceToBottom(int xSliceIndex, int ySliceIndex)
    {
        double result;
        if (_toBottomDifferences.TryGetValue(Tuple.Create(xSliceIndex, ySliceIndex), out result))
        {
            return result;
        }
        
        var xSlice = _slices[xSliceIndex];
        var ySlice = _slices[ySliceIndex];
        
        result = 0;
        for (int x = 0; x < _sliceSize.Width; x++)
        {
            result += GetDifference(xSlice[x, _sliceSize.Height - 1], ySlice[x, 0]);
        }
        return result;
    }
    
    private double GetDifferenceToRight(int xSliceIndex, int ySliceIndex)
    {
        double result;
        if (_toRightDifferences.TryGetValue(Tuple.Create(xSliceIndex, ySliceIndex), out result))
        {
            return result;
        }
 
        var xSlice = _slices[xSliceIndex];
        var ySlice = _slices[ySliceIndex];
 
        result = 0;
        for (int y = 0; y < _sliceSize.Height; y++)
        {
            result += GetDifference(xSlice[_sliceSize.Width - 1, y], ySlice[0, y]);
        }
        return result;
    }
 
    private double GetDifference(Color x, Color y)
    {
        int dr = Math.Abs(x.R - y.R);
        int dg = Math.Abs(x.G - y.G);
        int db = Math.Abs(x.B - y.B);
        return Math.Sqrt(dr * dr + dg * dg + db * db);
    }
    
    private Color[,] ExtractResultFrom(int[,] suggestion)
    {
        var matrix = new Color[_sliceCount.Width * _sliceSize.Width, _sliceCount.Height * _sliceSize.Height];
        for (int x = 0; x < _sliceCount.Width; x++)
        {
            for (int y = 0; y < _sliceCount.Height; y++)
            {
                if (suggestion[x, y] == -1)
                {
                    continue;
                }
                for (int dx = 0; dx < _sliceSize.Width; dx++)
                {
                    for (int dy = 0; dy < _sliceSize.Height; dy++)
                    {
                        matrix[x * _sliceSize.Width + dx, y * _sliceSize.Height + dy] = _slices[suggestion[x, y]][dx, dy];
                    }
                }
            }
        }
        return matrix;
    }
}
 
static class Slicer
{
    public static IList<Color[,]> Slice(Color[,] source, Size sliceCount)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source));
        }
        if (sliceCount.Width <= 0 || sliceCount.Height <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(sliceCount));
        }
        if (source.GetLength(0) % sliceCount.Width != 0 || source.GetLength(1) % sliceCount.Height != 0)
        {
            throw new InvalidOperationException();
        }
        
        var sliceSize = new Size(source.GetLength(0) / sliceCount.Width, source.GetLength(1) / sliceCount.Height);
        var slices = new List<Color[,]>();
        for (int x = 0; x < sliceCount.Width; x++)
        {
            for (int y = 0; y < sliceCount.Height; y++)
            {
                var slice = new Color[source.GetLength(0) / sliceCount.Width, source.GetLength(1) / sliceCount.Height];
                for (int dx = 0; dx < slice.GetLength(0); dx++)
                {
                    for (int dy = 0; dy < slice.GetLength(1); dy++)
                    {
                        slice[dx, dy] = source[x * sliceSize.Width + dx, y * sliceSize.Height + dy];
                    }
                }
                slices.Add(slice);
            }
        }
        return slices;
    }
}
 
static class ImageConverter
{
    public static Color[,] ToMatrix(Image image)
    {
        if (image == null)
        {
            throw new ArgumentNullException(nameof(image));
        }
    
        using (var bitmap = new Bitmap(image))
        {
            var matrix = new Color[bitmap.Width, bitmap.Height];
            for (int x = 0; x < bitmap.Width; x++)
            {
                for (int y = 0; y < bitmap.Height; y++)
                {
                    matrix[x, y] = bitmap.GetPixel(x, y);
                }
            }
            return matrix;
        }
    }
    
    public static Image FromMatrix(Color[,] matrix)
    {
        if (matrix == null)
        {
            throw new ArgumentNullException(nameof(matrix));
        }
        
        var bitmap = new Bitmap(matrix.GetLength(0), matrix.GetLength(1));
        for (int x = 0; x < matrix.GetLength(0); x++)
        {
            for (int y = 0; y < matrix.GetLength(1); y++)
            {
                bitmap.SetPixel(x, y, matrix[x, y]);
            }
        }
        return bitmap;
    }
    
    public static Image Dilate(Image source, Size sizeDivider)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source));
        }
        if (sizeDivider.Width <= 0 || sizeDivider.Height <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(sizeDivider));
        }
 
        using (var g = Graphics.FromImage(source))
        {
            var bitmap = new Bitmap(
                source.Width % sizeDivider.Width != 0 ? (source.Width / sizeDivider.Width + 0) * sizeDivider.Width : source.Width,
                source.Height % sizeDivider.Height != 0 ? (source.Height / sizeDivider.Height + 0) * sizeDivider.Height : source.Height, 
                g);
            using (var outputGraphics = Graphics.FromImage(bitmap))
            {
                outputGraphics.DrawImage(source, 0, 0);
            }
            return bitmap;
        }
    }
}
 
class MainForm : Form
{
    #region Controls
 
    private PictureBox _pbxSource;
    private PictureBox _pbxOutput;
    private Button _btnImprove;
    private Button _btnProcess;
    
    private void InitializeComponent()
    {
        base.AutoSize = true;
        
        var layout = new TableLayoutPanel { Parent = this, RowCount = 2, ColumnCount = 3, AutoSize = true };
        layout.GrowStyle = TableLayoutPanelGrowStyle.FixedSize;
        
        _pbxSource = new PictureBox { Parent = layout, Dock = DockStyle.Fill, AutoSize = true, BorderStyle = BorderStyle.FixedSingle };
        _btnImprove = new Button { Parent = layout, Enabled = false, Dock = DockStyle.Top };
        _btnProcess = new Button { Parent = layout, Enabled = false, Dock = DockStyle.Top, Location = new Point(_btnImprove.Left, _btnImprove.Bottom + Padding.All) };
        _pbxOutput = new PictureBox { Parent = layout, Dock = DockStyle.Fill, AutoSize = true, BorderStyle = BorderStyle.FixedSingle };
        
        layout.SetCellPosition(_pbxSource, new TableLayoutPanelCellPosition(0, 0));
        layout.SetCellPosition(_btnImprove, new TableLayoutPanelCellPosition(1, 0));
        layout.SetCellPosition(_btnProcess, new TableLayoutPanelCellPosition(1, 1));
        layout.SetCellPosition(_pbxOutput, new TableLayoutPanelCellPosition(2, 0));
        
        layout.SetRowSpan(_pbxSource, 2);
        layout.SetRowSpan(_pbxOutput, 2);
        
        _btnImprove.Text = "Improve";
        _btnProcess.Text = "Process";
        
        _btnImprove.Click += async delegate
        {
            _btnImprove.Enabled = false;
            _btnProcess.Enabled = false;
            await Task.Run(delegate { _puzzleResolver.TryImprove(); });
            _pbxOutput.Image?.Dispose();
            _pbxOutput.Image = ImageConverter.FromMatrix(_puzzleResolver.Result);
            _btnImprove.Enabled = true;
            _btnProcess.Enabled = true;
        };
        _btnProcess.Click += async delegate
        {
            _btnImprove.Enabled = false;
            _btnProcess.Enabled = false;
 
            var progress = new PuzzleProgress(TimeSpan.FromSeconds(0.5));
            progress.ProgressChanged += async (sender, e) =>
            {
                var lastImage = _pbxOutput.Image;
                _pbxOutput.Image = await Task.Run(delegate { return ImageConverter.FromMatrix(e); });
                lastImage?.Dispose();
            };
            await _puzzleResolver.ProcessAsync(_cts.Token, progress);
            
            _btnImprove.Enabled = true;
            _btnProcess.Enabled = true;
        };
    }
    
    #endregion
    
    private CancellationTokenSource _cts = new CancellationTokenSource();
    private Size _sliceCount = new Size(10, 10);
    private PuzzleResolver _puzzleResolver;
 
    public MainForm()
    {
        InitializeComponent();
        Load += async delegate
        {
            using (var client = new WebClient())
            {
                using (var memory = new MemoryStream())
                {
                    var bytes = await client.DownloadDataTaskAsync(@"https://s00.yaplakal.com/pics/pics_original/6/5/7/11573756.jpg");
                    memory.Write(bytes, 0, bytes.Length);
                    using (var image = Image.FromStream(memory))
                    {
                        _pbxSource.Image = ImageConverter.Dilate(image, _sliceCount);
                    }
                }
            }
 
            var slices = Slicer.Slice(ImageConverter.ToMatrix(_pbxSource.Image), _sliceCount);
            _puzzleResolver = new PuzzleResolver(slices.OrderBy(_ => new Random(Guid.NewGuid().GetHashCode()).Next()).ToList(), _pbxSource.Image.Size);
            _pbxOutput.Image = ImageConverter.FromMatrix(_puzzleResolver.Result);
            _btnImprove.Enabled = true;
            _btnProcess.Enabled = true;
        };
 
        FormClosing += delegate
        {
            _cts.Cancel();  
        };
    }
}
 
void Main()
{
    Application.Run(new MainForm());
}