CombinatorialSearch.md

조합 탐색

개요

지금까지 다룬 동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용될 때는 매우 유용하지만, 모든 문제에 적용할 수는 없다.

적절한 분할 방법이 없는 문제를 분할 정복으로 풀 수도 없고, 중복되는 부분 문제가 전혀 없거나 메모리를 너무 많이 사용하는 문제에 동적 계획법을 쓸 수도 없다. 이런 경우에 우리는 결국 시작점인 완전 탐색으로 돌아와 다시 시작해야 한다.

완전 탐색 알고리즘은 대개 답을 만드는 과정을 여러 개의 선택으로 나눈 뒤, 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현되곤 한다. 이때 부분 답과 완성된 답의 집합을 탐색 공간(search space)이라고 부른다. 예를 들면 여행하는 외판원 문제(TSP)에서 탐색 공간의 한 원소는 지금까지 방문한 정점의 목록과 현재 위치로 구성한다.

완전 탐색은 모든 답을 다 만들어 보면서 문제를 해결하므로, 완전 탐색의 수행 시간은 탐색 공간의 크기에 직접적으로 비례. 그런데 대부분의 문제에서 탐색 공간의 크기는 문제의 규모에 따라 기하급수적으로 증가. 예를 들어 문제를 n개의 선택지로 조각냈는데, 각 선택지마다 세 가지의 선택을 할 수 있다고 가정했을때, 탐색 공간의 크기는 문제의 크기가 1 커질 때마다 세 배로 증가하게 된다.

아래 그림 선택의 수가 증가함에 따라 확인해야 할 탐색 공간의 원소가 급격히 늘어남을 보여준다. 따라서 완전 탐색은 문제의 규모가 조금이라도 클 경우 사용하기 어렵다는 문제점이 존재.

완전 탐색을 포함해 크기가 유한한 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘들을 이 책에서는 조합 탐색(combinatorial search)이라고 부른다.

조합 탐색에는 다양한 최적화 기법이 있으며, 이들은 접근 방법은 다르지만 모두 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다.

조합 탐색을 최적화하기 위해 어떤 방법을 사용해야 할지 찾아내는 것은 문제 자체에 대한 깊은 식견을 요구하며, 속도와 정확도 사이의 상충 관계, 다양한 입력 형태 사이의 상충 관계 등을 모두 고려해야 한다. 이렇게 어려운 문제이기 때문에 조합 탐색에는 딱히 정답이 없다

조합 탐색 최적화 기법들은 크게 두 가지로 분류한다.

• 가지치기(pruning) 기법

탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라낸다. 현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 알고 있는 최적해보다 나쁘다면 탐색을 더 할 필요가 없다. 가지치기의 가장 기초적인 예로, 지금까지 찾아낸 최적해 보다 부분해가 이미 더 나빠졌다면 현재 상태를 마저 탐색하지 않고 종료해버리는 방법이 있다. 외판원 문제를 푸는데, 길이가 10인 경로를 이미 찾아냈다고 할때, 재귀 호출 도중 현재까지 만든 부분 경로의 길이가 이미 10 이상이 되 었다면 더 이상 탐색하지 않고 탐색을 중단해도 된다. 나머지 경로를 만들어봐야 10보다 짧은 경로를 찾을 수 없기 때문. 가지치기 기법을 사용하면 존재하는 답 중의 일부는 아예 만들지 않기 때문에 프로그램의 동작 속도가 빨라진다. 똑똑한 가지치기 기법들은 여러 방법을 이용해 현재 상태에서 얻을 수 있는 가장 좋은 답의 상한을 찾아 낸다.

• 좋은 답을 빨리 찾아내는 기법

탐색의 순서를 바꾸거나, 탐색 시작 전에 탐욕법을 이용해 적당히 좋은 답을 우선 찾아냅니다. 완전 탐색의 경우 답을 어떤 순서로 찾아내건 상관없지만, 가지치기와 함께 사용할 경우 더 좋은 답 을 알고 있으면 좀더 일찍 탐색을 중단할 수 있기 때문에 탐색의 효율이 좋아진다.

