Resolved Alghoritm of autocompleting puzzles

[Dragon4ik]

I have a task to write a programm, which slice the image into the equal rectangle puzzles . Then the program must solve this puzzle without knowing the way it was sliced. I wrote the code, but it works time after time and i can't understand what problem is. Thank you in advance for any help.
P.S. This alghoritm place every piece in the top left corner and try to find the best neighbor piece through the least difference between border pixels

using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Media.Imaging;

namespace Puzzles
{

    struct PixelColor
    {
        public byte Blue;
        public byte Green;
        public byte Red;
        public byte Alpha;
    }

    class Alghoritm
    {
        

        private List<int> GetNumbers(List<BitmapSource> list)
        {
            List<int> numbers = new List<int>();

            for (int i = 1; i <= list.Count; i++)
            {
                if (list.Count % i == 0)
                {
                    numbers.Add(i);
                }
            }

            return numbers;
        }
        private PixelColor[,] GetPixels(BitmapSource source)
        {
            if (source.Format != PixelFormats.Bgra32)
                source = new FormatConvertedBitmap(source, PixelFormats.Bgra32, null, 0);

            int width = source.PixelWidth;
            int height = source.PixelHeight;
            PixelColor[,] result = new PixelColor[width, height];


            source.CopyPixels(result, width * 4, 0, true);

            return result;
        }

        private double GetDifference(PixelColor first, PixelColor second)
        {
            int dr = Math.Abs(first.Red - second.Red);
            int dg = Math.Abs(first.Green - second.Green);
            int db = Math.Abs(first.Blue - second.Blue);
            int da = Math.Abs(first.Alpha - second.Alpha);

            return Math.Sqrt(dr * dr + dg * dg + db * db );
        }

        private double GetRightDifference(PixelColor[,] left, PixelColor[,] right)
        {
            double rightDifference = 0;

            try
            {
                if (left.Length != right.Length)
                    throw new Exception("Щось пішло не так");

                for (int i = 0; i < left.GetLength(0); i++)
                {
                    rightDifference += GetDifference(left[i, left.GetLength(1) - 1], right[i, 0]);
                }

            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
            }

            return rightDifference;

        }

        private double GetBottomDifference(PixelColor[,] up, PixelColor[,] down)
        {
            double bottomDifference = 0;

            try
            {
                if (up.Length != down.Length)
                    throw new Exception("Щось пішло не так і тут");

                for (int i = 0; i < up.GetLength(1); i++)
                {
                    bottomDifference += GetDifference(up[up.GetLength(0) - 1, i], down[0, i]);
                }
            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
            }

            return bottomDifference;
        }

        private BitmapSource GetRightImage(BitmapSource first, List<BitmapSource> list, ref double totalDifference)
        {
            double min = Int32.MaxValue;

            PixelColor[,] left = GetPixels(first);
            BitmapSource next = null;


            for (int i = 0; i < list.Count; i++)
            {
                PixelColor[,] right = GetPixels(list[i]);

                double value = GetRightDifference(left, right);

                if (min > value)
                {
                    next = list[i];
                    min = value;
                }
            }
            totalDifference += min;

            return next;
        }

        private BitmapSource GetBottomImage(BitmapSource first, List<BitmapSource> list, ref double totalDifference)
        {
            double min = Int32.MaxValue;

            PixelColor[,] up = GetPixels(first);
            BitmapSource next = null;


            for (int i = 0; i < list.Count; i++)
            {
                PixelColor[,] down = GetPixels(list[i]);

                double value = GetBottomDifference(up, down);

                if (min > value)
                {
                    next = list[i];
                    min = value;
                }
            }

            totalDifference += min;

            return next;
        }

        private double GetBestCurrentVariant(List<BitmapSource> list, int row,int col, ref BitmapSource[,] bestChoice)
        {
            BitmapSource bestPiece;

            double min = Int32.MaxValue;

                for (int j = 0; j < list.Count; j++)    //перебір всіх елементів колекції для даної розстановки
                {
                    double total = 0; //показує повну різницю всього малюнку

                    BitmapSource[,] elements = new BitmapSource[row, col];  //отриманий результат

                    List<BitmapSource> cash = new List<BitmapSource>(list);     //колекція доступних елементів

                    elements[0, 0] = cash[j];

                    cash.RemoveAt(j);

                    for (int irow = 0; irow < row - 1; irow++)    // перебір по рядкам
                    {
                        for (int icol = 0; icol < col - 1; icol++)  //перебір по стовпцям
                        {
                            //for(int icas = 0; icas<cash.Count;icas++)   //перебір по доступним елементам
                            //{
                            //}

                            bestPiece = GetRightImage(elements[irow, icol], cash, ref total);//отримуємо найкращий правий фрагмент
                            elements[irow, icol + 1] = bestPiece;//додаємо отриманий фрагмент до результату

                            cash.Remove(bestPiece);//видаляємо недоступний елемент

                        }

                        bestPiece = GetBottomImage(elements[irow, 0], cash, ref total);//отримуємо найкращий нижній фрагмент

                        elements[irow+1, 0] = bestPiece;//додаємо отриманий фрагмент до результату

                        cash.Remove(bestPiece);//видаляємо недоступний елемент
                    }

                    //додаємо фрагменти до останнього рядка
                    for (int icol = 0; icol < col - 1; icol++)  //перебір по стовпцям
                    {
                        bestPiece = GetRightImage(elements[row - 1, icol], cash, ref total);//отримуємо найкращий правий фрагмент
                        elements[row - 1, icol + 1] = bestPiece;//додаємо отриманий фрагмент до результату

                        cash.Remove(bestPiece);//видаляємо недоступний елемент
                    }

                    if (min > total)
                    {
                        bestChoice = (BitmapSource[,])elements.Clone();
                        min = total;
                    }
                }

            return min;
        }

        public BitmapSource[,] GetBestPuzzleImage(List<BitmapImage> list)
        {
            List<BitmapSource> bmp = new List<BitmapSource>();

            for(int i=0;i<list.Count;i++)
            {
                BitmapSource temp = (BitmapSource)list[i];
                bmp.Add(temp);
            }

            List<int> numbers = new List<int>(GetNumbers(bmp));

            BitmapSource[,] bestChoice = null;

            double min = Int32.MaxValue;  //значення найменшої різниці малюнку(для визначення найкращого результату)

            for (int i = 0; i < numbers.Count;i++)
            {
                int row = numbers[i];   //кількість рядків
                int col = list.Count / row;     //кількість стовпців

                BitmapSource[,] possibleChoice = new BitmapSource[row,col];

                double value = GetBestCurrentVariant(bmp, row, col, ref possibleChoice);

                if (min > value)
                {
                    bestChoice = (BitmapSource[,])possibleChoice.Clone();

                    min = value;
                }
            }

            return bestChoice;
        }
    }
}

 

[Skydiver]

Can you explain what problem you are encountering with your code, and what you have already tried to solve the problem?

 

[jmcilhinney]

You need to debug the code, stepping through it line by line and determining what you expect to happen at each step based on the algorithm. When you find that what happened does not match your expectations, you've found an issue. Even if you still can't work out how to fix it, at least you can give us ALL the relevant information.

 

[Dragon4ik]

It's source image

And what returns alghoritm:

or

I look through the alghoritm with debugger, but can't understand, why it choose this variant as the best choice and see it as variant with the least total difference between border pixels. And when it work with the RIGHT variant of completed puzzle, it sees , that this variant doesn't have the minimal difference.

P.S. I also add the code of slicing alghoritm ( I hope it can be also the source of problem and also think maybe it slice image not in the right way):

for (int y = 0, i=0; y < image.ActualHeight; y+=nheight, i++)
            {
                for (int x = 0, j=0; x < image.ActualWidth; x+=nwidth, j++)
                {
                    var encoder = new PngBitmapEncoder();

                    //розріз зораження на окремі фрагменти
                    try
                    {
                        CroppedBitmap cb = new CroppedBitmap((BitmapSource)bitmap, new Int32Rect(x, y, nwidth, nheight));
                        Image img = new Image { Source = cb };
                      
                        encoder.Frames.Add(BitmapFrame.Create((BitmapSource)img.Source));
                    }
                    catch(ArgumentException ex)
                    {
                        break;
                    }
                    
                    //шлях для окремого фрагменту
                    string filename = path + "\\"+ source + $"_{i}_{j}.jpg";
                    
                    //збереження фрагменту
                    try
                    {
                        using (FileStream stream = new FileStream(filename, FileMode.Create))
                        {
                            encoder.Save(stream);
                        }
                    }
                    catch(Exception ex)
                    {
                        MessageBox.Show("Вказаний невірний шлях");
                    }
                }
            }

 

[jmcilhinney]

I look through the alghoritm with debugger

Did you really? So, you set a breakpoint at the top of the code and then you stepped through the code line by line and observed whether, at each step, the code did what you expected it to do? In that case, one of two things must have happened. One possibility is that the code did exactly what you expected at every step. In that case, it's your expectations that are wrong and your expectations that you need to reevaluate. The other possibility is that what actually happened did differ from your expectations somewhere and somehow. In that case, you can tell us exactly where and exactly how. Which is it?

 

[Dragon4ik]

Did you really? So, you set a breakpoint at the top of the code and then you stepped through the code line by line and observed whether, at each step, the code did what you expected it to do? In that case, one of two things must have happened. One possibility is that the code did exactly what you expected at every step. In that case, it's your expectations that are wrong and your expectations that you need to reevaluate. The other possibility is that what actually happened did differ from your expectations somewhere and somehow. In that case, you can tell us exactly where and exactly how. Which is it?

It happens in this block of code:

public static void CopyPixels(this BitmapSource source, PixelColor[,] pixels, int stride, int offset, bool dummy)
        {
            var height = source.PixelHeight;
            var width = source.PixelWidth;
            var pixelBytes = new byte[height * width * 4];
            source.CopyPixels(pixelBytes, stride, 0);
            int y0 = offset / width;
            int x0 = offset - width * y0;
            for (int y = 0; y < height; y++)
                for (int x = 0; x < width; x++)
                    pixels[x + x0, y + y0] = new PixelColor
                    {
                        Blue = pixelBytes[(y * width + x) * 4 + 0],
                        Green = pixelBytes[(y * width + x) * 4 + 1],
                        Red = pixelBytes[(y * width + x) * 4 + 2],
                        Alpha = pixelBytes[(y * width + x) * 4 + 3],
                    };
        }

It returns array of cropped image's pixels, and then it sends this result to function GetDifference():

private double GetDifference(PixelColor first, PixelColor second)
        {
            int dr = Math.Abs(first.Red - second.Red);
            int dg = Math.Abs(first.Green - second.Green);
            int db = Math.Abs(first.Blue - second.Blue);
            int da = Math.Abs(first.Alpha - second.Alpha);

            return Math.Sqrt(dr * dr + dg * dg + db * db );
        }

And when it calculate the difference, it sees that the RIGHT variant will have "worse" pixels every time, than other. And i can't get, why it works so: maybe it gets pixels not in the right way, or slicing alghoritm makes too big gap between the neighbor fragments and it causes the mistake in calculations.

I know my answer is still incomplete, but i hope this information will give you enough information. Thank you for your attention!