求二维数组最大和
有一个n*n的二维数组(n >= 2)，以n=3为例
9 8 6
8 6 4
5 6 3
其中每一列为降序排列
现在在数组中取n个数，求取出数的最大和
要求取出的这些数两两不能在同一行或者是同一列

示例应该输出
a[0][2] + a[1][0] + a[2][1] = 6 + 8 + 6 = 20

求一个解决思路

[解决办法]
还是一样，正常解其实还是“笛卡尔积”连出全排列，在去除不和判定条件的东西，不过效率低点

最优解的化，则类似8皇后问题，利用“贪婪回溯”可以完成


[解决办法]

C# code

using System;using System.Collections.Generic;using System.Diagnostics;using System.Linq;using System.Text;namespace ConsoleApplication1{    class Program    {        static void Main(string[] args)        {            int[,] data = new int[,]            {                { 9, 8, 6 },                { 8, 6, 4 },                { 5, 6, 3 }            };            Debug.Assert(data.GetLength(0) == data.GetLength(1));            var query = Arrange(Enumerable.Range(0, data.GetLength(0)).Select(x => x).ToList(), new List<int>())                .Select(x => x.Select((y, i) => data[i, y]).Sum()).Max();            Console.WriteLine(query);        }        static IEnumerable<List<T>> Arrange<T>(List<T> source, List<T> current)        {            if (current.Count == source.Count)            {                yield return current;            }            else            {                foreach (var item in source)                {                    if (!current.Any(x => x.Equals(item)))                    {                        foreach (var item1 in Arrange(source, current.Union(new List<T>() { item }).ToList()))                        {                            yield return item1;                        }                    }                }            }        }    }}
[解决办法]
C# code
public struct Cell    {        public int col;        public int row;        public int value;    }        static Stack<Cell> stack = new Stack<Cell>();    static int colnum = 3;    static int maxValue = 0;        static int[,] data = {{9,8,6},{8,6,4},{5,6,3}};            public static void RunSnippet()    {                for(int i = 0; i < colnum; i ++)        {            Cell cell = new Cell();                cell.row = 0;                cell.col = i;                cell.value = data[0,i];                SumMax(cell);                stack.Pop();        }        WL(maxValue);                }        public static void SumMax(Cell cell)    {        stack.Push(cell);        if (!Check())            return;                int row = cell.row + 1;                if (row < colnum)        {            for(int i = 0; i < colnum; i++)            {                Cell next = new Cell();                next.row = row;                next.col = i;                next.value = data[row,i];                SumMax(next);                stack.Pop();            }        }        else        {            int cMax = 0;            foreach ( Cell c in stack )            {                cMax += c.value;            }                        if (cMax > maxValue)            {                maxValue = cMax;            }        }    }        public static bool Check()    {        bool rtn = true;        foreach ( Cell c in stack )        {            foreach ( Cell c2 in stack )            {                    if (c.col == c2.col && c.row == c2.row)                {                    continue;                }                else                {                    if (c.col == c2.col)                    {                        rtn = false;                        return rtn;                    }                }            }        }        return rtn;    }