在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国际象棋棋盘上放置皇后

回答

相关问题