아래 그림은 이와 같은 기법들이 완전 탐색을 어떻게 빠르게 하는지를 보여 준다. 탐색 공간 내에 우리가 원하는 답(별표 표시)이 세 개 있고, 시작 상태에서 가까울수록 더 좋은 답이라고 합시다. 결과적으로 우리가 원하는 최적해는 가장 오른쪽에 있는 별표가 됩니다. 그림 11.2(a)는 가지치기를 적용한 완전 탐색의 수행 과정을 보여준다. 맨 왼쪽에 있는 답을 찾은 이후에는 그 이상 깊이 탐색하지 않는 것을 볼 수 있다. 이미 답을 하나 찾았다면 시작 상태로 부터 그보다 멀리 떨어진 상태를 탐색할 필요가 없기 때문. 그림 11.2(b)는 좋은 답을 일찍 찾아내는 기 법을 적용한 완전 탐색의 수행 과정을 보여준다. 적절한 탐욕법이나 휴리스틱을 이용해 가운데 있는 답을 먼저 찾아냈다고 하자. 그러면 깊이 6 이하로 내려갈 필요가 없기 때문에 더 적은 상태만을 검사하고 최적해를 찾아낼 수 있다.

---

조합 탐색기법들

이 절에서는 조합 최적화 문제를 푸는 완전 탐색 알고리즘의 수행 속도를 높이기 위해 사용되는 여러 방법들을 소개하고, 대표적 최적화 문제인 여행하는 외판원 문제1(TSP)를 푸는 완전 탐색 알고리즘에 이 기 법들을 적용하면서 변화하는 수행 속도를 관찰해 보자.

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초

입력이 커지면 커질수록 수행 시간이 급격히 증가하는 것을 볼 수 있다.

동적 계획법이 사용하는 메모리 또한 입력의 크기에 따라 지수적으로 커진다. 초대형 입력을 처리하기 위해 동적 계획법 알고리즘은 약 3GB의 메모리를 필요로 한다. 만약 컴퓨터의 메모리가 모자랐다면 결국 가상 메모리를 사용 해야 했을 테고, 결과적으로 상상할 수 없을 정도로 느려졌을 것.

조합 탐색 뼈대의 구현

우선 최적화의 기본이 될 탐색 알고리즘의 뼈대를 구현해 보자. 아무런 최적화도 하지 않은 완전 탐색의 구현을 보여줍니다. 완전 탐색을 다루는 장에서 작성한코드와 어떻게 다른지 유의하며 보면 shortestPath() 경로의 길이를 직접 반환하지만, search()는 경로의 길이를 직접 반환하지 않고 전역 변수 best를 갱신하는 방식으로 동작한다. 이렇게 전역 변수에 지금까지 찾은 최적해의 길이를 저장해 두면 탐색 중에 더 최적해를 발견할 가능성이 없는 가지를 쳐내기 쉬워집니다.

조합탐색 TSP 구현 🔗

이와 같은 단순한 알고리즘의 수행 속도는 search()가 만드는 경로의 수는 (n-1)!개가 된다. 11!는 약 4천만 정도 되는 수이므로, 소형 입력은 그럭저럭 풀 수 있다. 단 중형 입력에서 경로의 개수는 12 * 13 * 14 * 15 = 30,000배 늘기 때문에 중형 입력을 풀기란 불가능할 거 라 예측할 수 있다. 소형 입력이 1분 30초 정도 걸릴때, 우리 계산대로라면 중형 입력에만 4만 5천 분(750시간)이나 되는 시간이 소모될 거라고 예측할 수 있다. 이제 이것을 최적화 해보자.

최적해보다 나빠지면 그만두기

가장 기초적인 가지치기 방법은 현재 상태의 답이 지금까지 구한 최적해와 같거나 더 나쁠 때 탐색을 중단하는 것. TSP에서는 지금까지 만든 경로의 길이를 알고 있기 때문에, 이것을 최적해와 비교하면 이 가지치 기를 간단하게 구현할 수 있다. 다음과 같은 한 줄의 조건문을 search() 함수의 처음에 추가하는 것으로 충분.

