minimum number of queens in a chessboard to cover entireboard

#include <stdio.h>
#include <string.h>

typedef struct {
int x, y;

}Pos;

int minQueen(int a[8][8], Pos pos[], int num){

int b[8][8];

int i, j, min = 0, k;

for(i = 0; i < 8; ++i){

for(j = 0 ; j < 8; ++j){

if(a[i][j] == 0){

memcpy(b, a , sizeof(b));

//fill the covered area
for(k = 0; k < 8; ++k){

b[i][k] = 1; //row
b[k][j] = 1; //column

b[(i + k) % 8 ][ (j + k) % 8] = 1; //diagnol
}

int n = minQueen(b, pos, num + 1);

n++;

if(min == 0 || min >= n) {
min = n;

pos[num].x = i;
pos[num].y = j;

if(num == 0){

for(k = 0; k < n; ++k)
printf("(%d,%d) ", pos[k].x, pos[k].y);
printf("\n");
}
}
}
}
}

return min;

}


int main(){

int a[8][8] = {0};

Pos pos[8];

printf("%d\n", minQueen(a, pos, 0));
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s