为了练习，我已经开始解决街头面试问题。我发现了这个皇后在船上的问题。
船上皇后区（50 分）
你有一个 N * M 棋盘，上面有一些方格被挡住了。你有多少种方法可以在棋盘上放置一个或多个皇后，使得没有两个皇后相互攻击？如果一个皇后可以通过水平、垂直或对角线移动而不经过任何被阻挡的方格而到达另一个皇后，则两个皇后会互相攻击。最多一个皇后可以放在一个正方形上。皇后不能放在被阻挡的方格上。
输入：第一行包含测试用例 T 的数量。接下来是 T 测试用例。每个测试用例的第一行包含整数 N 和 M。接下来的 N 行包含 M 个字符，每个字符代表棋盘。'#' 代表一个被阻挡的正方形和一个 '.' 表示一个未阻塞的正方形。
输出：输出包含每个测试用例所需答案的 T 行。由于答案可能非常大，因此以 1000000007 为模输出它们。
https://www.interviewstreet.com/challenges/dashboard/#problem/4e904d63c5069
我想知道解决这个问题的最佳算法是什么？
谢谢你。