// 간단한 가지치기: 지금까지 찾은 가장 좋은 답 이상일 경우 중단
if best <= currentLength {return}

최소한 현재 경로의 길이가 지금까지 가지고 있는 최적해보다 커졌을 때는 탐색을 종료하므로, n!개의 경로를 전부 만들어 보지는 않는다.

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
없음	89.74	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58초	981.53초	시간초과	시간초과

소형 입력 데이터 해결 시간이 1/30로 줄어듦을 확인할 수 있다. 이런 간단한 최적화로도 큰 효과를 볼 수 있다.

간단한 휴리스틱을 이용한 가지치기

휴리스틱을 이용해 답의 남은 부분을 어림짐작하는 가지치기를 이용하여 최적화할 수 있다.

조합 탐색에서 방문하는 상태의 수는 탐색의 깊이가 깊어질수록 증가하기 때문에 탐색 중 ‘이 부분에서는 최적해가 나올 수 없다’는 것을 가능한 한 일찍 알아내는 것이 유리.

어림짐작하는 휴리스틱함수. 휴리스틱의 반환값은 항상 정확한 답일 필요는 없고 그럴 수도 없다. 우리가 기대하는 휴리스틱은 '적당히 그럴듯한' 짐작을 돌려받는 것.

휴리스틱이 실제 필요한 경로보다 더 긴 경로가 필요하다고 잘못 짐작할 경우에는 최적해를 찾을 수 있는 상태를 걸러내 버리게 된다. 그러면 문제의 최적해는 영영 찾지 못한 채 종료할 수 밖에 없다. 이런 일이 일어나지 않기 위해서는 휴리스틱의 반환 값이 항상 남은 최단 경로의 길이 보다 작거나 같아야 한다.

이런 방법을 문제를 과소평가(underestimate)하는 휴리스틱, 혹은 낙관적인 휴리스틱(optimistic)라고 말한다.

휴리스틱 함수 작성하기

남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작적으로 돌아가도 된다. 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 된다.

단순한 휴리스틱 함수의 구현

인접한 간선 중 가장 짧은 간선의 길이를 더하는 것. 아직 방문하지 않은 도시를 방문하려면 인접한 간선 중 하나를 타고 가야 하므로, 이들 중 가장 짧은 간선의 길이만 모으면 실제 최단 경로 이하의 값이 될 수 밖에없다.

단순 휴리스틱 TSP 구현 🔗

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
없음	89.74	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58초	981.53초	시간초과	시간초과
단순한 휴리스틱	0.85초	84.18초	시간초과	시간초과

가까운 도시부터 방문하기

도시를 번호 순서대로 방문하는 대신, 더 가까운 것부터 방문하여 좋은 답을 더 빨리 찾아내자.

이와 같은 전략이 항상 최적해를 가져다 주는 것은 아니지만, 어느 정도 좋은 답을 좀더 일찍 발견할 확률 은 올라간다. 그리고 좋은 답을 일찍 찾을수록 가지치기를 더 많이 할 수 있다.

가까운 도시 TSP 구현 🔗

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
최적해보다 나빠지면 그만두기	2.58초	981.53초	시간초과	시간초과
단순한 휴리스틱	0.85초	84.18초	시간초과	시간초과
가까운 도시부터 방문하기	0.52초	31.03초	시간초과	시간초과

이 조합 탐색의 수행은 탐색을 시작하기전에 탐욕법으로 초기해를 구하는 것과 같은 효과를 지닌다.

지나온 경로를 이용한 가지치기

앞으로 남은 조각들의 비용을 예측하여 가지치기하는 방법이 아니라, 지금까지 만든 경로를 검사해 가지치기를 할 수도 있다.

지금까지 만든 경로가 시작 상태에서 현재 상태까지 도달하는 최적해가 아니면, 앞으로 남은 조각을 잘 선택해 봤자 최적해를 찾지 못할 것이고, 탐색을 계속할 이유가 없다.

(..., ..., p, a, b, q, here)

위와같은 경로에서 a와 b의 순서를 바꿔 보았을때, p - q구간의 거리가 더 짧아진다면 이 경로에서 최적해를 찾을 가능성이 없으니 탐색을 중단해도 된다.

