using System.Text;

using static System.Math;

class GameField
{
    private int[,] _cells;

    public GameField(int[,] cells)
    {
        _cells = cells;
    }

    public static GameField Generate(int size)
    {
        var cells = new int[size, size];
        var variants = new List<int>(size * size - 1);
        var random = new Random();

        for (int i = 0; i < size * size - 1; i++)
        {
            variants.Add(i + 1);
        }

        for (int i = 0; i < size * size - 1; i++)
        {
            var y = i % size;
            var x = i / size;
            var variant = random.Next(0, variants.Count);
            cells[x, y] = variants[variant];
            variants.RemoveAt(variant);
        }

        var field = new GameField(cells);

        if(!field.IsResolvable())
        {
            if(size == 2)
                (cells[size - 1, size - 2], cells[size - 2, size - 1]) = (cells[size - 2, size - 1], cells[size - 1, size - 2]);
            else
                (cells[size - 1, size - 2], cells[size - 1, size - 3]) = (cells[size - 1, size - 3], cells[size - 1, size - 2]);
        }

        return field;
    }

    public bool IsResolvable()
    {
        var evenness = 0;
        for (int i = 0; i < _cells.Length - 1; i++)
        {
            var y1 = i % _cells.GetLength(0);
            var x1 = i / _cells.GetLength(1);

            for (int j = i + 1; j < _cells.Length - 1; j++)
            {
                var y2 = j % _cells.GetLength(0);
                var x2 = j / _cells.GetLength(1);
                if (_cells[x1, y1] > _cells[x2, y2])
                    evenness++;
            }
        }
        return (evenness & 1) == 0;
    }

    public int GetHeuristics()
    {
        var heuristics = 0;
        for(int i = 0; i < _cells.Length - 1; i++)
        {
            var y1 = i % _cells.GetLength(0);
            var x1 = i / _cells.GetLength(1);

            var value = _cells[x1, y1] - 1;

            var y2 = value % _cells.GetLength(0);
            var x2 = value / _cells.GetLength(1);

            heuristics += Abs(x1 - x2) + Abs(y1 - y2);
        }
        return heuristics;
    }

    public override string ToString()
    {
        var result = new StringBuilder();
        for (int i = 0; i < _cells.GetLength(0); i++)
        {
            for (int j = 0; j < _cells.GetLength(1); j++)
            {
                result.Append($"\t{_cells[i, j]}\t");
            }
            result.Append("\n");
        }
        return result.ToString();
    }
}