删除最少数量的国际象棋骑士，这样剩下的骑士就不会威胁到另一个骑士

Question

我很难想出骑士游戏任务的算法。

任务描述为：

骑士游戏是在一个尺寸为 N x N 的棋盘上进行的，棋盘上有很多 0 <= K <= N² 的国际象棋骑士。

我收到一个棋盘（字符矩阵），其中 'K' 表示骑士，'0' 表示空单元格。我的任务是移除最少的骑士，这样就不会剩下可以攻击另一个骑士的骑士了。在第一行，我收到了板的 N 尺寸。在接下来的 N 行中，我收到带有 Ks 和 0s 的字符串。

这是我到目前为止的设计：

public class SolutionTwo
{
    public static void Main()
    {
        var size = int.Parse(Console.ReadLine());

        var board = new char[size][];
        PrepareBoard(board);

        var knights = new List<Knight>();

        for (int x = 0; x < board.Length; x++)
        {
            for (int y = 0; y < board[x].Length; y++)
            {
                if (board[x][y] == 'K')
                {
                    knights.Add(new Knight()
                    {
                        X = x,
                        Y = y,
                        KnightAttacks = GetKnightAttacks(x, y, board)
                    });
                }
            }
        }

        var count = 0;

        foreach (var knight in knights.OrderByDescending(k => k.KnightAttacks.Count()))
        {
            if (!IsReaminingHits(board))
            {
                break;
            }

            board[knight.X][knight.Y] = '0';
            count++;

            foreach (var subK in knight.KnightAttacks)
            {
                var c = knights.Single(k => k.X == subK.Item1 && k.Y == subK.Item2);

                c.KnightAttacks.Remove(new Tuple<int, int>(knight.X, knight.Y));
            }

            // for test purposes
            //Console.WriteLine($"Kn: [{knight.X} {knight.Y}] - he attacks: {string.Join(" ", knight.KnightAttacks)} {knight.KnightAttacks.Count()}");
        }

        Console.WriteLine(count);
    }

    private static bool IsReaminingHits(char[][] board)
    {
        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[i].Length; j++)
            {
                if (board[i][j] == 'K')
                {
                    if (GetKnightAttacks(i, j, board).Count > 0)
                    {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private static void PrepareBoard(char[][] board)
    {
        for (int i = 0; i < board.Length; i++)
        {
            board[i] = Console.ReadLine()
                .ToCharArray();
        }
    }

    private static List<Tuple<int, int>> GetKnightAttacks(int x, int y, char[][] board)
    {
        var deltas = new int[8][]
        {
            new int[] {-2, -1},
            new int[] {-2, +1},
            new int[] {+2, -1},
            new int[] {+2, +1},
            new int[] {-1, -2},
            new int[] {-1, +2},
            new int[] {+1, -2},
            new int[] {+1, +2}
        };

        var xCandidate = 0;
        var yCandidate = 0;

        var list = new List<Tuple<int, int>>();

        for (int i = 0; i < 8; i++)
        {
            xCandidate = x + deltas[i][0];
            yCandidate = y + deltas[i][1];

            if (0 <= xCandidate && xCandidate < board.Length
                && 0 <= yCandidate && yCandidate < board[0].Length
                && board[xCandidate][yCandidate] == 'K')
            {
                list.Add(new Tuple<int, int>(xCandidate, yCandidate));
            }
        }

        return list;
    }
}

public class Knight
{
    public int X { get; set; }

    public int Y { get; set; }

    public List<Tuple<int, int>> KnightAttacks { get; set; } = new List<Tuple<int, int>>();
}

示例 #1：

输入：

5 
0K0K0
K000K
00K00
K000K 
0K0K0

预期结果：1

示例 #2：

输入：

8
0K0KKK00
0K00KKKK
00K0000K
KKKKKK0K
K0K0000K
KK00000K
00K0K000
000K00KK

预期结果：12

Answer 1

算法有缺陷，在这个较小的板上更容易看出：

这里的解应该是2；但是算法 returns 3. 这样做的原因是算法去掉了攻击次数最多的 first 骑士；假设此删除是正确答案的一部分；但是，这个攻击次数的骑士可能有多个，第一个不一定是最好的选择。

此外 knights.OrderByDescending(k => k.KnightAttacks.Count()) 不会执行您希望它执行的操作，即使您在循环内添加 knight.KnightAttacks.Clear(); 也是如此，因为它必须评估所有值才能枚举它们；但当然这些数字会随着您开始移除骑士而变化。

正确的算法需要尝试所有具有相同攻击次数的备选方案，以找出最佳方案。我还可以想出攻击次数最多的骑士不是最佳选择的场景。例如：

因此，使用以下代码替换 var count=0; 开头的代码可以稍微改进算法（例如，我的小示例得到正确答案 2，"Example #2" 得到正确答案 12）；但不是完整的解决方案：

var count = 0;
while (knights.Any(k => k.KnightAttacks.Count > 0))
{
    var knight = knights.OrderByDescending(k => k.KnightAttacks.Count).First();

    // for test purposes
    //Console.WriteLine($"Kn: [{knight.X} {knight.Y}] - he attacks: {string.Join(" ", knight.KnightAttacks)} {knight.KnightAttacks.Count()}");

    board[knight.X][knight.Y] = '0';
    count++;

    foreach (var subK in knight.KnightAttacks)
    {
        var c = knights.Single(k => k.X == subK.Item1 && k.Y == subK.Item2);

        c.KnightAttacks.Remove(new Tuple<int, int>(knight.X, knight.Y));
    }
    knight.KnightAttacks.Clear();
}

删除最少数量的国际象棋骑士，这样剩下的骑士就不会威胁到另一个骑士

Remove minimum amount of chess knights so no remaining knight threatens another knight

c#

algorithm

chess

示例 #1：

示例 #2：