gistfile1.txt

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MagicSquares
{
    class Program
    {
        static void Main(string[] args)
        {
            Tuple<int, string> data;
            //data = InputData.input4_0;
            //Timed(data);
            //data = InputData.input4_1;
            //Timed(data);
            //data = InputData.input4_2;
            //Timed(data);
            //data = InputData.input6_3;
            //Timed(data);
            //data = InputData.input6_4;
            //Timed(data);
            //data = InputData.input6_5;
            //Timed(data);
            data = InputData.input8_6;
            Timed(data);
            data = InputData.input8_7;
            Timed(data);
            data = InputData.input10_8;
            Timed(data);
            data = InputData.input10_9;
            Timed(data);
            data = InputData.input12_10;
            Timed(data);
            data = InputData.input16_11;
            Timed(data);
        }

        public static void Timed(Tuple<int, string> data)
        {
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            watch.Start();
            Console.WriteLine(Environment.NewLine + data.Item1 +  " Matrix:");
            SquareMatrix solution = new DominoSolver().SolveMagic(data.Item2, data.Item1);
            Console.Write(solution.ToString());
            watch.Stop();
            Console.WriteLine(watch.Elapsed.ToString());
        }
    }

    public class DominoSolver{

        List<Domino> dominolist = new List<Domino>();

        public SquareMatrix SolveMagic(string input, int matrixSize)
        {
            dominolist.Clear();
            ParseDominos(input);
            SquareMatrix sm = new SquareMatrix(matrixSize);
            ArrangeMatrix(sm);
            
            return new GeneticSolver(sm).Solve();
        }

        private void ArrangeMatrix(SquareMatrix sm)
        {
            foreach(var dom in dominolist)
            {
                sm.TryPlace(dom);
            }
        }

        private void ParseDominos(string input)
        {
            foreach (var line in input.Split(new string[] { Environment.NewLine }, StringSplitOptions.None))
            {
                var entries = line.Split(' ');
                int maj = int.Parse(entries[0]);
                int min = int.Parse(entries[1]);
                Domino dom = new Domino()
                {
                    Major = maj,
                    Minor = min
                };
                dominolist.Add(dom);
            }
        }
    }

    public struct Domino
    {
        public int Major;
        public int Minor;

        public int x1, y1;
        public int x2, y2;       

        public bool IsHorizontal()
        {
            return x1 == x2;
        }

        public void RotateRight()
        {
            if (IsHorizontal())
            {
                x2 = x1 - 1;
                y2 = y1;
            }
            else
            {
                x2 = x1;
                y2 = y1 + 1;
            }
        }

        public override string ToString()
        {
            return Major.ToString() + ":" + Minor.ToString() + string.Format("({0},{1})({2},{3})",x1,y1,x2, y2);
        }

        public bool Equals(Domino p)
        {
            // If parameter is null return false:
            if ((object)p == null)
            {
                return false;
            }

            // Return true if the fields match:
            return (x1 == p.x1) && (y1 == p.y1) &&
                   (x2 == p.x2) && (y2 == p.y2) &&
                   (Major == p.Major) && (Minor == p.Minor);
        }

        public static bool operator ==(Domino d1, Domino d2)
        {
            return d1.Equals(d2);
        }

        public static bool operator !=(Domino d1, Domino d2)
        {
            return !d1.Equals(d2);
        }
    }

    public struct MatrixEntry
    {
        public int Value;
        public Domino Piece;

        public MatrixEntry(int value, Domino piece)
        {
            Value = value;
            Piece = piece;
        }
    }

    public class SquareMatrix : ICloneable{
        public readonly int N;
        public readonly int MagicNumber;
        public MatrixEntry[,] Matrix;
        public static readonly Domino ZeroDomino = new Domino();
        public static readonly MatrixEntry ZeroEntry = new MatrixEntry(0, ZeroDomino);

        public SquareMatrix(int n)
        {
            N = n;
            MagicNumber = N * (N * N + 1) / 2;
            Matrix = new MatrixEntry[n,n];
        }

        public bool IsMagic()
        {

            return DiagonalSum() == MagicNumber &&
                   OtherDiagonalSum() == MagicNumber &&
                   ColumnSumLeft() == MagicNumber &&
                   ColumnSumRight() == MagicNumber &&
                   RowSumTop() == MagicNumber &&
                   RowSumBottom() == MagicNumber;
        }

        public int DiagonalSum()
        {
            int sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += Matrix[i, i].Value;
            }
            return sum;
        }

        public int OtherDiagonalSum()
        {
            int sum = 0;
            for (int i = N - 1; i >= 0; i--)
            {
                sum += Matrix[N-1 -i,i].Value;
            }
            return sum;
        }

        public int ColumnSumRight()
        {
            int sum = 0;
            for(int i = 0; i < N; i++)
            {
                sum += Matrix[N - 1, i].Value;
            }
            return sum;
        }

        public int ColumnSumLeft()
        {
            int sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += Matrix[0, i].Value;
            }
            return sum;
        }

        public int RowSumBottom()
        {
            int sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += Matrix[i, N - 1].Value;
            }
            return sum;

        }
        public int RowSumTop()
        {
            int sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += Matrix[i, 0].Value;
            }
            return sum;
        }


        public void Clear()
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    Matrix[i, j].Value = 0;
                    Matrix[i, j].Piece = ZeroDomino;
                }
            }
        }

        public override string ToString()
        {
            string str = "";
            for (int i = 0; i < N; i++)
            {
                for(int j = 0; j < N; j++)
                {
                    str += string.Format("{0,3} ", Matrix[i, j].Value);
                }
                str += Environment.NewLine;
            }

            return str;
        }

        /// <summary>
        /// Will attempt to place a domino, onto the matrix
        /// </summary>
        /// <param name="dom"></param>
        internal bool TryPlace(Domino dom)
        {
            int x, y;
            if (TryFindEmpty(out x, out y))
            {
                if (x + 1 < N && Matrix[x + 1, y].Value == 0)
                {
                    dom.x1 = x;
                    dom.y1 = y;
                    dom.x2 = x + 1;
                    dom.y2 = y;
                    Matrix[x, y] = new MatrixEntry(dom.Major, dom);
                    Matrix[x + 1, y] = new MatrixEntry(dom.Minor, dom);
                    return true;
                }
                else if (y + 1 < N && Matrix[x, y + 1].Value == 0)
                {
                    dom.x1 = x;
                    dom.y1 = y;
                    dom.x2 = x;
                    dom.y2 = y + 1;
                    Matrix[x, y] = new MatrixEntry(dom.Major, dom);
                    Matrix[x, y + 1] = new MatrixEntry(dom.Minor, dom);
                    return true;
                }
            }

            throw new ArgumentOutOfRangeException("Matrix is in an invalid state");
        }

        private bool TryFindEmpty(out int x, out int y)
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (Matrix[i, j].Value == 0)
                    {
                        x = i;
                        y = j;
                        return true;
                    }
                }
            }
            x = -1;
            y = -1;
            return false;            
        }

        //rotates a domino 90 degrees, and deals with the fallout
        internal void Rotate90(int x, int y)
        {
            Domino self = Matrix[x, y].Piece;
            if (self.IsHorizontal())
            {
                if (x - 1 >= 0)
                {
                    TryRotateRight(self);
                }
            }
            else
            {
                if (y + 1 < N)
                {
                    TryRotateRight(self);
                }
            }
            //check if can be rotate right

        }

        private void TryRotateRight(Domino self)
        {
            //world's laziest rotate
            if (self.IsHorizontal())
            {
                Domino neighbor = Matrix[self.x1 - 1, self.y1].Piece;
                Domino neighbor2 = Matrix[self.x2 - 1, self.y2].Piece;
                if (neighbor == neighbor2 && neighbor.IsHorizontal())
                {
                    Remove(neighbor);
                    Remove(self);

                    self.RotateRight();
                    neighbor.RotateRight();

                    UpdateBoard(self);
                    TryPlace(neighbor);
                }
            }
            else
            {
                Domino neighbor = Matrix[self.x1, self.y1 + 1].Piece;
                Domino neighbor2 = Matrix[self.x2, self.y2 + 1].Piece;
                if (neighbor == neighbor2 && !neighbor.IsHorizontal())
                {
                    Remove(neighbor);
                    Remove(self);

                    self.RotateRight();
                    neighbor.RotateRight();
                    UpdateBoard(self);
                    TryPlace(neighbor);
                }
            }

        }

        //rotates a domino 180 degrees
        internal void Rotate180(int x, int y)
        {
            Domino domino = Matrix[x, y].Piece;
            int tmp;
            tmp = domino.x1;
            domino.x1 = domino.x2;
            domino.x2 = tmp;

            tmp = domino.y1;
            domino.y1 = domino.y2;
            domino.y2 = tmp;

            UpdateBoard(domino);
        }

        internal void SwapNeighbor(int x, int y)
        {
            throw new NotImplementedException();
        }

        internal void Swap(int x1, int y1, int x2, int y2)
        {
            Domino piece1 = Matrix[x1, y1].Piece;
            Domino piece2 = Matrix[x2, y2].Piece;

            int tmp;

            tmp = piece1.Major;
            piece1.Major = piece2.Major;
            piece2.Major = tmp;

            tmp = piece1.Minor;
            piece1.Minor = piece2.Minor;
            piece2.Minor = tmp;

            UpdateBoard(piece1);
            UpdateBoard(piece2);
        }

        internal void UpdateBoard(Domino domino)
        {
            Matrix[domino.x1, domino.y1].Value = domino.Major;
            Matrix[domino.x1, domino.y1].Piece = domino;

            Matrix[domino.x2, domino.y2].Value = domino.Minor;
            Matrix[domino.x2, domino.y2].Piece = domino;
        }
        
        internal void Remove(Domino domino)
        {
            Matrix[domino.x1, domino.y1] = ZeroEntry;
            Matrix[domino.x2, domino.y2] = ZeroEntry;
        }

        public object Clone()
        {
            SquareMatrix clone = new SquareMatrix(N);

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    clone.Matrix[i, j] = new MatrixEntry(Matrix[i,j].Value, Matrix[i,j].Piece);
                }
            }

            return clone;
        }
    }

}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MagicSquares
{
    public struct Point
    {
        public int x, y;
    }

    public class GeneticSolver
    {
        private int _matrixSize;
        private int _targetFitness;
        private SquareMatrix _seed;
        private SquareMatrix _currentMatrix;
        private const int _generationSize = 30;
        //private double _fitnessDelta = 0.005;

        public int Generation = 0;
        public const int GenerationCap = 5000000;
        public double AverageFitness = 0; 
        public SortedDictionary<double, SquareMatrix> FittestList =
            new SortedDictionary<double, SquareMatrix>();

        public List<SquareMatrix> Population = new List<SquareMatrix>();
        public List<Point> KeyIndices = new List<Point>(); //premature optimization for 10x10+
        private int _keyIndexSize = 0; //probably optimized by compiler, but w/e

        private Random _rng;


        public GeneticSolver(SquareMatrix seed)
        {
            _rng = new Random(0);
            _seed = seed;
            _matrixSize = _seed.N;
            _targetFitness = _seed.MagicNumber;
            PopulateKeyPoints();
            Seed(seed, 100);
        }

        private void PopulateKeyPoints()
        {
            for (int i = 0; i < _matrixSize; i++)
            {
                KeyIndices.Add(new Point() { x = i, y = 0 });
                KeyIndices.Add(new Point() { x = i, y = _matrixSize - 1 });
            }

            for (int i = 1; i < _matrixSize - 1; i++)
            {
                KeyIndices.Add(new Point() { x = 0, y = i });
                KeyIndices.Add(new Point() { x = _matrixSize - 1, y = i });
            }

            for (int i = 1; i < _matrixSize - 1; i++)
            {
                KeyIndices.Add(new Point() { x = i, y = i });
                KeyIndices.Add(new Point() { x = _matrixSize - 1 - i, y = i });
            }

            _keyIndexSize = KeyIndices.Count;
        }

        public SquareMatrix Solve()
        {
            while (Generation != GenerationCap)
            {
                foreach (var entry in FittestList)
                {
                    if (entry.Value.IsMagic())
                        return entry.Value;
                }

                if (Generation != 0)
                {
                    Populate();
                    MutatePopulation();
                }

                Cull();
                Generation++;
            }
            throw new ArgumentException("Solution not found: Mutate into infinity.");
        }

        private void Cull()
        {
            foreach(var entry in Population)
            {
                double fitness = Fitness(entry);                
                FittestList.Add(fitness + _rng.NextDouble() / 1000, entry);
            }

            while(FittestList.Count > _generationSize)
            {
                FittestList.Remove(FittestList.First().Key);
            }

            double avg = 0;
            foreach(var entry in FittestList.Keys)
            {
                avg += entry;                
            }
            avg /= FittestList.Count;
            //Console.WriteLine("Generation: " + Generation + " Avg. Fitness: " + avg);
        }

        private void MutatePopulation()
        {
            foreach(var entry in Population)
            {
                _currentMatrix = entry;
                Mutate();
            }
        }

        public void Mutate()
        {
            if (_rng.NextDouble() >= .5)
                Swap();
            else
                Rotate();
        }

        private void Populate()
        {            
            Population.Clear();
            //clone the fittest members && keep the fittest pure from mutation
            foreach(var entry in FittestList.Values)
            {
                Population.Add((SquareMatrix)entry.Clone());
            }
            //while (FittestList.Count > _generationSize - 10) //yay extinction?
            //{
            //    FittestList.Remove(FittestList.First().Key);
            //}

            //Subject Fittest and Least Fittest to random mutation instead of original seed.
            if (FittestList.Count > 0)
            {
                Seed(FittestList.First().Value, 20);
                Seed(FittestList.Last().Value, 20);
            }
        }

        private void Seed(SquareMatrix template, int n)
        {
            for (int i = 0; i < n; i++)
            {
                SquareMatrix newseed = (SquareMatrix)template.Clone();
                int operation = _rng.Next(_matrixSize);
                _currentMatrix = newseed;
                while (operation-- > 0)
                {
                    Mutate();
                }

                Population.Add(newseed);
            }       
        }

        public double Fitness(SquareMatrix _currentMatrix)
        {
            int diagSum1 = _currentMatrix.DiagonalSum();
            int diagSum2 = _currentMatrix.OtherDiagonalSum();
            int top = _currentMatrix.RowSumTop();
            int bot = _currentMatrix.RowSumBottom();
            int left = _currentMatrix.ColumnSumLeft();
            int right = _currentMatrix.ColumnSumRight();

            //int target = _targetFitness;
            //double avgsum = (diagSum1 + diagSum2 + top + bot + left + right) / 6.0;
            //double penalty = Math.Pow(
            //                Math.Abs(diagSum1 - diagSum2) +
            //                Math.Abs(top - bot) +
            //                Math.Abs(left - right), 2);
            return 0 - Math.Pow(_targetFitness - diagSum1, 2) -
                       Math.Pow(_targetFitness - diagSum2, 2) -
                       Math.Pow(_targetFitness - top, 2) -
                       Math.Pow(_targetFitness - left, 2) -
                       Math.Pow(_targetFitness - right, 2) -
                       Math.Pow(_targetFitness - bot, 2);

            //return target - avgsum - penalty;
        }

        #region GeneticOperations

        private void Swap() {
            Point swap = KeyIndices[_rng.Next(_keyIndexSize)];
            _currentMatrix.Swap(swap.x, swap.y,
                                _rng.Next(_matrixSize), _rng.Next(_matrixSize));
        }

        private void Rotate() {
            if (_rng.NextDouble() > .5)
                Rotate90();
            else
                Rotate180();
        }
        private void Rotate90() {
            Point p = KeyIndices[_rng.Next(_keyIndexSize)];
            _currentMatrix.Rotate90(p.x, p.y);
        }
        private void Rotate180() {
            Point p = KeyIndices[_rng.Next(_keyIndexSize)];
            _currentMatrix.Rotate180(p.x, p.y);
        }

        #endregion

        //fitness measured as the sum of both diagonals.

        //supported ops
        //swap .5, rotate .5
        //neighbor swap = .8, random swap = .2
        //rotate 90 = .5, 180 = .5

        //number of ops: ceil(target - AverageFitness) + 1
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MagicSquares
{
    public static class InputData
    {
        public static Tuple<int, string> input4_0 = Tuple.Create<int, string>(
            4, @"1 7
2 8
3 13
4 6
5 11
9 15
10 16
12 14");

        public static Tuple<int, string> input4_1 = Tuple.Create<int, string>(
    4, @"1 8
2 13
3 14
4 7
5 11
6 12
9 16
10 15");

        public static Tuple<int, string> input4_2 = Tuple.Create<int, string>(
4, @"1 14
2 8
3 13
4 15
5 11
6 9
7 12
10 16");

        public static Tuple<int, string> input6_3 = Tuple.Create<int, string>(
6, @"1 33
2 20
3 32
4 22
5 14
6 35
7 25
8 19
9 18
10 26
11 31
12 16
13 29
15 17
21 34
23 30
24 28
27 36");

        public static Tuple<int, string> input6_4 = Tuple.Create<int, string>(
6, @"1 10
2 18
3 31
4 11
5 23
6 15
7 20
8 24
9 36
12 16
13 21
14 34
17 33
19 28
22 30
25 29
26 35
27 32");

        public static Tuple<int, string> input6_5 = Tuple.Create<int, string>(
6, @"1 19
2 34
3 25
4 17
5 9
6 10
7 20
8 24
11 31
12 26
13 21
14 30
15 35
16 33
18 22
23 32
27 28
29 36");

        public static Tuple<int, string> input8_6 = Tuple.Create<int, string>(
8, @"1 40
2 51
3 62
4 35
5 60
6 16
7 37
8 57
9 61
10 50
11 52
12 41
13 25
14 55
15 46
17 47
18 33
19 22
20 38
21 23
24 53
26 58
27 54
28 42
29 45
30 49
31 39
32 36
34 59
43 64
44 56
48 63");

        public static Tuple<int, string> input8_7 = Tuple.Create<int, string>(
8, @"1 17
2 41
3 28
4 31
5 51
6 63
7 64
8 58
9 57
10 15
11 52
12 30
13 44
14 56
16 38
18 39
19 54
20 49
21 32
22 46
23 59
24 62
25 35
26 37
27 47
29 45
33 60
34 42
36 50
40 43
48 55
53 61");

        public static Tuple<int, string> input10_8 = Tuple.Create<int, string>(
10, @"1 82
2 8
3 40
4 95
5 64
6 24
7 39
9 28
10 17
11 18
12 94
13 76
14 98
15 16
19 100
20 70
21 77
22 47
23 57
25 52
26 44
27 61
29 45
30 81
31 63
32 91
33 74
34 50
35 86
36 92
37 49
38 88
41 66
42 51
43 75
46 85
48 54
53 84
55 80
56 79
58 71
59 90
60 67
62 69
65 78
68 87
72 97
73 89
83 96
93 99");

        public static Tuple<int, string> input10_9 = Tuple.Create<int, string>(
10, @"1 17
2 93
3 96
4 6
5 74
7 80
8 71
9 36
10 67
11 34
12 99
13 81
14 20
15 78
16 97
18 100
19 76
21 83
22 66
23 79
24 62
25 50
26 32
27 43
28 40
29 98
30 56
31 63
33 89
35 53
37 69
38 95
39 57
41 65
42 60
44 51
45 47
46 94
48 82
49 55
52 77
54 72
58 64
59 84
61 86
68 75
70 88
73 92
85 87
90 91");
        public static Tuple<int, string> input12_10 = Tuple.Create<int, string>(
12, @"1 55
2 20
3 104
4 140
5 73
6 7
8 24
9 88
10 37
11 76
12 137
13 119
14 54
15 43
16 75
17 95
18 41
19 143
21 77
22 51
23 98
25 129
26 111
27 135
28 138
29 52
30 91
31 78
32 139
33 123
34 105
35 121
36 94
38 99
39 71
40 58
42 116
44 113
45 59
46 108
47 102
48 69
49 81
50 83
53 133
56 67
57 141
60 61
62 122
63 80
64 92
65 106
66 90
68 131
70 103
72 142
74 97
79 85
82 93
84 134
86 101
87 112
89 120
96 118
100 128
107 115
109 110
114 132
117 144
124 126
125 127
130 136");

        public static Tuple<int, string> input16_11 = Tuple.Create<int, string>(
16, @"1 50
2 149
3 14
4 243
5 115
6 135
7 84
8 192
9 167
10 201
11 252
12 219
13 82
15 158
16 111
17 74
18 93
19 52
20 98
21 230
22 35
23 162
24 30
25 136
26 176
27 123
28 211
29 62
31 249
32 157
33 138
34 255
36 250
37 54
38 96
39 113
40 205
41 127
42 159
43 231
44 210
45 46
47 183
48 72
49 121
51 173
53 147
55 142
56 65
57 61
58 90
59 161
60 70
63 92
64 160
66 122
67 221
68 247
69 216
71 193
73 222
75 170
76 166
77 225
78 144
79 175
80 178
81 185
83 215
85 154
86 100
87 234
88 109
89 177
91 151
94 140
95 164
97 240
99 152
101 102
103 232
104 105
106 169
107 251
108 131
110 141
112 171
114 254
116 209
117 235
118 229
119 182
120 206
124 217
125 223
126 197
128 156
129 198
130 220
132 148
133 244
134 155
137 228
139 194
143 207
145 199
146 236
150 172
153 241
163 208
165 213
168 203
174 181
179 233
180 246
184 214
186 253
187 218
188 202
189 237
190 212
191 242
195 204
196 239
200 245
224 226
227 256
238 248");

    }
}