카쿠로

스도쿠나 N-Queens 문제들을 마주할 때면 가슴이 답답하다. 냅색이나 LIS 처럼 차곡차곡 상황들을 쌓아 갈 수 없을 뿐더러 두더지 게임 처럼 하나의 조건을 해결하면 또 다른 문제가 튀어나오니 도대체 어떻게 풀어야 할 지 감을 잡을 수 없었다. 이러한 유형의 문제를 보면 정말 머리 좋은 친구들이 푸는건가보다 하고 그냥 넘어 갔던 것 같다.

알고리즘 해결 전략에서는 스도쿠, N-Queen 그리고 가쿠로 문제처럼 특정한 제약에 해당하는 답을 찾는 문제를 제약 충족 문제라고 한다. 조합 탐색 문제들 중에 하나인데 먼저 조합 탐색은 기존에 사용했던 알고리즘(DP, 탐욕법 등등)을 사용 할 수 없고 가지치기를 통해 검사 할 필요가 없는 경우들을 미리 쳐내는 방법이다. 제약 충족 문제는 조합 문제에서 한 발 더 나아간다. 주어진 조건에서 제약을 스스로 만들고 다른 조각에 그 제약을 전파 하는 것이다. 다르게 말하면 답의 일부를 생성한 뒤 거기서 얻을 수 있는 정보를 최대한 많이 찾아내는 것이라 할 수 있다.

한가지 더 생각해볼 것은 채울 순서를 고르는 것이다. 스도쿠 문제를 풀 때 빈 칸중에서 제일 만만히 입력 할 수 있는 빈칸은 가로 또는 세로가 많이 채워져 있는 칸일 것이다. 최대한 가지의 순서를 줄이려면 어느 것을 먼저 채울지 선택하는것 또한 중요하다.

카쿠로 문제에서도 동일하다. 먼저 채울 순서는 오른쪽 또는 세로의 줄에 칸이 적은 것들 부터 골라야 할 것이다. 즉 빈칸에 들어갈 숫자 후보의 수가 가장 작은 곳 부터 먼저 채워가야 한다. 그래야지 빈칸을 채우는 전체 경우의 수가 줄어들어 시간내에 풀 수 있다.

이 문제의 해설 을 볼 때 감탄을 했던 부분이 여러 군데 였던 것 같다. 첫 번째는 각 빈칸에 놓을 수 있는 숫자들의 잡합을 비트로 표현했다는 것이다. 각 칸마다 가능한 숫자 후보자는 가로쪽 힌트와 세로쪽 힌트의 교집합인데, 비트마스크는 그 힌트를 가장 간단히 표현 해주었다.

두번째는 모든 후보 경우의 수들을 전처리해준 것이다. 후보 집합에 영향을 미치는 값들이 길이, 총합 인데 중복 계산을 방지 하기 위해 모든 경우에 대해서 전처리 해줬다. 가능한 숫자로 0을 빼기 위해 비트 연산을 넣은 센스도 감탄 스러웠다.

책에서 본 내용을 토대로 작성한 코드는 이렇다.

 
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<string.h>

using namespace std;

const int WHITE = 1;
const int MAXN = 21;

int candidates[10][46][1024];

int n, color[MAXN][MAXN], value[MAXN][MAXN], hint[MAXN][MAXN][2];
int q, sum[MAXN*MAXN], length[MAXN*MAXN], known[MAXN*MAXN];

int getSize(int mask) {
	int ret = 0;

	for (int i = 0; i <= 9; i++)
		if (mask & (1 << i))
			ret++;

	return ret;
}
int getSum(int mask) {
	int ret = 0;

	for (int i = 0; i <= 9; i++)
		if (mask & (1 << i))
			ret += i;

	return ret;
}

void generatesCandidates() {
	memset(candidates, 0, sizeof(candidates));

	for (int set = 0; set < 1024; set += 2) {
		int l = getSize(set), s = getSum(set);
		int subset = set;

		while (true) {
			candidates[l][s][subset] |= (set & ~subset);
			if (subset == 0) break;
			subset = (subset - 1)&set;
		}
	}
}

void put(int r, int c, int val) {
	for (int h = 0; h < 2; h++)
		known[hint[r][c][h]] += (1 << val);
	value[r][c] = val;
}

void remove(int r, int c, int val) {
	for (int h = 0; h < 2; h++)
		known[hint[r][c][h]] -= (1 << val);
	value[r][c] = 0;
}

int getCandHint(int hint) {
	return candidates[length[hint]][sum[hint]][known[hint]];
}

int getCandCoord(int r, int c) {
	return getCandHint(hint[r][c][0])&getCandHint(hint[r][c][1]);
}

void printSolution() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) 
			printf("%d ", value[i][j]);
		printf("\n");
	}
}

void setSum(int hint, int hintSum) {
	sum[hint] = hintSum;
}

void setLen(int hintNum, int direct, int r, int c) {
	int len = 0;

	int inc_r = 0, inc_c = 0;
	if (direct == 0)
		inc_c++;
	else
		inc_r++;

	r += inc_r, c += inc_c;
	while (true) {
		if (r > n || c > n || color[r][c] != 1)
			break;
		hint[r][c][direct] = hintNum;
		r += inc_r;
		c += inc_c;

		len++;
	}

	length[hintNum] = len;
}

bool search() {
	int y = -1, x = -1, minCands = 1023;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if (color[i][j] == WHITE && value[i][j] == 0) {
				int cands = getCandCoord(i, j);
				if (getSize(minCands) > getSize(cands)) {
					minCands = cands;
					y = i, x = j;
				}
			}

	if (minCands == 0) return false;

	if (y == -1) {
		printSolution();
		return true;
	}

	for (int val = 1; val <= 9; val++) {
		if (minCands & (1 << val)) {
			put(y, x, val);
			if (search()) return true;
			remove(y, x, val);
		}
	}

	return false;
}

int main() {

	int tc, r, c, dir, s;

	generatesCandidates();

	freopen("input.txt", "r", stdin);
	scanf("%d", &tc);

	while (tc--) {
		scanf("%d", &n);


		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				scanf("%d", &color[i][j]);
				value[i][j] = 0;
				hint[i][j][0] = hint[i][j][1] = 0;
			}

		for (int i = 1; i <= MAXN*MAXN; i++)
			length[i] = sum[i] = known[i] = 0;

		scanf("%d", &q);

		for (int i = 1; i <= q; i++) {
			scanf("%d%d%d%d", &r, &c, &dir, &s);
			setSum(i, s);
			setLen(i, dir, r, c);
		}

		search();
	}

	return 0;
}

이런 문제를 보면 감탄스러우면서도 이런 코드를 과연 작성 할 수 있을지 마음이 착잡하다..