c# - N皇后算法。情节扭曲 : The Queen is a Knight too

Question

尝试在 N*N 棋盘上修改骑士运动集的 N-Queens 算法。在我的例子中，我在 4*4 和 8*8 板上测试它。

我的算法，resp。我的递归无法处理骑士，因为它有时需要跳过一行。如果只是皇后移动，则不需要跳过行，因为每行恰好有 1 个皇后。

问题出在我的 Solve() 函数中，因为我的递归与皇后区的数量有关。通常每 block 棋盘的皇后数应为 8。然而，结合骑士运动将数量减少到 6。因此，我认为递归的深度不够(只有 6 行深，而不是 8 行)。

例如，4*4 板上的解决方案是 (1,1) 和 (4,2) (行*列)。但它不能跳过第 2 行和第 3 行。

如何使递归遍历所有行，同时能够跳过一些行。

    static int[] board = new int[9];
    static int cnt = 0;

    static bool CanPlace(int row, int col) // eg. x[1] = 2, 1st row 2nd col has a Queen
    {            
        for (int j = 1; j <= (row - 1); j++)
        {               
            if (board[j] == col || Math.Abs(board[j] - col) == Math.Abs(j - row)) return false;
            if ((Math.Abs(board[j] - col) - 1)  ==  Math.Abs(j - row)) return false;                
            //The line of code above should work for all of the possible moves of the Knight. 
            //At least it does for a 4x4 board, for the first two lines. 
            //Giving a pair of results = (1,1)(2,4) and the mirror (1,4)(2,1)
        }
        return true;
    }

    static void Solve(int row, int boardSize)
    {
        for (int col = 1; col <= boardSize; col++)
        {
            if (CanPlace(row, col)) //This only triggers 6 times per board
            {
                board[row] = col;
                if (row == boardSize - 2)   // Here i tried to fix it but the bottom rows get sacrificed               
                    PrintBoard();                   
                else
                    Solve(row + 1, boardSize);                   
            }                    
        }        
    }

    static void PrintBoard()
    {
        Console.WriteLine();           
        cnt++;
        for (int i = 1; i <= board.Length-1; i++)
        {
            for (int j = 1; j <= board.Length - 1; j++)               
                if (board[i] == j) Console.Write("Q");                   
                else Console.Write(".");                    
            Console.WriteLine();
        }

        for (int i = 1; i <= board.Length - 1; i++)            
            Console.Write("{0},", board[i]);               

        Console.WriteLine();
    }

    static void Main(string[] args)
    {
        Solve(1, 8);
        Console.WriteLine("\nNumber of solutions: {0}\n",cnt);
    }

Answer 1

是的，这变得更难了。您需要对前面的问题进行一些修改，这使它成为一个有值(value)的编程练习。

1. 记录您放置了多少个皇后。
2. 允许跳过一行:不放置皇后不算失败；你只是不更新​​计数。
3. 您需要保留迄今为止找到的最佳解决方案(最多皇后数)，并继续前进，直到您将第一个皇后运行到中途点。

请注意，您不必允许第一行没有皇后。如果存在第一行没有任何皇后的解，则存在具有相同皇后数的对应解，只是移动了一行。

这足以让您动起来吗？