[05. 재귀 알고리즘] 8퀸 문제(8-Queen Problem)

Recursion

#include <iostream>
using namespace std;

int count_board = 0;

void print_board(int pos[]) {
	for (int r = 0; r < 8; r++) {
		cout << pos[r] << ' ';
		for (int c = 0; c < 8; c++)
			cout << (pos[r] == c ? "■" : "□");
		cout << endl;
	}
	cout << endl;
	count_board++;
}

void queen(int r=0) {
	static int pos[8] = { 0 };
	static bool col[8] = { false };
	static bool right_down[15] = { false };
	static bool left_down[15] = { false };

	for (int c = 0; c < 8; c++) {
		if (col[c] || right_down[r - c + 7] || left_down[r + c])
			continue;
		
		pos[r] = c;
		if (r != 7) {
			col[c] = right_down[r - c + 7] = left_down[r + c] = true;
			queen(r + 1);
			col[c] = right_down[r - c + 7] = left_down[r + c] = false;
		}
		else
			print_board(pos);
	}
}

int main(int num) {
	queen();
	cout << count_board << endl;
}

출력

0 ■□□□□□□□
4 □□□□■□□□
7 □□□□□□□■
5 □□□□□■□□
2 □□■□□□□□
6 □□□□□□■□
1 □■□□□□□□
3 □□□■□□□□

0 ■□□□□□□□
5 □□□□□■□□
7 □□□□□□□■
2 □□■□□□□□
6 □□□□□□■□
3 □□□■□□□□
1 □■□□□□□□
4 □□□□■□□□

.
.
.

7 □□□□□□□■
2 □□■□□□□□
0 ■□□□□□□□
5 □□□□□■□□
1 □■□□□□□□
4 □□□□■□□□
6 □□□□□□■□
3 □□□■□□□□

7 □□□□□□□■
3 □□□■□□□□
0 ■□□□□□□□
2 □□■□□□□□
5 □□□□□■□□
1 □■□□□□□□
6 □□□□□□■□
4 □□□□■□□□

92

Stack

#include <iostream>
#include <stack>
#include <tuple>
#include <array>
using namespace std;

int count_board = 0;

void print_board(const array<int, 8>& pos) {
	for (int r = 0; r < 8; r++) {
		cout << pos[r] << ' ';
		for (int c = 0; c < 8; c++)
			cout << (pos[r] == c ? "■" : "□");
		cout << endl;
	}
	cout << endl;
	count_board++;
}

void queen(int r = 0) {
	array<int, 8> pos = { 0 };
	array<bool, 8> col = { false };
	array<bool, 15> right_down = { false };
	array<bool, 15> left_down = { false };

	stack<tuple<int, array<int, 8>, array<bool, 8>, array<bool, 15>, array<bool, 15>>> st;
	st.emplace(r, pos, col, right_down, left_down);
	
	while (!st.empty()) {
		auto cur_r = get<0>(st.top());
		auto cur_pos = get<1>(st.top());
		auto cur_col = get<2>(st.top());
		auto cur_rd = get<3>(st.top());
		auto cur_ld = get<4>(st.top());
		st.pop();

		for (int c = 0; c < 8; c++) {
			if (cur_col[c] || cur_rd[cur_r - c + 7] || cur_ld[cur_r + c])
				continue;

			cur_pos[cur_r] = c;
			if (cur_r != 7) {
				cur_col[c] = cur_rd[cur_r - c + 7] = cur_ld[cur_r + c] = true;
				st.emplace(cur_r + 1, cur_pos, cur_col, cur_rd, cur_ld);
				cur_col[c] = cur_rd[cur_r - c + 7] = cur_ld[cur_r + c] = false;
			}
			else
				print_board(cur_pos);
		}
	}
}

int main(int num) {
	queen();
	cout << count_board << endl;
}

출력

7 □□□□□□□■
3 □□□■□□□□
0 ■□□□□□□□
2 □□■□□□□□
5 □□□□□■□□
1 □■□□□□□□
6 □□□□□□■□
4 □□□□■□□□

7 □□□□□□□■
2 □□■□□□□□
0 ■□□□□□□□
5 □□□□□■□□
1 □■□□□□□□
4 □□□□■□□□
6 □□□□□□■□
3 □□□■□□□□

.
.
.

0 ■□□□□□□□
4 □□□□■□□□
7 □□□□□□□■
5 □□□□□■□□
2 □□■□□□□□
6 □□□□□□■□
1 □■□□□□□□
3 □□□■□□□□

92