具體問題描述為：在M列N行的棋盤上放置3個Q，如何確定沒有兩個Q處于進攻位置的方式數？
請注意，M 不等于 N，并且 M/NInteger在 C 語言中比 a 大，因此無法使用經典計算機演算法（如 DFS/BFS）（出于時間和記憶體復雜性考慮）來解決此問題。
我猜這個問題可以通過排列或組合的數學方法來計算，但我不擅長數學，所以，請幫助我。
uj5u.com熱心網友回復：
簡單的答案是包含/排除。
我們首先計算按順序放置 3 個皇后的方法的數量。這只是(n*m) * (n*m - 1) * (n*m - 2).
現在我們已經高估了，因為我們不想要在皇后 1,2 攻擊的情況下放置 3 個皇后的方法數量的計數。或皇后 1,3。或皇后 2,3。但是，這是剛剛超過行，列和長度的對角線之和l的l * (l-1) * (m*n-2)。
但是現在我們低估了，因為如果所有 3 個皇后都互相攻擊，那么我們在第一步中將它們相加，在第二步中減去 3x，現在我們需要將它們加回 2x 以計算那些 0 次。這比行，列和長度的對角線之和l的l * (l-1) * (l-2)。
但這是將所有皇后按順序排列的方法數。但是鑒于棋盤上有 3 個皇后，我們可以下 6 個訂單。所以將整個答案除以 6。
這可以變成一個O(n m)要運行的程式。這對于您的目的來說應該足夠快。如果你愿意做更多的分析，我們實際上可以產生一個O(1)公式。
uj5u.com熱心網友回復：
帶有坐標的欄位(i, j)對于位于(qi , qj)if的皇后來說是脆弱的
i == qi || j == qj || abs(i - j) == abs(qi - qj)
這個布爾運算式應該false用于每個皇后的可行坐標。找到三個這樣的欄位應該不難。可以嘗試o(M * N)在最壞情況下具有復雜性的 Monte Carlo 方法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/357741.html