Backtracking

tv 프로그램 '문제적 남자' 에서 나온 ..가 backtracking으로 풀 수 있는 예제 중 하나이다.

c언어 구현 코드

#include<stdio.h>

int numbers[9]; // 어차피 마지막은 0이므로 1~9번째 자리만 찾기
				// int로 만들 수 있는 최대 숫자 21억, unsigned int 42억

void initNumbers() {
	for (int i = 0; i < 9; i++) {
		numbers[i] = -1; // 0은 답중에 있기때문.
	}
}

int makeNumbers(int idx) {

	int sum = numbers[0];
	for (int i = 1; i <= idx; i++) {
		sum = sum * 10 + numbers[i];
	}
	return sum;
}

// idx 위치에 v라는 숫자를 넣는다.
// 그리고 거기까지 만들어진 숫자가 조건에 부합하는지 검사한다.
void checkNumber(int v, int idx) {
	
	numbers[idx] = v;

	// 조건1. idx앞에 있는 v와 겹치는 숫자가 있는지 검사한다.
	// 실패하면 return
	for (int i = 0; i < idx; i++) {
		if (numbers[i]==v) {
			return; // backtracking 되는 부분.
		}
	}

	// 조건2. numbers[0...idx]까지 숫자가 idx+1로 나누어 떨어지는지 검사한다.
	// 실패하면 return
	if (makeNumbers(idx)%(idx+1)!=0) {
		return;
	}

	// 탈출조건
	// idx가 8번째 자리까지했으면 탈출해야함. - 영광스러운 탈출
	if (idx == 8) {
		printf("The Number is %d\n",makeNumbers(idx));
	}

	// 1차와 2차 관문을 무사히 통과했으면 다음 단계로 진입
	// 다음 차례(다음 위치idx)에도 알맞은 수를 넣는다.
	for (int i = 1; i <= 9; i++) {
		checkNumber(i,idx+1); // 계속 뒷자리까지 가는 것
	}
}

int main() {

	// numbers[]를 모두 -1로 초기화한다.
	initNumbers();

	// index0에 1~9까지의 수를 넣어보면 backtracking
	for (int i = 1; i <= 9; i++) {
		checkNumber(i, 0); 
	}

	return 0;
}