수도쿠 퍼즐을 통해서 살펴본 SAT에서 전처리 효과*
권 기 현**
Effect on Preprocessing in SAT with Sudoku Puzzle*
Gihwon Kwon**
Abstract
The concept of preprocessing is widely used in various computer science area such as compiler and software engineering for the purpose of macro processing and optimization. In addition, preprocessing is also used in SAT solvers in order to eliminate redundant literals and clauses to speed up its solving time before searching the state space.
However, there is an unexpected run-time error such as stack-overflow during this step, in case the size of a given set of clauses is huge which impedes SAT solvers. In this case, the preprocessing should be applied at the encoding time to optimize its size. In this paper this idea is applied to several Sudoku problems. As a result, significant improvements are obtained with respect to the number of variables and clauses as well as the solving time compared to the previous works.
Keyword：Satisfiability, Clause, Preprocessing, Sudoku
논문투고일：2008년 04월 21일 논문수정완료일：2008년 06월 03일 논문게재확정일：2008년 06월 05일
* 이 논문은 2005학년도 경기대학교 교원 교비 해외파견 연구비 지원에 의해 연구되었음.
** 경기대학교 컴퓨터과학과 교수
1. 서 론
전처리(preprocessing)는 컴퓨터 과학의 다양한 분야에서 널리 사용된다. 전처리란 단어 그대로 본 격적인 작업 이전에 처리하는 활동을 일컫는다. 매 크로 처리, 최적화 등이 대표적인 전처리 활동의 예 이다.
이러한 전처리 개념은 이진 변수의 만족가능성 (satisfiability)을 검사하는 SAT 분야에서도 널리 사용된다. 대부분의 SAT 처리기 내부에는 전처 리 기능이 있다[2]. 처리기는 입력된 절(clause) 집 합의 만족가능성을 검사하기 전에 전처리 기능을 통해서 불필요하거나 중복된 절들을 미리 제거한 다. 전처리를 통해서 절을 최적화한 후에 만족가 능성을 검사한다.
그러나 입력된 절 집합이 거대한 경우에는 전처 리 기능을 실행하는 도중에 메모리 오버플로우 등 으로 인해서 처리기 실행이 중단되는 경우가 있 다. 이러한 문제점을 개선하기 위해서 전처리 기 능을 처리기 내부가 아닌 외부에서 처리기와는 독 립적으로 실행하는 연구도 있다[7]. 이러한 연구 역시 앞의 경우와 마찬가지로 절 집합이 거대하면 실행 도중에 멈출 수 있다.
본 연구에서는 다음 [그림 1]과 같이 전처리 수 행 시점을 초기, 중기, 말기로 구분한다. 처리기 내부에서 수행되는 시점은 말기, 처리기 앞쪽에서 수행되는 시점을 중기라고 한다. 말기, 중기와는 달리 절 집합을 생성하는 인코딩 시점에서 수행되 는 전처리를 초기라고 부른다. 본 논문에서는 기 존 연구와는 달리 절 집합을 생성하는 초기 단계 에서 전처리를 적용해서 최적화된 절 집합을 생성 하는 개념을 제시하고 이를 수도쿠 퍼즐에 적용한 다. 기존 수도쿠 연구에서는 절 집합 생성만을 언 급하고 이를 최적화하는 것은 SAT 처리기나 독 립적인 전처리 도구에 일임시키는 것에 비해, 본 논문에서는 인코딩 시작 시점부터 전처리 개념을 적용해 최적화된 절 집합을 생성코자 한다. 마치, 암을 말기 보다는 초기에 발견하는 것이 유리한
것과 같은 개념이다. 최적화와 관련된 연구 경험 축적은 대규모 문제 풀이에 필수적이다. 단순하면 서도 다양한 크기를 퍼즐이 이러면에서 유용하다 고 판단해서 수도쿠를 선택했다.
[그림 1] 전처리 실행 시점：초기-③, 중기-②, 말기-①
본 논문에서는 대부분의 처리기에서 널리 사용 되는 단일 절 전파 규칙을 인코더 내에 구현하였 다. 그 결과 매우 축소된 절 집합이 생성되었고 이전의 인코딩과 비교해서 큰 성능 개선이 있었 다. 예를 들어 기존 방법으로는 풀리지 않았던 81
×81 수도쿠를 풀었을 뿐만 아니라 최대 144× 144까지도 풀었다.
이러한 방법의 단점은 인코딩에도 일정 비용, 즉 시간이 소요된다는 것이다. 그러나 크기가 큰 경 우, 즉 생성되는 절 집합이 거대한 경우에는 절 크기가 줄어들기 때문에 오히려 인코딩 시간도 줄 었다. 따라서 절 집합 크기가 거대한 경우에는 인 코딩 및 처리기 시간 모두에서 유리한 방법이다.
본 논문의 구성은 다음과 같다. 제 2장에서는 이 진 변수의 만족가능성을 설명한다. 그리고 제 3장 에서는 수도쿠 인코딩과 관련된 기존 방법과 제안 한 방법을 비교 설명한다. 그리고 제 4장에서는 제안한 방법을 이용해서 다양한 크기의 문제를 실 험한 결과를 소개한다. 결론 및 향후 연구는 제 5 장에서 기술한다.
2. 배경 지식
이진 만족가능성 문제란 주어진 명제 논리식이 만족가능한지를 결정하는 것이다[1]. 그리고 이것 을 줄여서 SAT 문제라고 부르고, 소프트웨어 공 학 및 인공지능을 비롯해서 컴퓨터 과학의 여러 분야에서 널리 활용되고 있다[8].
주어진 문제를 SAT 문제로 간주하기 위해서는 문제를 SAT의 입력 언어인 CNF(Conjunctive Normal Form)로 먼저 변환해야 한다[5]. CNF는 특별한 구문 형식을 갖는 명제 논리식이다.
• 정의(CNF 논리식)
리터럴(literal)은 명제 변수 혹은 이것의 부정 이다. 절(clause)은 이러한 리터럴의 논리합이다.
그리고 CNF 논리식은 절의 논리곱이다.
용이한 기계 처리를 위해서 CNF 논리식을 다 음과 같은 절 집합으로 표현한다.
• 정의(절 집합)
를 각각 리터럴, 절, 절 집합이라 하자.
절은 리터럴의 모임으로서 ∈ 이며, 절 집합은 절의 모임으로서 ∈이다.
예로서 CNF 논리식 ∧ ∨ ∧∨에 해당되는 절 집합은 이다.
• 정의(절 집합의 해석)
절 집합에 출현한 변수의 모임을 라고 하자.
해석 → 는 이진 변수에 참() 또는 거 짓()을 배정하는 함수이다.
절 집합의 가능한 해석 수는 집합 의 크기에 좌우된다. 만약 이라면 해석 총수는 이다.
예로서 절 집합 에는 8개 의 해석이 있다. ↦ ↦ ↦는 그 중 의 하나이다.
• 정의(절 집합의 만족가능성)
절 집합 를 참이 되게 하는 해석 가 존재한다 면 절 집합은 만족가능(satisfiable)하다. 표기는
⊨이다. 그리고 이러한 해석을 모델(model)이라 고 부른다. 모델의 의미를 재귀적으로 정의하면 다음과 같다.
⊨ iff
⊨ iff
⊨ iff ∃∈⋅⊨
⊨ iff ∀ ∈⋅⊨
예를 들어 절 집합 은 만 족가능하다. 모델 ↦ ↦ ↦이 존재 하기 때문이다. 그러나 은 만 족불능(unsatisfiable)이다. 왜냐하면 모델이 존재 하지 않기 때문이다.
• 정의(변수 집합 분할)
모델 하에서 이진 변수 집합 를 참 값과 거 짓 값을 갖는 두 개의 부분 집합으로 분할할 수 있다. 즉, ∪ 여기서
∈
∈
예로서 을 위한 모델
↦ ↦ ↦ 을 가정하자. 이러한 경우
는 , 로 분할된다.
• 정의(만족가능성 관점에서의 동치)
′를 절 집합이라고 하자. 만족가능성 입장 에서 두 집합이 동치일 때 ≈′로 표시한다.
만족가능성 관점에서 동치라고 해서 논리적 동 치는 아니다. 이러한 차이점을 강조하기 위해서 기 호≡대신에≈를 사용했다. 원래 절 집합 에다 어떤 변환을 적용해서 얻은(물론 크기가 더 줄어든) 절 집합을 ′이라고 하자. 두 개의 절 집합이 만족 가능성 관점에서 동일하다면 보다 더 적은 ′을 이용해서 만족가능성 검사를 수행하는 것이 유리 하다.
• 정리(단일 절 전파)
∈ 을 단일 절(unit clause) 이라고 하자.
로부터 이 포함된 절은 모두 제거하고 그리고 이것의 부정인 이 포함된 절은 리터럴 만을 제거해서 (절은 그대로 남아있음) 얻은 절 집합을
′이라고 하자. 그렇다면 ≈′이다.
증명： 를 의 모델이라고 가정하자. 그런 후 하에서 모든 ′∈′값이 참, 즉 ′ 임을 보이도록 한다. 가 의 모델이기 때문에 모든 절 ∈은 이다. 그리고 ,
이다. 만약 ∈ 이라면 이 되도록 하기 위해서 다른 리터럴이 존재한다. 따라서 부 정 리터럴을 제거한 절 ′ 은 하에 서 참이다. 즉, ′ 이다.
단일 절 전파는 SAT 관련 분야에서 가장 널리 사용되는 단순화 규칙 중의 하나로서 다음 장에서 절 집합을 축소시키는데 핵심적으로 사용된다. 예 를 들서 다음 절 집합을 고려하자.
′
에서 은 삭제될 단일 절이다. 그래서 를 위한 모든 모델에서 이다. 그렇다면 절
이 만족되기 위해서는 이 만족되 어야 한다. 따라서 ≈′이다.
3. 수도쿠 퍼즐 사례
전처리 수행 시점을 살펴보기 위한 예제로서 본 논문에서는 [그림 2]와 같은 수도쿠 퍼즐을 다룬 다. 수도쿠는 셀에 들어갈 숫자를 선택하는 퍼즐 로서 × 수도쿠에는 셀, 행, 열, 그리고
× 블록이 개 있다. 각 셀은 두 가지로 구분되는데 숫자가 미리 배정된 고정 셀이거나 또 는 비어있는 자유 셀이다. 자유 셀에 ⋯ 중에 서 하나의 숫자를 배정해야 한다. 이때 같은 행, 같은 열, 같은 블록에 있는 숫자와 중복되지 않는 숫자를 골라야 한다.
[그림 2] 수도쿠
× 수도쿠 문제를 절 집합으로 표현하기 위 해서 다음과 같은 이진 변수 집합을 사용한다.
≤ ≤ ≤ ≤ ≤ ≤
사용된 변수는 개이다. 셀마다 개의 가능 성을 고려해야 하기 때문이다. 여기서 이진 변수
는 행, 열에 숫자 가 배정됨을 나타낸다.
약속된 이진 변수 집합을 이용해서 수도쿠를 절 집합으로 표현해 보자. 편의상 다음과 같이 일반 화된 합집합 연산자를 다중 정의해서 사용한다.
⋯
⋯ ⋯
⋯
⋯
⋯
⋯
수도쿠 퍼즐을 위해 여러 인코딩 기법이 제안되 었다[5, 9]. 그 중에서 널리 사용되는 것이 [5]에서 제시된 확장 인코딩(extended encoding)이다. 본 논문에서는 일반화된 합집합 연산자를 이용해서 확장 인코딩을 절 집합 형식으로 재정의한다.
SAT 처리기의 입력 언어인 CNF는 표현력이 낮기 때문에 “하나(exactly one)”를 바로 표현할
수 없다. 대신 “최소한 하나(at least one)”와 “최 대한 하나(at most one)”의 논리곱으로 표현한다.
따라서 “각 셀은 하나의 숫자만을 갖는다”를 두 가지로 나누어 표현해야 한다. 먼저, 각 셀에 최소 한 하나의 숫자가 배정된다는 것을 절 집합으로 표현하면 다음과 같다.
이어서, 셀은 최대한 하나의 숫자를 갖는다는 것을 표현하면 다음과 같다.
각 셀은 정확히 하나의 숫자만을 갖는다는 것을 나타내기 위해서는 위의 두 집합을 합해야 한다.
즉, 이것을 합한 ∪이다. 이 같은 방식으로 각 행, 열, 블록에 하나의 숫자가 배정된다는 것을 나타내면 다음과 같다.
특히 블록 정의에서 사용된 는 모듈로 연 산을 나타낸다. 위에서 정의된 8개의 절 집합은 수 도쿠 규칙을 CNF로 표현한 것이다. 수도쿠를 풀 기 위해서는 이들 외에 값이 미리 주어진 고정 셀을 표현해야 한다.
고정 셀은 단일 절로 표현할 수 있다. 이를 위해 서 고정 셀을 나타내는 이진 변수 집합 ⊆ 를 식별할 필요가 있다.
여기서 은 수도쿠 퍼즐을 표현한 2차원 배열 이다. 개의 고정 셀을 단일 절 집합으로 표현하면 다음과 같다.
∈
따라서 수도쿠 퍼즐을 풀기 위해서는 위에서 언 급한 절 집합을 모두 합해야 한다.
∪∪∪∪∪∪∪∪
여기서 등은 위에서 정의된 바와 같이 각 수도쿠 규칙을 나타낸 절 집합이다. 이와 같은 인 코딩 방식으로 생성된 절 집합 크기는 다음과 같다.
크기의 절이 생성되기 때문에 크기가 큰 수도쿠인 경우 현재의 SAT 처리기 수준을 넘는 거 대한 절 집합이 생성된다. 예로서 81×81 수도쿠 를 인코딩한 결과 무려 85,060,787절이 생성되었 다. 절의 수가 너무 커서 SAT 처리기의 전처리기 를 실행하는 도중에 스택 오버플로우 에러가 발생 했다. 절의 수를 줄이기 위해서 NiVER와 같은 독립적인 전처리 도구를 사용하였다. 마찬가지로, 실행 도중에 스택 오버플로우 에러가 발생했다.
거대한 절 집합을 갖는 문제를 다루기 위해서는 전처리 기능을 조기에 활용해야 한다. 그래서 본 논문에서는 절 집합을 생성하는 단계에서 중복된 절과 리터럴을 제거해서 절 집합을 최대한 축소시 키는 것이 바람직하다고 주장한다.
수도쿠 인코딩을 위해 사용된 이진 변수 집합을 다음과 같이 분할할 수 있다.
∪∪
전 장에서 언급한 바와 같이 는 참 값을 갖 는 이진 변수 모임이고, 는 거짓 값을 갖는 이 진 변수 모임이다. 반면에 에 속한 이진 변수 의 진리값은 아직 미정이다(unknown). 앞에서와 같이 고정 셀을 통해서 를 쉽게 식별할 수 있 다. 만약 ∈라면 같은 행, 같은 열, 같은 블록에는 숫자 가 위치할 수 없다. 따라서 거짓 값을 갖는 이진 변수 집합 는 다음과 같다.
∃
′′′∈ ′ ∧ ′∧≠′
∨ ′ ∧≠′∧ ′
∨ ≠′ ∧ ′∧ ′
∨
≠′ ∨≠′∧ ′∧
∃ ≤ ′ ≤
∧≤ ′ ≤
는 긍정의 리터럴을 갖는 집합이고, 는 부정 리터럴을 갖는 집합이기 때문에 이 두 개의 절 집합을 이용해서 에다 단일 절 전파 규칙을 적용해서 ′을 구할 수 있다. 원래 절 집합과 축 소된 절 집합은 ≈′이다. 즉 만족가능성 관점 에서 두 개는 동치이다. 더군다나 ′의 크기가 보다 월등히 줄어들었기 때문에 더 적은 자원으로 문제를 풀이할 수 있다. 즉 축소된 절 집합 ′는 진리값이 아직 결정되지 않는 에 속하는 변수 들에 의해서 정의된 절 집합이고, 이것을 SAT 처 리기에 입력하면 처리기는 절 집합을 만족하는 모 델을 찾고, 모델은 자유 셀에 들어갈 숫자를 결정 한다.
4. 실 험
제안한 아이디어의 정확성을 실제적으로 확인하 기 위해서 자바로 인코딩 프로그램을 작성했다. 이 프로그램은 수도쿠 문제를 입력받아서 SAT 처리 기에 입력될 절 집합을 생성한다. 절 집합을 생성 할 때 전처리를 미리 적용함으로써 생성된 절 집 합에는 중복성이 제거된 절 집합이 생성된다. 절 집합을 다루는 SAT 처리기로는 MiniSAT 버전 1.1.4를 사용했다. 실험 환경은 Windows XP sp2 이며 CPU는 Intel® Core™2 Duo CPU E6750 2.66GHz이며 메모리는 2G를 사용하였다.
<표 1> 다양한 크기에 적용한 실험 결과
기존 방법 제안한 방법
변수 절 시간 변수 절 시간
9×9 729 11988 0.03 187 1279 0.02 16×16 4096 123904 0.13 475 3785 0.02 25×25 15625 752500 0.78 1990 24137 0.06 36×36 46656 327114 4.83 3673 45383 0.08 49×49 117650 11303908 14.13 7642 112444 0.17 64×64 262144 24779088 43.78 11440 169772 0.29
81×81 17793 266024 0.33
100×100 36620 889591 1.16
144×144 38521 596939 0.75
다양한 크기의 문제를 실험한 결과가 <표 1>
에 있다. <표 1>은 세 열로 구성되는데 첫 번째 열은 문제의 크기를 나타내고, 두 번째 열은 기존 연구에서 가장 널리 사용되는 [5]의 방법을 사용 한 결과이고, 세 번째 열이 제안한 방법으로 실험 한 결과이다. 표에서 음영 표시는 스택 오버플로 우가 발생한 경우를 나타낸다. 결과에서 보듯이 기존 방법보다는 제안한 방법이 월등히 우수함을 볼 수 있다. 예를 들어 81×81는 기존 방법으로 풀 수 없었다. 왜냐하면 85,060,787 크기의 거대한 절을 SAT 처리기의 현재 기술로 다루기는 어렵 다. 그러나 제안한 방법으로 생성된 절은 불과
266,024 였다. 1초도 걸리지 않아서 모델을 찾아 내었다. 뿐만 아니라 본 실험에서는 최대 144× 144 수도쿠도 풀었다. 이것 역시 SAT 처리기 실 행 시간이 채 1초도 되지 않았다. 신문이나 잡지 에서 등장하는 수도쿠의 크기는 보통 9×9이다.
우리가 실험에서 풀어낸 81×81, 100×100, 141× 141 크기가 얼마나 큰 것인지를 상대적으로 비교 한 것은 의미가 있다고 판단해서 이를 아래 [그림 3]과 같이 비교해 보았다. 그림을 통해서 일반적 인 9×9에 비해서 144×144이 얼마나 큰 것인지 를 쉽게 이해할 수 있을 것이다.
[그림 3] 실험에서 사용된 문제의 상대적 크기 비교 주목할 것은, 144×144이 오히려 100×100보다 더 쉽게 풀렸다는 것이다. 실험에서 사용된 두 문 제의 경우 비록 144×144은 크기가 컸지만 미리 숫자가 주어진 고정 셀이 많아서, 오히려 자유 셀 을 많이 갖고 있는 100×100보다도 절들이 더 많 이 축소되었다. 표에서 제시된 숫자는 SAT 처리 기 실행 시간만을 기록했다. 문제의 크기가 클수 록 생성된 절 집합의 크기가 크게 줄어들기 때문 에 인코딩에 소요되는 시간도 기존 방법에 비해서 크게 줄어들었다.
제안한 방법의 성능 개선을 시각적으로도 보이 는 것이 좋겠다고 판단해서 CNF 절 집합을 시각 화하는 도구인 DPvis[6]를 이용해서 동일한 문제 를 기존 방법과 제안한 방법으로 인코딩한 것을 비교했다. 사용된 문제는 [그림 2]에 있는 퍼즐이
다. [그림 4]와 [그림 5]에서 보듯이 제안한 방법 으로 생성된 절 집합이 기존 방법에 비해서 크게 줄어들었음을 알 수 있다.
[그림 4] 기존 방법으로 인코딩한 결과
[그림 5] 제안한 방법으로 인코딩한 결과
5. 결 론
SAT 문제는 소프트웨어 공학을 비롯해서 여러 분야에서 널리 활용되고 있다. SAT을 이용해서 문제를 풀이하다 보면 낮은 CNF의 표현력 때문 에 거대한 절 집합이 생성되는 경우가 많다. 여기 서 거대한 절 집합이라 함은 보통은 절 집합의 크 기가 수천 만개인 경우이다. 이러한 거대한 절 집 합은 SAT 처리기를 종종 위협한다. 그 결과 문 제의 해가 존재함에도 불구하고 자원(시간 및 메
모리)의 한계로 인해서 해를 찾지 못하게 된다.
이러한 문제점을 개선하기 위해서 본 논문에서 는 수도쿠 퍼즐의 예를 들어서, 절 집합의 크기가 거대한 경우 인코딩 시점부터 전처리 기능을 적용 해서 최적화된 절 집합을 생성하는 것이 바람직하 다고 주장하고 실험을 통해서 그 주장의 정확성을 확인했다. 본 논문의 기여는 다음과 같다.
첫째, 기존에 제시된 CNF 논리식 위주의 수도 쿠 인코딩을 절 집합 형식으로 재정의 했다. 논리 곱과 논리합으로 구성된 논리식 표현보다는 절 집 합 표현이 이해와 규칙 적용에 용이하다.
둘째, 기존 선행 연구에서 다루었던 최대 크기 는 81×81였다[4]. 본 실험에서는 이를 보다 크기 가 훨쒼 큰 100×100, 144×144을 다루었다. 중간 크기인 121×121도 풀려고 인터넷을 수없이 검색 했지만 결국 찾지 못했다.
마지막으로, 수도쿠와 같은 퍼즐을 논리적으로 풀이하는 예제는 교육에 유용하다.1) 비록 주관적 이기는 하지만 저자는 정형 논리를 강의할 때 이 러한 예제를 사용함으로써 학생들에게 논리에 대 한 이해를 높였다고 판단한다.
참 고 문 헌
[1] Davis, M., G. Logemann, and D. Loveland,
“A Machine Program for Theorem Pro- ving”, Communications of the ACM, Vol.5,
1) http://kuic.kyonggi.ac.kr/~khkwon/03-teaching/
discrete-mathematics/index.html
No.7(1962), pp.394-397.
[2] Een, N. and N. Sorensson, “An Extensible SAT Solver”, in The Proceedings of SAT, 2003.
[3] Huth, M. and M. Ryan, Logic in Computer Science, Cambridge university Press, 2004.
[4] Kwon, G. and H. Jain, Optimized CNF En- coding for Sudoku Puzzles, in the Proceed- ings of LPAR, 2006.
[5] Lynce, I. and J. Ouaknine, “Sudoku as a SAT problem”, in the Proceedings of AI MATH, 2006.
[6] Sinz, C. and E. M. Dieringer, “DPvis - a Tool to Visualize Structured SAT Instan- ces”, in the Proceedings of SAT, (2005), pp.
257-268.
[7] Subbarayan, S. and D. Pradhan, “NiVER：
Non increasing Variable Elimination Re- solution for Preprocessing SAT Instan- ces”, in the Proceedings of SAT, 2004.
[8] Velev, M. N., “Tuning SAT for Formal Verification and Testing”, Journal of Uni- versal Computer Science, Vol.10, No.12 (2006), pp.1559-1561.
[9] Weber, T., “A SAT-based Sudoku Solver”, in the Proceedings of LPAR, (2005), pp.11- 15.
저 자 소 개
권 기 현 ([email protected])
경기대학교에서 전자계산학 학사를 받았고, 중앙대학교에서 소프트웨어 공학 전공으로 석사 및 박사 학위를 받았다. 현재 경기대학교 컴퓨터과 학과 교수로 재직 중이며 시스템통합기술원, 한국소프트웨어공학협회, 한 국IT지적재산관리학회에서 이사로 봉사하고 있다. 주요 관심분야로는 소 프트웨어공학, 정형기법, 웹 서비스 등이 있다. 주요저서로는 컴퓨터과학 을 위한 논리(2008), 퍼스널 소프트웨어 프로세스 입문(2003), 소프트웨어 공학(1996) 등이 있다.
