众所不知，rly现在不会玩国际象棋。但是，作为一个OIer，rly当然做过八皇后问题。这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在n*n的方格中摆n个皇后使其互不攻击到，求不同的解的数量，这就是经典的n皇后问题。现在问题推广到n皇后问题，这个问题对于你而言实在是小菜一叠。但因为上一次rly把棋盘弄破了，又拿不出新的，所以rly打算难一点点，问题就是破棋盘上的n皇后问题。他想知道……（你们懂的）。

棋子都是相同的。

一行，一个正整数N。

接下来N行，每行N个数，要么为0，表示没坏，要么1，表示坏了。

N<=16

一行，输出不同的解的数量。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,map[22][22],ans;

int viscol[50],vis1[50],vis2[50];

void dfs(int row) {

	if(row==n+1) {ans++; return ;}

	int i;

	for(i=1;i<=n;i++) {

		if(!map[row][i]&&!viscol[i]&&!vis1[row-i+16]&&!vis2[row+i]) {

			viscol[i]=vis1[row-i+16]=vis2[row+i]=1;

			dfs(row+1);

			viscol[i]=vis1[row-i+16]=vis2[row+i]=0;

		}

	}

}

int main() {

	scanf("%d",&n);

	int i,j;

	for(i=1;i<=n;i++) {

		for(j=1;j<=n;j++) {

			scanf("%d",&map[i][j]);

		}

	}

	dfs(1);

	printf("%d\n",ans);

}