-
Notifications
You must be signed in to change notification settings - Fork 0
/
NQUEENB.C
137 lines (132 loc) · 3.61 KB
/
NQUEENB.C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<stdio.h>
#include<conio.h>
#define DIM 8
void block_path(int data[DIM+1][DIM+1], int queen_r, int queen_c)
{
int row,col;
data[queen_r][queen_c]=queen_r;
//left
for(row = queen_r, col = queen_c-1; col>0 ; col--)
data[row][col]+= queen_r;
//left top dia
for(row = queen_r-1, col = queen_c-1; row>0 && col>0 ; row--,col--)
data[row][col]+= queen_r;
//top
for(row = queen_r-1, col = queen_c; row>0 ; row--)
data[row][col]+= queen_r;
//right top dia
for(row = queen_r-1, col = queen_c+1; row>0 && col<=DIM ; row--,col++)
data[row][col]+= queen_r;
//right
for(row = queen_r, col = queen_c+1; col<=DIM ; col++)
data[row][col]+= queen_r;
//right down dia
for(row = queen_r+1, col = queen_c+1; row<=DIM && col<=DIM ; row++,col++)
data[row][col]+= queen_r;
//down
for(row = queen_r+1, col = queen_c; row<=DIM ; row++)
data[row][col]+= queen_r;
//left down dia
for(row = queen_r+1, col = queen_c-1; row<=DIM && col>0 ; row++,col--)
data[row][col]+= queen_r;
}
void free_path(int data[DIM+1][DIM+1], int queen_r, int queen_c)
{
int row,col;
data[queen_r][queen_c]=0;
//left
for(row = queen_r, col = queen_c-1; col>0 ; col--)
data[row][col]-= queen_r;
//left top dia
for(row = queen_r-1, col = queen_c-1; row>0 && col>0 ; row--,col--)
data[row][col]-= queen_r;
//top
for(row = queen_r-1, col = queen_c; row>0 ; row--)
data[row][col]-= queen_r;
//right top dia
for(row = queen_r-1, col = queen_c+1; row>0 && col<=DIM ; row--,col++)
data[row][col]-= queen_r;
//right
for(row = queen_r, col = queen_c+1; col<=DIM ; col++)
data[row][col]-= queen_r;
//right down dia
for(row = queen_r+1, col = queen_c+1; row<=DIM && col<=DIM ; row++,col++)
data[row][col]-= queen_r;
//down
for(row = queen_r+1, col = queen_c; row<=DIM ; row++)
data[row][col]-= queen_r;
//left down dia
for(row = queen_r+1, col = queen_c-1; row<=DIM && col>0 ; row++,col--)
data[row][col]-= queen_r;
}
void path_tracker(int data[DIM+1][DIM+1], int queen_r, int queen_c,int flag)
{
int row,col;
for(row= 1; row<=DIM; row++)
for(col = 1; col<= DIM ;col++)
if(queen_r==row|| queen_c==col||
(row-col)==(queen_r-queen_c)|| (row+col)==(queen_r+queen_c))
data[row][col]= data[row][col] + (flag *queen_r);
}
void display(int queen_pos[DIM+1])
{
int row,col;
gotoxy(1,5);
for(row= 1,printf("\n\t"); row<=DIM; row++,printf("\n\t"))
for(col = 1; col<= DIM ;col++)
{ if(queen_pos[row] == col)
printf("Q ");
else
printf("_ ");
}
}
int main()
{
int data[DIM+1][DIM+1]={0};
int queen_pos[DIM+1]={0};
int row,col,safe_pos,solCtr=0;
clrscr();
safe_pos=0;
row=1;
while(1)
{
while(row<=DIM)
{
for(col=safe_pos+ 1;col<=DIM ; col++)
{
if(data[row][col]==0)//safety check
{
path_tracker(data,row,col,1); //block the path
queen_pos[row]=col; //update queen position
row++; //goto nxt row
safe_pos=0;
break;
}
}
if(col>DIM)//backtracking
{
row--;
path_tracker(data,row,queen_pos[row],-1); //free the path
safe_pos= queen_pos[row];
queen_pos[row]=0;
}
}
display(queen_pos);
gotoxy(5,3);
printf("Sol Ctr: %2d",++solCtr);
delay(200);
if(solCtr==92)
break;
row--;
path_tracker(data,row,queen_pos[row],-1); //free the path
safe_pos= queen_pos[row];
queen_pos[row]=0;
}
/*
for(row= 1,printf("\n\t"); row<=DIM; row++,printf("\n\t"))
for(col = 1; col<= DIM ;col++)
printf("%2d ",data[row][col]);
*/
getch();
return 0 ;
}