Solution of 8-Queen Problem

Definition of problem :- Here is a very famous problem. How many ways are there to place 8 queens on a chess board so that
no two queens attack each other? A chess board is an 8x8 grid. Queens can be placed in the cells f
the grid. Two queens are under mutual attack if they share a row, a column or a diagonal. Here is one
possible solution:
We have to endure 4-things
1)No 2 Queens share same Column
2)No 2 Queens share same Row
3)No 2 Queens share / diagonal
4)No 2 Queens share \ diagonal
No. 1 is automatic because the way we store solution
No. 2 is done with used array
for 3 and 4 we do same thing we keep two array of size 15 to keep track which diagonals are occupied.,Consider the following trick.If we take a cell with coordinate (r,c) what are the values of (r+c) and (r+c-7) (indexing is from 0-7).

Let's call (r+c) the "Slash Code" of cell and (r-c+7) the "Backslash Code" .Then two queen which share a / diagonal has same "Slash code" and those who share a \ diagonal has same "Backslash Code" .

Solution O/P :-

For more info goto : http://securityresearch.in/beta
Code :-

1:  //   8_queen.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <vector>  
21:  using namespace std;  
22:  vector<int> row(8),used(8),slash(15),backSlash(15);  
23:  int total;  
24:  int queen(int i)  
25:  {  
26:       if(i==8)  
27:       {  
28:            return 1;  
29:       }  
30:       for(row[i]=0;row[i]<8;row[i]++)  
31:       {  
32:            if(used[row[i]]==1 || slash[row[i]+i]==1 || backSlash[row[i]-i+7]==1)  
33:                 continue;  
34:            used[row[i]]=1;  
35:            slash[row[i]+i]=1 ;  
36:            backSlash[row[i]-i+7]=1;  
37:            total=queen(i+1);  
38:            if (total==1)  
39:              return 1;  
40:            used[row[i]]=0;  
41:            slash[row[i]+i]=0 ;  
42:            backSlash[row[i]-i+7]=0;  
43:       }  
44:       return total;  
45:  }   
46:  int main(int argc, char** argv)  
47:  {  
48:       for(int i=0;i<8;i++)  
49:       {  
50:            row[i]=0;  
51:            used[i]=0;  
52:       }  
53:       for(int i=0;i<15;i++)  
54:       {  
55:            slash[i]=0;  
56:            backSlash[i]=0;  
57:       }  
58:       int k=queen(0);  
59:       k++;  
60:       /*for(int i=0;i<8;i++)  
61:       {  
62:            cout<<row[i]<<endl;  
63:       }*/  
64:    for(k=0;k<8;k++)  
65:        {  
66:        for(int l=0;l<8;l++)  
67:            cout<<" ----";  
68:        cout<<endl;  
69:        for(int j=0;j<9;j++)  
70:        {  
71:            cout<<"|  ";  
72:            if(row[k]==j)  
73:            cout<<"\b\bQ"<<k;  
74:        }  
75:        cout<<endl;  
76:     }  
77:       for(int l=0;l<8;l++)  
78:            cout<<" ----";       
79:       return 0;  
80:  }  

                                                                 Rest in Peace