## Algorithm

You are given a chess board (of 8×8 dimension) and there are 8 queens placed randomly on the board. Each of the 8 queens is in different columns and that means no two queens are attacking each other vertically. But some queens are attacking each other horizontally and/or diagonally. You have to move the queens so that no two queens are attacking each other from any direction. You are allowed to move the queens vertically and thus you can only change the row positions of each queen and not the column. A move consists of moving a queen from (R1, C) to (R2, C) where 1 ≤ R1, R2 ≤ 8 and R1 ΜΈ= R2. You have to find the minimum number of moves required to complete the task. Input There will be multiple test cases. Each case consists of a line containing 8 integers. All these integers will be in the range [1, 8]. The i-th integer indicates the row position of a queen in the i-th column. Output For each case, output the case number followed by the required output. Constraints • Total number of test cases will be less than 1000. Sample Input 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 Sample Output Case 1: 7 Case 2: 7

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````#include <bits/stdc++.h>

using namespace std;
int res;
void backtrack(int sum,vector<int>& board,vector < bool>& rows,
vector<bool>& diag1,vector<bool>& diag2,int c){
if(c == 8) {
res = min(sum,res);
return;
}
for(int i=0;i<8;i++){
if(rows[i] || diag1[i-c+7] || diag2[c+i]) continue;
rows[i] = diag1[i-c+7] = diag2[c+i] = true;
backtrack(sum+(i==board[c] ? 0 : 1),board,rows,diag1,diag2,c+1);
rows[i] = diag1[i-c+7] = diag2[c+i] = false;
}
}

int main()
{
int v;
int tc=1;
while(cin>>v>{
res = INT_MAX;
vector < bool> rows(8);
vector<bool> diag1(8);
vector < bool> diag2(16);
vector<int> board(1,v-1);
for(int j=1;j < 8;j++){
cin >> v;
board.push_back(v-1);
}
backtrack(0,board,rows,diag1,diag2,0);
printf("Case %d: %d\n",tc++,res);
}
}
```
```
Copy The Code &

Input

cmd
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1

Output

cmd
Case 1: 7
Case 2: 7