이 알고리즘으로 UI를 구현한 Sudoku solver는 http://sunnyholic.com/100 여기 있습니다.
자바로 동일하게 작성한 코드는 http://sunnyholic.com/80 입니다.
비트마스크로 최적화 한 코드는 글의 맨 아래를 봐주세요.
빈 칸중 들어갈 수 있는 수의 경우가 제일 적은 칸을 선택하여 수를 삽입한 뒤 재귀적으로 풀고
오답이면 백트래킹 하고 정답이 나오면 종료하는 알고리즘 입니다.
C처럼 보이지만 C문법을 따르진 않았습니다.
함수 메인 제외 5개
1. init() : 간편하게 행 열 섹터를 순차적으로 순회하기 위해 미리 순회 순서를 찾아놓음.
2. sizeofNumset(Set set) : 가능한 숫자 셋트에서 그 숫자들을 세어 개수를 리턴
3. findAblNum(int rn,int cn) : (rn,cn)칸에 가능한 숫자 셋트 리턴
4. findMinPossible() : 가장 가능한 숫자가 적은 칸을 찾아서 리턴
5. solve() : 재귀함수로 문제 탐색. 정답시 true 오답시 false 리턴
#include <stdio.h>
char sudoku[9][9+1]; //9x9 스도쿠판. +1은 여유공간
char* r[9][9]; //스도쿠판의 행 우선 참조
char* c[9][9]; //스도쿠판의 열 우선 참조
char* s[9][9]; //스도쿠판의 3x3 섹터 우선 참조
typedef struct {int rn, cn; bool num[9];} Set; //rn cn 칸에 가능한 숫자 세트
void init() { //참조 포인터 초기화
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
r[i][j] = c[j][i] = &sudoku[i][j];
for (int rn = 0; rn < 9; rn += 3)
for (int cn = 0; cn < 9; cn += 3)
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
s[rn + (cn / 3)][i * 3 + j] = &sudoku[rn + i][cn + j];
}
inline int sizeofNumset(Set set) { //가능한 숫자 개수 카운터
bool *n=set.num;
return n[0]+n[1]+n[2]+n[3]+n[4]+n[5]+n[6]+n[7]+n[8];
}
Set findAblNum(int rn, int cn) { //해당 칸의 가능한 숫자 세트 탐색
Set nums = { rn, cn, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; //true로 초기화
int sn = rn / 3 * 3 + cn / 3; //섹터 번호 구함
for (int i = 0; i < 9; i++) {
//행(*r),열(*c),섹터(*s) 탐색
if (*r[rn][i] > 0) //채워져 있으면
nums.num[*r[rn][i] - 1] = false; //마킹
if (*c[cn][i] > 0)
nums.num[*c[cn][i] - 1] = false;
if (*s[sn][i] > 0)
nums.num[*s[sn][i] - 1] = false;
}
return nums;
}
Set findMinPossible() { //가장 경우의 수가 적은칸의 세트 리턴
int size = 10;
Set minset = { -1, -1 };
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (sudoku[i][j] > 0) continue; //채워진칸 무시
Set temp = findAblNum(i, j);
int nsize = sizeofNumset(temp);
if (!nsize) //빈칸인데 가능한 숫자가 없으면
return Set { 10, 10 }; //오답 표시 리턴 (C++11 이상)
else if (nsize == 1) //가능한 숫자가 하나일 경우 바로 리턴
return temp;
else if (nsize < size) {
size = nsize;
minset = temp;
}
}
}
return minset;
}
bool solve() {
Set set = findMinPossible(); //가장 경우의 수가 적은 칸 탐색
if (set.rn > 9) //불가능한 칸이 있음을 뜻함
return false;
if (set.rn < 0) //더 이상 빈칸이 없음을 뜻함.
return true; //풀린것!
for (int i = 1; i <= 9; i++) { //숫자 1~9를 채우는 부분
if (!set.num[i - 1]) continue; //불가능한 숫자는 스킵
sudoku[set.rn][set.cn] = i; //가능한 숫자를 채움
if (solve()) //채운걸 풀어봄
return true; // 그게 풀렸으면 탈출
}
// 채울 수 있는 숫자가 없거나 다 채워봤는데 안된거니까
sudoku[set.rn][set.cn] = 0; //지우고
return false; //오답 리턴
}
int main() {
init(); //참조 포인터 초기화
char input[10]; //입력
//문자를 숫자로 변환
for (int i = 0; i < 9; i++) {
scanf("%s", input);
for (int j = 0; j < 9; j++)
sudoku[i][j] = input[j] - '0';
}
printf("%s\n", solve() ? "[Solved]" : "[No solution]"); //풀어
//결과 출력
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
printf("%d", sudoku[i][j]);
printf("\n");
}
}
0은 빈칸으로 간주됩니당.
한줄에 9글자
총 9줄이 입력되면 시작합니다.
표준입력
표준출력
findAblNum(int rn,int cn) 함수 이해를 돕기 위해 findAblNum(5,3)일때 탐색하는 칸 범위 그림 첨부합니다.
rn,cn칸에 삽입 가능한 숫자 세트를(Set 구조체) 1,2,3,4,5,6,7,8,9 이 모든 숫자가 삽입 가능한걸로 초기화를 합니다.
그 다음 보라색 칸들을 탐색하며 보라색 칸들에 있는 숫자들을 초기값에서 하나씩 지워갑니다.
즉 보라색 칸에 1이 있다 하면 삽입 가능한 숫자는 2,3,4,5,6,7,8,9가 되는것이고
또 9가 있다 하면 2,3,4,5,6,7,8이 되는 것입니다.그리고 가능한 숫자 세트에서 모든 보라색칸 숫자를 뺀 세트를 리턴합니다.
findMinPossible() 함수는 스도쿠판 내의 모든 빈칸에 대해 findAblNum을 수행하여 가장 삽입 가능한 숫자가 적은 칸의 Set를 얻어옵니다.
사실 Set 구조체에서 불리언 배열보다는 비트마스크를 사용하는편이 더 좋지만 이해도를 위해 단순 불리언 배열을 사용했습니다.
비트마스크를 쓰면 컴파일러 개별적으로 true인 비트 개수를 리턴해주는 함수가 따로 존재하기 때문에 sizeofNumset 함수를 따로 구현 할 필요가 없습니다.
또한 char형보다 int형으로 연산하는게 훨신 나은 성능을 보여줍니다.
아래는 sizeofNumset 함수를 컴파일러 내장 함수로 대체하고 불리언 배열 대신 비트마스크와 char형 대신 int형을 쓴 코드입니다.
비트마스크에서 sizeofNumset 함수랑 똑같은 기능을 하는 함수를 쓰는 방법은
Visual C++에선 intrin.h 헤더 파일을 include하고 __popcnt 함수를 쓰면 되고.
gcc에선 바로 __builtin_popcount 함수를 쓰면 됩니다.
'프로그래밍/알고리즘 > C++' 카테고리의 다른 글
| [C++] 구간트리 (Binary Indexed Tree) - 구간 최대,최소값 (1) | 2015.08.12 |
|---|---|
| [C++] 펜윅트리 (이진 인덱스 트리) - 구간합 구해주는 트리 (0) | 2015.07.28 |
| [C++] 비트 마스크 배열 (큰 비트 마스크) (0) | 2015.07.27 |
| 트리 최적 노드 삽입 순서 (0) | 2015.07.09 |
| 버블 정렬 알고리즘 오름차순 (0) | 2015.07.08 |