在NxM國際象棋棋盤上放置皇后

練習中，我已經開始解決interviewstreet問題。我在車上遇到這個皇后問題。上板在NxM國際象棋棋盤上放置皇后

皇后（50分）

你必須在其上一些方形阻擋在外的N * M個棋盤。您可以在棋盤上放置一個或多個皇后的方式有多少種方式，以避免兩名皇后互相攻擊？兩個皇后互相攻擊，如果一個人可以通過水平，垂直或對角線移動到另一個皇后而不通過任何方格。至多有一個皇后可以放在廣場上。女王不能被放置在被遮擋的廣場上。

輸入：第一行包含T測試用例後面的測試用例數。每個測試用例在第一行包含整數N和M.以下N行包含每個代表電路板的M個字符。 '＃'代表一個被遮擋的正方形和一個'。'代表一個暢通無阻的廣場。

輸出：輸出包含每個測試用例所需答案的T行。由於答案可真大，它們輸出模1000000007.

https://www.interviewstreet.com/challenges/dashboard/#problem/4e904d63c5069

我想知道什麼是解決這一問題的最佳算法？

謝謝。

來源

2013-01-25 Manas Paldhe

可能重複[N-Queens問題..我們可以走多遠？]（http://stackoverflow.com/questions/1863531/n-queens-problem-how-far-can-we-go）和[N皇后放置算法]（http://stackoverflow.com/q/11476500/62576） –

This page provides an easy to follow implementation of the N-Queens problem。如果你想找到所有的排列，在nQueenProblem方法中，而不是使用簡單的，只需使用for循環迭代不同的值。而不是返回正確的電路板，只需計算電路板。

來源

2013-01-25 00:45:29 kasavbere

這是一個蠻力方法，需要大量的時間。我正在尋找更快的算法。謝謝。 –

@ManasPaldhe根據維基百科（http://en.wikipedia.org/wiki/Eight_queens_puzzle#Counting_solutions），「目前還沒有解決方案確切數量的已知公式。」也許其他人擁有比我更快的替代方案能夠爲你找到。 – kasavbere

在這個特定的問題中有一些限制，有一些「阻塞」的方塊 –

在NxM國際象棋棋盤上放置皇后

回答

相關問題