UVa – 750 – The 8 Queens Problem

Problem Link : UVa – 750 – The 8 Queens Problem

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int N, top = 0, S = 1;
int temp[10], sol[100][10], taken[10], left_diagonal[20], right_diagonal[20];
void back_track(int c) {
	if (c == 9) {
		memcpy(sol[top++], temp, sizeof temp);
	} else {
		for (int r = 1; r < 9; ++r) {
			if (!taken[r] && !left_diagonal[r + c] && !right_diagonal[r - c + 8]) {
				taken[r]   =  left_diagonal[r + c]  =  right_diagonal[r - c + 8] = 1;
				temp[c] = r;
				back_track(c + 1);
				taken[r]   =  left_diagonal[r + c]  =  right_diagonal[r - c + 8] = 0;
			}
		}
	}
}
int main() {
	memset(taken, 0, sizeof taken);
	memset(left_diagonal, 0, sizeof left_diagonal);
	memset(right_diagonal, 0, sizeof right_diagonal);
	back_track(1);
	int T, r, c;
	scanf("%d", &T);
	while (T-- && scanf("%d %d", &r, &c) && !(S = 0)) {
		printf("SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n\n");
		for (int i = 0; i < top; i++) {
			if (sol[i][c] == r) {
				printf("%2d     ", ++S);
				for (int j = 1; j < 9; ++j)
					printf(" %d", sol[i][j]), printf(j == 8 ? "\n" : "");
			}
		}
		if (T)
			printf("\n");
	}
	return 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

%d bloggers like this: