N-Queens算法。劇情扭曲：女王也是騎士

Question

試圖在N*N板上修改騎士運動套裝的N-Queens算法。在我的情況下，我正在使用4*4和8*8板進行測試。

我的算法，我的遞歸失敗處理騎士，因爲它有時需要跳過一行。如果只是Queens的運動，則不需要跳過行，因爲每行的女王號確切爲1。

問題出在我的Solve()函數中，因爲我的遞歸關係與皇后的數量有關。通常每塊板的皇后數量應該是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

是的，這變得更加困難。您需要對前面的問題進行一些修改，這使得這是一個有價值的編程練習。

1. 保持計數您放置了多少個皇后。
2. 允許跳過一行：不放置女王不是失敗;你根本不需要更新計數。
3. 您需要保留迄今爲止發現的最佳解決方案（最大數量的皇后），並繼續前進，直到您將第一個皇后跑過中途點。

請注意，你做不是必須允許在第一行沒有皇后。如果在第一行有一個沒有皇后的解決方案，那麼有一個對應的解決方案，只有一個皇后，只移動一行。

這足以讓你感動嗎？