# Checkerboard problem---[Status Compression]

Question 1:
Place nnn rooks (which can attack the row and column where they are located) on a checkerboard of n∗n(n≤20)n*n(n≤20)n∗n(n≤20), and find the ones that cannot attack each other Total number of programs.

If you think about this from a combinatorics perspective, it's pretty simple:

We put it line by line, the first line has nnn choices, the second line has n−1,...n-1,...n−1,..., and the last line has 1 choice. According to the principle of multiplication, the answer is n! n!n!

Here we introduce another solution: State Compressing Recursion (SCR) (States Compressing Recursion, SCR) (States Compressing Recursion, SCR).

We still place line by line.
Take the placement of chess pieces as the state, if a chess piece has been placed in a certain column, it will be 111, otherwise it will be 000. In this way, a state can be represented by a binary number of up to 202020 bits.
For example, n=5n=5n=5, and the 1st, 3rd, 41st, 3rd, 41st, 3rd, and 4th columns have been placed, then this state can be represented as 011010110101101 (from right to left). Let fs be the number of solutions to reach state s, then you can try to establish the recurrence relation of f.
Consider n=5,s=01101n=5,s=01101n=5,s=01101
Because we placed it row by row, when s is reached, the third row has already been placed. And because a row can place only one car, we know that state s must come from:

```        ①The first two rows have pawns placed in columns 3 and 4(Regardless of the order, the same below)，The third row is placed in column 1;

②The first two rows have pawns placed in columns 1 and 4, and the third row is placed in column 3;

③The first two rows have pawns placed in columns 1 and 3, and the third row is placed in column 4.

These three cases do not intersect with each other, and only these three cases are possible. According to the principle of addition, fs should be equal to the sum of these three cases. written in recursive             Yes:

f(01101) = f(01100) + f(01001) ＋ f(00101);
```

According to the above discussion ideas, the solution of the example is obtained:
f(0) = 1;

```    f(s) = ·f(s-2^i);

in s from right i+1 bit is 1(In fact, it is enumerating s 1 in the binary representation of)
```

code show as below:

```#include<iostream>
#include<cstdio>
using namespace std;
long long f[1<<20];

int main(){
long long n;
while(cin>>n){
memset(f,0,sizeof(f));
f[0] = 1;
long long i,t;
for( i=1; i< 1<<n; i++){
for( t=i; t>0; t -= (t & -t)){
f[i] += f[i & ~(t & -t)];  //Pay attention to understanding
}
}
cout<<f[(1<<n)-1]<<endl;
}
}
```

Question 2: Place n rooks on the n∗n(n≤20)n*n(n≤20)n∗n(n≤20) checkerboard. Some squares cannot be placed, so they cannot be placed on each other.
The total number of schemes attacked.
Input: give you an n and m, which represent the size of the chessboard and the total number of squares that cannot be placed
Next are m lines of coordinates, representing the seats that cannot be placed.
Output: Total number of eligible schemes.

0 means can be placed, 1 means cannot be placed
0 1 0
0 0 1
0 0 0
enter:
3 2
1 2
2 3
output: 3
enter:
4 1
1 1
Output: 3∗3∗2∗1==183*3*2*1 == 183∗3∗2∗1==18
hint:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

long long f[1<<20];
long long vist[22];

int main(){
long long n,m;
while(cin>>n>>m){
memset(f,0,sizeof(f));
memset(vist,0,sizeof(vist));
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
vist[a] += 1<<(b-1); //A certain position cannot be placed, compress this position into an integer
}
f[0] = 1;
for(int i=1;i< 1<<n; i++){
int num = 0;
for(int j=i;j>0;j -= (j & -j)) num++; //Calculate the number of i state 1, that is, the maximum number of rows included
for(int j=i;j>0;j -= (j & -j)) {
if(!(vist[num]&(j & -j))) f[i] += f[ i& ~(j & -j)];//Determine whether the location can be placed
}
}
cout<<f[(1<<n)-1]<<endl;
}
}
```

Problem 3: Given a checkerboard of n∗mn*mn∗m (n, m≤80,n∗m≤80)(n, m≤80,n*m≤80)(n, m≤80,n∗ m≤80), k(k≤20)k(k≤20)k(k≤20) pieces should be placed on the board so that any two pieces are not adjacent. Find the total number of plans that can be placed

```#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int s[1<<10],c[1<<10],f[82][1<<9][21];
int n,m,num,flag,val;

