Emmm，我又来 POJ 了，这题感觉比上次做的简单点。类似皇后问题。但是稍微做了一点变形，比如棋子数量是不定的。棋盘形状不在是方形等等。
题目链接：POJ 1321 棋盘问题
解题思路
基本思路：从上往下放旗子，每种情况完成后，复盘继续下一种情况。
这里讲一下，void backTrack(int left, int x) 函数。
left 表示还剩的棋子数量，显然如果 left 为 0，说明所有棋子已放完，那么方案数 solution 加 1。
如果不为 0。那么继续检查当前位置的列是否有棋子，如果无棋子，那么当前位置可以放旗子。然后继续递归，棋子数量减 1，行数加 1。如果有棋子，那么悔棋 1 步。继续下一个位置。
C代码
/**
* @author wowpH
* @date 2019-9-14 19:54:16
*/
#include<stdio.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define MAX_N 8 // 矩阵最大为8
#define BOARD TRUE // 棋盘
#define BLANK FALSE // 空白
int matrix[MAX_N][MAX_N];// 矩阵，BOARD表示棋盘，BLANK表示空白
int n, k, solution;// solution最终结果
int column[MAX_N];// 每列是否有棋子，TRUE表示有棋子，FALSE表示无棋子
void backTrack(int left, int x) {// 回溯，left表示剩余棋子，x表示当前行
if (left == 0) {// 无多余棋子
++solution; // 方案数加1
return;
}
// 遍历x行及下方的棋盘
for (int i = x; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == BLANK) {// 空白
continue; // 不能放旗子
}
if (column[j] == TRUE) {// 第j列有棋子
continue; // 不能放旗子
}
column[j] = TRUE; // 当前位置可以放子，设为TRUE
backTrack(left - 1, i + 1); // 回溯，棋子数减1，行数加1
column[j] = FALSE; // 复盘，设为无子
}
}
}
int main() {
while (scanf("%d %d", &n, &k) && n != -1 && k != -1) {
getchar();// '\n'
// 输入棋盘
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char ch = getchar();
if (ch == '.') {
matrix[i][j] = BLANK;// 空白
} else if (ch == '#') {
matrix[i][j] = BOARD;// 棋盘
}
}
getchar();// '\n'
}
// 初始化
memset(column, FALSE, sizeof(column));
solution = 0;
backTrack(k, 0);// 回溯
printf("%d\n", solution);
}
return 0;
}