Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2026
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);
}
}
Input
1 1 1 1 1 1 1 1
Output
Case 2: 7
Demonstration
UVA Online Judge solution - 11085-Back to the 8-Queens - UVA Online Judge solution in C,C++,java