지나온 경로 순서 변경 TSP 구현 🔗

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
최적해보다 나빠지면 그만두기	2.58초	981.53초	시간초과	시간초과
단순한 휴리스틱	0.85초	84.18초	시간초과	시간초과
가까운 도시부터 방문하기	0.52초	31.03초	시간초과	시간초과
인접한 두 도시 순서 바꾸는 가지치기	0.15초	4.64초	233.52초	시간초과
부분 경로 뒤집는 가지치기	0.07초	1.13초	33.29초	1160.81초

MST 휴리스틱을 이용한 가지치기의 구현

문제의 제약을 너무 많이 없애서 답을 너무 과소평가하는 경향이 있다.

좀더 현실에 가까운 답을 계산하는 휴리스틱 알고리즘이 있다면 깊이 우선 탐색의 효율에 큰 도움이 될 것이다. 좀더 현실에 가까운 답을 계산하기 위해 다음 제약을 추가한다.

1. 한 간선은 최대 한 번만 선택할 수 있다.
2. 선택하지 않은 간선을 모두 지웠을 때 그래프가 둘 이상으로 쪼개지면 안 된다.

선택한 간선들만 남겼을 때 아직 방문하지 않은 정점들과 현재 정점이 연결되어 있게끔 해야 한다는 뜻.

크루스칼의 스패닝 트리 알고리즘을 이용해 MST를 구하고 간선 가중치의 합으로부터 탐색의 하한 값을 예상하는 mstHeuristic을 구현한다.

MST Heuristic TSP 구현 하지 않음

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
부분 경로 뒤집는 가지치기	0.07초	1.13초	33.29초	1160.81초
MST	0.06초	0.37초	14.77초	836.43초

MST 휴리스틱은 단순한 휴리스틱 보다 훨씬 정확한 값을 찾아준다. 한 가지 유의할 점은 mstHeuristic()은 simpleHeuristic()보다 수행하는 데 훨씬 많은 시간을 요구한다는 것. 하지만 결과적으로 프로그램이 훨씬 빨라졌으니 가지치기에서 절약한 시간이 MST 계산에 드는 시간보다 훨씬 컸음을 알 수 있다.

마지막 단계 메모이제이션하기

같은 상태를 두 개 이상의 방법으로 방문할 수 있을 때, 이런 비효율을 메모이제이션으로 제거하는 것이 좋겠다는 아이디어를 자연스럽 게 떠올릴 수 있다. 그냥 사용하기에는 메모리가 부족할 것이다. 이 문제를 해결하기 위해, 남은 조각의 수가 미리 정해둔 수 k 이하일 때만 메모이제이션을 하자. 예를 들어 TSP의 경우, 5개 이하의 도시가 남았을 때만 메모이제이션을 하도록 하는 것. 도시의 수가 20일 때 그냥 동적 계획법을 했을 때는 약 2천만 개의 상태를 저장해야 하지만, 마지막 5단계만 메모이제이션하기로 하면 저장해야 하는 상태의 수는 다음과 같습니다.

20 * ((20/5) + (20/4) + (20/3) + (20/2) + (20/1)) == 약 440000

대략 44만 개의 상태만을 저장하면 된다. 마지막 5개의 도시를 배치하는 문제를 5! = 120번 푸는 대신에 한 번만 풀게 되니 탐색 속도가 최대 120배 빨라질 수도 있다는 것이 중점이다.

단 이와 같은 이득을 쉽게 얻을 수는 없다. 가지치기를 사용하는 함수는 쉽게 메모이제이션할 수 없기 때문. 메모이제이션을 하기 위해서는 함수의 반환 값이 현재의 상태에만 영향을 받아야 하는데, 가지치기를 적용하면 현재 상태까지 오기 위한 경로에 따라 반환 값이 달라질 수 있기 때문, 물론 경로까지 메모이제이션의 키로 사용하면 답이 틀리지는 않겠지만, 경로들은 서로 겹치지 않기 때문에 메모이제이션을 쓰는 의미가 없다. 따라서 이 방법을 이용하기 위해서는 가지치기를 사용하지 않는 동적 계획법 함수를 별도로 작성한 뒤, 마지막 k단계에 도달하면 이 함수를 사용하도록 구현해야 한다.