void DFS(int ans,int pos,int flag){  ///
if(pos>n) {
s[++num] = ans;
c[num] = flag;
return;
}
DFS(ans,pos+1,flag);
DFS(ans+(1<<pos-1),pos+2,flag+1);
}

int main(){
while(cin>>n>>m>>val){
if(n>m) swap(n,m); // row and column exchange
num = 0;  // State number initialization
DFS(0,1,0); // Parameters: current state, position, number of 1s, find out the total number of eligible conditions in a row
memset(f,0,sizeof(f));
///
for(int i=1;i<=num;i++) //The first line is initialized, and the number of 1s in the state is initialized
f[1][s[i]][c[i]] = 1;
for(int i=2;i<=m;i++){ //which line
for(int j=1;j<=num;j++){ //a state of a row
for(int r=1;r<=num;r++){ //a state of the previous line
if(!(s[j]&s[r])){ //The current line and the previous line state do not conflict
for(int k=0;k<=val;k++){ //Enumerate the number of pieces in the current row
if(k>=c[j]) f[i][s[j]][k] += f[i-1][s[r]][k-c[j]]; //Enumerate the current state with the help of the state from the previous line
}
}
}
}
}
long long sum=0;
for(int i=1;i<=num;i++) // Accumulates the total number of matches in the last row
sum += f[m][s[i]][val];
cout<<sum<<endl;
}
}
```

/*
Due to the lack of data, I simulated several sets of data myself
Input: 3 3 2
output: 23
Input: 2 2 2
output: 2
Input: 20 1 2
Output: 171
*/

Question 4:
Put k kings (which can attack the adjacent 888 squares) on the chessboard of n∗n(n≤10)n*n(n≤10)n∗n(n≤10), so that they cannot be
The number of schemes attacking each other.

```#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
long long f[11][1<<10][30];
int s[1<<10],c[1<<10],num;
int n,m,val;

void DFS(int ans,int pos,int flag){
if(pos>n){
s[++num] = ans;
c[num] = flag;
return ;
}
DFS(ans,pos+1,flag);
DFS(ans+(1<<pos-1),pos+2,flag+1);
}

int main(){
while(cin>>n>>m>>val){
num = 0;
DFS(0,1,0);
memset(f,0,sizeof(f));
for(int i=1;i<=num;i++)
f[1][s[i]][c[i]]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=num;j++){ //current line
for(int r=1;r<=num;r++){ //previous row
if((s[j]&s[r]) || ((s[j]>>1)&s[r]) || ((s[j]<<1)&s[r])) continue; //Eight directions to judge
for(int k=0;k<=val;k++){
if(k>=c[j]) f[i][s[j]][k] += f[i-1][s[r]][k-c[j]];
}
}
}
}
long long sum=0;
for(int i=1;i<=num;i++)
sum += f[n][s[i]][val];
cout<<sum<<endl;
}
}
```

/*
Input: 3 3 2
Output: 16
Input: 2 2 1
output: 4
Input: 3 3 3
output: 8
Input: 9 9 2
Output: 1968
*/

Problem 5: Given a chessboard of n∗m(n≤100,m≤10)n*m(n≤100,m≤10)n∗m(n≤100,m≤10), some grids cannot place chess pieces . ask for the most
How many pieces are placed on the board so that there are at least two spaces between any two pieces in each row and column.

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
long long f[11][1<<10];
int n,m,s[1<<10],c[1<<10];
int num,ant,a[1<<10];

void DFS(int ans,int pos,int flag){
if(pos>m){
s[++num] = ans;
c[num] = flag;
return ;
}
DFS(ans,pos+1,flag);
DFS(ans+(1<<pos-1),pos+3,flag+1);
}

int main(){
while(cin>>n>>m>>ant){
int p,q;
for(int i=0;i<ant;i++){
cin>>p>>q;
a[p] += (1<<q-1);
}
memset(f,0,sizeof(f));
num = 0;
DFS(0,1,0);
//  for(int i=1;i<=num;i++) cout<<s[i]<<" "<<c[i]<<endl;
for(int i=1;i<3 && i<=n;i++){
for(int j=1;j<=num;j++){ // When i==2, it means the current line, and when i==1, it means the current line
if(i==1){
if(a[i]&s[j]) continue;  // cannot be placed
f[i][s[j]]=c[j];
}
else {
if(a[i]&s[j]) continue;  // cannot be placed
for(int r=1;r<=num;r++){ // Cannot be placed and does not conflict with state 1, indicating the state of the previous line
if(a[i-1]&s[r]) continue;  // cannot be placed
if((s[j]&s[r])) continue;
f[i][s[j]] = max(f[i][s[j]],f[i-1][s[r]]+c[j]);
}
}
}
}
for(int i=3;i<=n;i++){
for(int j=1;j<=num;j++){//current line
if(s[j]&a[i]) continue;
for(int r=1;r<=num;r++){//previous row i-1
if((s[r]&a[i-1]) || (s[j]&s[r])) continue;
for(int h=1;h<=num;h++){//one more line i-2
if((s[h]&a[i-3])||(s[j]&s[h])||(s[r]&s[h])) continue;
f[i][s[j]] = max(f[i][s[j]],f[i-2][s[h]]+c[j]+c[r]);
}
}
}
}
long long sum = 0;
for(int i=1;i<=num;i++)
sum = max(f[n][s[i]],sum);
cout<<sum<<endl;
}
}
```

/*
enter:
3 3 3
2 1
2 2
2 3
output: 2
*/

Topic 6:
Given a checkerboard of n∗m(1≤n, m≤11)n*m(1≤n, m≤11)n∗m(1≤n, m≤11), use 1∗21*21∗ 2 rectangles of dominoes cover this without overlapping
Checkerboard, find the number of plans covered.

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
using namespace std;
long long f[12][1<<14];
int s1[1<<14],s2[1<<14],s[1<<14],ss[1<<14];
int n,m,num,flag;
bool vist[1<<14];

void DFS(int ans1,int ans2,int pos){
if(pos>n) {
if(pos==n+1) {
s1[++num] = ans1;
s2[num] = ans2;
}
return ;
}
DFS(ans1,ans2,pos+1); // don't let go
DFS(ans1+(1<<pos-1)+(1<<pos),ans2,pos+2); // lay horizontally
DFS(ans1+(1<<pos-1),ans2+(1<<pos-1),pos+1); // vertical
}

void dfs(int ans,int pos){
if(pos>n){
if(pos==n+1)
s[++flag] = ans;
return;
}
dfs(ans,pos+1);
dfs(ans+(1<<pos-1)+(1<<pos),pos+2);
}

int main(){
while(cin>>n>>m){
if(n==0 && m==0) break;
if(n%2 && m%2){ cout<<'0'<<endl; continue; }
if(n > m) swap(n,m);
if(n%2) swap(n,m);
if(m==1) { cout<<'1'<<endl; continue; }
num = 0; flag = 0;
DFS(0,0,1);
dfs(0,1); // First line all state search
memset(f,0,sizeof(f));
for(int i=1;i<=flag;i++)
f[1][s[i]] = 1;
int ant = (1<<n) - 1;
for(int i=1;i<=num;i++){ //second line
ss[i] = s1[i];
for(int j=1;j<=flag;j++){ //first row
if((s2[i]&s[j])) continue;
if((ant-s2[i])&(ant-s[j])) continue; //handle the same 0
f[2][s1[i]] += f[1][s[j]];
}
}
sort(ss+1,ss+num);
int ans = 0;
ss[++ans] = ss[1];
for(int i=2;i<=num;i++){  //Remove the same to avoid double counting
if(ss[i]!=ss[i-1]) ss[++ans] = ss[i];
}
for(int i=3;i<=m;i++){ //The third row
for(int j=1;j<=num;j++){//State traversal of row i
for(int r=1;r<=ans;r++){ // Line i-1 ***** The same s1[r] can only be calculated once WA for a long time
if(s2[j]&ss[r]) continue;
if((ant-s2[j])&(ant-ss[r])) continue;
f[i][s1[j]] += f[i-1][ss[r]];
}
}
}
cout<<f[m][(1<<n)-1]<<endl;
}
}

```

Posted by santosj on Sat, 21 May 2022 19:44:58 +0300