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

I have trouble coming up with an algorithm for Knight Game task.

The description of the task is:

The knight game is played on a board with dimensions N x N and a lot of chess knights 0 <= K <= N².

I receive a board (char matrix) with 'K' for knights and '0' for empty cells. My task is to remove a minimum of the knights, so there will be no knights left that can attack another knight. On the first line, I receive the N size of the board. On the next N lines I receive strings with Ks and 0s.

This is what I devised so far:

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>>();
}

Example #1:

Input:

5 
0K0K0
K000K
00K00
K000K 
0K0K0

Expected result: 1

Example #2:

Input:

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

Expected result: 12

Solution

The algorithm is flawed, as can be seen more easily on this smaller board:

The solution here should be 2; but the algorithm returns 3. The reason for this is that the algorithm removes the first knight with the most attacks; assuming that this removal is part of the correct answer; however, there may be multiple knights with that number of attacks, and the first is not necessarily the best choice.

Also knights.OrderByDescending(k => k.KnightAttacks.Count()) doesn't do what you want it to do, even if you add knight.KnightAttacks.Clear(); inside the loop, since it has to evaluate all the values in order to enumerate them; but of course those numbers will vary as you start removing knights.

The correct algorithm is going to need to try all of the alternatives with the same number of attacks, to work out which is best. I can also come up with scenarios where the knight-with-the-most-attacks is not be the best choice. For example:

So using the following replacement for the code beginning var count=0; improves the algorithm a little (e.g. it gets the correct answer of 2 for my small example, and 12 for "Example #2"); but isn't the full solution:

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();
}