부분 DP TSP 구현 🔗

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
부분 경로 뒤집는 가지치기	0.07초	1.13초	33.29초	1160.81초
MST	0.06초	0.37초	14.77초	836.43초
메모이제이션	0.06초	0.28초	2.91초	25.24초

동적 계획법으로 전환하는 시점

부분 DP TSP에서는 동적 계획법으로 전환하는 시점 CACHED_DEPTH를 상수로 지정했다. 이 값을 결정하는 쉬운 방법은 없습니다. 이 값이 크면 클수록 더 많은 상태를 메모이제이션하겠지만, 원소가 많아지면 많아질수록 에 접근 하는 비용이 늘어나기 때문.

---

최종 비교

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적계획법	0.03초	0.58초	26.45초	768.21초
없음	89.74	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58초	981.53초	시간초과	시간초과
단순한 휴리스틱	0.85초	84.18초	시간초과	시간초과
가까운 도시부터 방문하기	0.52초	31.03초	시간초과	시간초과
인접한 두 도시 순서 바꾸는 가지치기	0.15초	4.64초	233.52초	시간초과
부분 경로 뒤집는 가지치기	0.07초	1.13초	33.29초	1160.81초
MST	0.06초	0.37초	14.77초	836.43초
메모이제이션	0.06초	0.28초	2.91초	25.24초

---

전문적 TSP 해결기법들

여기서 소개한 알고리즘은 TSP를 해결하기 위한 방법과는 거리가 멈 실제로는 TSP만을 해결하기 위해 고안된 프로그램들 정수계획법, 선형계획법 등을 사용함.

TSP more

https://www.math.uwaterloo.ca/tsp/index.html

---

BOARDCOVER2

가지치기

경로의 최소 길이를 구해야 했던 TSP와는 달리 여기서는 블록의 최대 개수를 찾기 때문에, 현재 답이 지금까지 찾은 최적해보다 나쁠 경우 중단하는 가지치기를 할 수 없다.

대신 이 문제에서 가지치기를 하려면 현재 상태에서 최선을 다해도 최적해보다 많은 블록을 내려놓을 수는 없다. 이렇게 가장 큰 답을 찾는 최적화 문제에서 낙관적인 휴리스틱들은 문제를 과소평가하는 대신에 과대평가한다.

즉, 실제로 놓을 수 있는 블록 수 이상을 항상 반환해야 한다.

이런 휴리스틱 함수를 만드는 쉬운 방법은 블록을 통째로 내려놓아야 한다는 제약을 없애서, 블록들을 한 칸씩 쪼개서 놓을 수 있도록 문제를 변형하는 것. 그러면 우리가 놓을 수 있는 블록의 수는 단순히 남은 빈 칸의 수를 블록의 크기로 나눈 것이 된다.

이 값은 항상 우리가 실제 놓을 수 있는 블록의 수 이상이기 때문에, 우리가 얻을 수 있는 답의 상한이 된다. 이 답의 상한이 현재 찾은 최적해 이하라면 더이상 탐색을 수행할 필요가 없다.

BOARDCOVER2 구현 🔗

---

ALLERGY

집합 덮개

계산 이론 쪽에서는 가장 유명한 NP 완비(NP complete) 문제 중 하나이다.

Slow Search

위 코드는 m이 최댓값일 경우 대략 백만 개의 상태를 탐색한다. 얼핏 생각하면 그렇게 큰 수가 아닌 것 같지만, 이 코드를 작성해 제출해보면 시간 안에 동작하지 않음을 알 수 있다.

최적화 방식

• 다음으로 만들 음식을 고를 때 아직 먹을 음식이 없는 친구들 중 가장 많은 사람이 먹을 수 있는 음식부터 시도하기
• 휴리스틱을 이용한 가지치기 해 보기
• 아직 먹을 음식이 없는 친구들의 수가 적은 경우들을 메모이제이션으로 해결하기
• 음식 a를 먹을 수 있는 친구들의 목록이 음식 b를 먹을 수 있는 친구들의 목록을 포함할 때 음식 b를 만들 필요가 없으므로 무시하기
• 탐욕적 알고리즘으로 적절한 초기해 만들기

