Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Problem description

Given an n by n board, there are some positions on the board where the queen cannot be placed. Now you put n black queens and n white queens on the board so that no two black queens are on the same row, column, or diagonal, and no two white Queens are on the same row, column, or diagonal. How many different ways are there? N is less than or equal to 8. Input format The first line of input is an integer n, representing the size of the checkerboard. The next n rows have n integers of 0 or 1. If an integer is 1, it indicates that the corresponding position can be put into the queen. If an integer is 0, it indicates that the corresponding position can not be put into the queen. Output format The output is an integer that indicates how many formats there are.

The sample input

4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1Copy the code

Example Output 2 Example input

1 1 1 1 1 1 1 1 1 1 1 1 1Copy the code

Example output 0

The answer

In fact, this is the deformation of the N Queen problem, assuming that the black queen first, then for the black queen comes is a simple N queen problem, the only difference is that a certain position can not put the queen.

The second step is the white Queen, so for the white Queen, it is a simple N Queen problem, the only difference is that a certain position can not put the queen, this can not include (the value of the position given by the question is 0 and the position where the black Queen has been placed).
#include<iostream> #include <math.h> int N; using namespace std; int chess[8][8]; int num=0; Int blackCur[8]; Int whiteCur[8]; int whiteCur[8]; Int check(int n,int Cur[]){// Pass in line for(int I =0; i<n; I++) {if (Cur [I] = = Cur [n] | | abs (n - I) = = abs (Cur [n] - Cur [I])) {/ / whether the location of the current place before and if placed in the same column or with inclined column return 0; } } return 1; } void whiteQueen(int n){ if(n==N){ num++; }else{ for(int j=0; j<N; j++){ if( blackCur[n]! =j && chess[n][j]! =0){ whiteCur[n]=j; if(check(n,whiteCur)){ whiteQueen(n+1); }}}}} void blackQueen(int n){if(n== n){}}}}} void blackQueen(int n){if(n== n){// whiteQueen(0); }else{for(int j=0; j<N; J ++){// place column positions from 0 to last if(chess[n][j]! =0) { blackCur[n]=j; If (check(n,blackCur)){blackQueen(n+1); }}}}} int main(){cin>>N; for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ cin>>chess[i][j]; } } blackQueen(0); cout<<num; return 0; }Copy the code