棋盘问题：
题目链接：https://vjudge.net/problem/POJ-1321
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input：
输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output：
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
简单的回溯搜索（类似经典的八皇后问题）。
这题要得到方案数，因为找不到任何规律，所以只能去枚举所有可行的情况，并统计个数。而通过搜索来枚举是一种比较高效的办法。
1）首先建立全局的数组来存放棋盘：
int chessboard[10][10]; //0表示不能放棋子 1表示可以 2表示已经放了棋子棋盘上的点显然有三种可能的状态：
①不能放棋子（即空白区域）
②可以放棋子
③可以放棋子但已经放过棋子了
分别用0，1，2记录棋盘上点的状态
2）写一个check函数来判断某个棋盘上的点能不能放棋子
因为数据量较小，直接遍历整个棋盘看看有没有同一行或者同一列的棋子
bool check(int row,int column){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((row==i&&chessboard[i][j]==2)||(column==j&&chessboard[i][j]==2)) return 0; return 1; }接着就是递归回溯。
第一个变量row的设置目的是按序搜索以避免答案重复
第二个变量step是为了记录已经放置了几颗棋子，当放了k个就结束搜索，答案++
关于回溯，我是这么理解的：
由于递归函数的性质，当向下一层继续深搜时，函数会“放下”当前的函数，先继续往下一层深搜，等到下一层搜索完毕之后再回到当前的函数。
以这道题为例，我们选择一个地方放置棋子，要对其进行标记，然后向下一层深搜。回溯的意思就是，当返回到当前函数后，解除这个标记。因为递归函数写在for循环的内部，解除该标记后就可以去尝试该行的下一个位置了。
void dfs(int row,int step){ if(step==k){ C++; return ; } else{ for(int i=row;i<=n;i++) for(int j=1;j<=n;j++){ if(check(i,j)&&chessboard[i][j]!=0){ chessboard[i][j]=2; dfs(i+1,step+1); chessboard[i][j]=1;//回溯 } } } }下附AC代码：
#include <cstdio> using namespace std; int n,k; int chessboard[10][10]; //0表示不能放棋子 1表示可以 2表示已经放了棋子 int C; bool check(int row,int column){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((row==i&&chessboard[i][j]==2)||(column==j&&chessboard[i][j]==2)) return 0; return 1; } void dfs(int row,int step){ if(step==k){ C++; return ; } else{ for(int i=row;i<=n;i++) for(int j=1;j<=n;j++){ if(check(i,j)&&chessboard[i][j]!=0){ chessboard[i][j]=2; dfs(i+1,step+1); chessboard[i][j]=1; } } } } int main() { while(~scanf("%d %d",&n,&k)){ if(k==-1&&n==-1) break; C=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ char temp; scanf(" %c",&temp); if(temp=='#') chessboard[i][j]=1; else chessboard[i][j]=0; } dfs(1,0); printf("%d\n",C); } return 0; }