이런 최적화를 통해 수행시간을 제한 안으로 최적화할 수도 있지만, 사실 이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것이다. 각 음식을 만들 것인가 여부를 선택하는 대신에, 매 재귀 호출마다 아직 먹을 음식이 없는 친구를 하나 찾은 뒤 이 친구를 위해 어떤 음식을 만들지를 결정하는 것

Search

왜 더 빠른가 ?

• search()는 항상 모든 친구가 먹을 음식이 있는 조합만을 찾아낸다. 반면 slowSearch()는 마지막 조각까지 결정한 뒤에도 배고픈 친구가 남는 경우들도 모두 탐색하기 때문.
• search()는 한 번 호출될 때마다 항상 음식을 하나 하게된다. 반면 sS는 음식을 하지 않고도 재귀 호출을 할 수 있다. sS의 깊이는 항상 m으로 고정되는 반면 s탐색의 깊이는 답과 같은데 답은 항상 m이하의 숫자다.
• sS에서는 반드시 필요하지 않은 음식도 만드는 경우가 있다. 이 음식을 먹을 수 있는 친구들은 이미 다 먹을 음식이 있는 경우, 반면 s에서는 음식을 한다는 말은 그 음식이 필요한 친구가 반드시 있다는 의미이다.

이 문제와 비슷한 형태를 갖는 문제들에서 이렇게 탐색 방향을 바꾸면 훨씬 빠른 수행 속도를 얻을 수 있는 경우가 많다.

더 최적화 하기

• 아직 먹을 것이 없는 첫 번째 친구를 찾는 것이 아니라, 먹을 수 있는 음식의 종류가 적은 친구를 찾도록 한다. 두 가지 음식만 먹을 수 있는 친구에게 어느 음식을 해 줄지 결정하기가 열가지 음식을 먹을 수 있는 친구에게 어느 음식을 해 줄지 결정하기보다 쉽다. 열 가지 음식을 먹을 수 있는 친구는 우리가 따로 챙겨주지 않아도 먹을 걸 찾을 가능성 또한 높다.
• 음식을 선택할 때, 가장 많은 사람이 먹을 수 있는 음식부터 시도한다. 한 명만 먹을 수 있는 음식은 가능하면 마지막에 방법이 없을 때 시도하는게 좋다.

이와 같은 기법들은 좀더 좋은 답을 초반에 찾아내서 가지치기를 더 잘 할수 있도록 도와준다.

---

KAKURO

제약 전파

답의 일부를 생성하고 나면 문제의 조건에 의해 다른 조각의 답에 대해 알게 되는 것을 제약 전파(constraint propagation)라고 부른다.

제약 전파가 항상 다른 조각의 답을 정확히 알아내는 것은 아니지만, 한칸에 4를 썼을 때 다른 칸에 들어갈 값을 알 수 없더라도, 이들에는 더이상 4가 들어갈 수 없다는 사실을 알아내는 것 또한 제약 전파라고 한다.

제약 전파는 답의 일부를 생성한 뒤 여기서 얻을 수 있는 정보를 최대한 많이 찾아내는 것.

제약 전파를 이용하면 실제 탐색해야 할 탐색 공간의 수가 크게 줄어든다.

채울 순서 정하기

• 변수 순서 정하기(variable ordering) - 어느 빈 칸부터 채워나갈지를 결정
• 값 순서 정하기(value ordering) - 이 빈 칸에 어떤 숫자부터 채워나갈 것인지를 말한다.

후보의 수 계산하기

어떤 힌트에 대한 정보가 주어질 때, 이 힌트에 해당하는 칸들에 들어갈 수 있는 후보 숫자들의 목록을 반환하는 함수 구현

getCandidate(len, sum, known[])

후보 구하기 구현 🔗

후보의 수 빠르게 계산하기

메모이제이션 구현 🔗

더 읽을 거리

http://norvig.com/sudoku.html

---