본문 바로가기

프로그래밍/알고리즘/C++

[C++] 창작 스도쿠 푸는 알고리즘

이 알고리즘으로 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 rncnbool num[9];} Set//rn cn 칸에 가능한 숫자 세트

 

void init() { //참조 포인터 초기화

   for (int i = 0i < 9i++)

       for (int j = 0j < 9j++)

          r[i][j] = c[j][i] = &sudoku[i][j];

   for (int rn = 0rn < 9rn += 3)

       for (int cn = 0cn < 9cn += 3)

          for (int i = 0i < 3i++)

              for (int j = 0j < 3j++)

                 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 rnint cn) { //해당 칸의 가능한 숫자 세트 탐색

   Set nums = { rncn111111111 }; //true 초기화

   int sn = rn / 3 * 3 + cn / 3;    //섹터 번호 구함

   for (int i = 0i < 9i++) {

       //(*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 = 0i < 9i++) {

       for (int j = 0j < 9j++) {

          if (sudoku[i][j] > 0continue;    //채워진칸 무시

          Set temp = findAblNum(ij);

          int nsize = sizeofNumset(temp);

          if (!nsize)   //빈칸인데 가능한 숫자가 없으면

              return Set { 1010 };  //오답 표시 리턴 (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 = 1i <= 9i++) { //숫자 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 = 0i < 9i++) {

       scanf("%s"input);

       for (int j = 0j < 9j++)

          sudoku[i][j] = input[j] - '0';

   }

 

   printf("%s\n"solve() ? "[Solved]" : "[No solution]");  //풀어

 

   //결과 출력

   for (int i = 0i < 9i++) {

       for (int j = 0j < 9j++)

          printf("%d", sudoku[i][j]);

       printf("\n");

   }

}


0은 빈칸으로 간주됩니당.

한줄에 9글자

총 9줄이 입력되면 시작합니다.


결과

표준입력

800000000

003600000

070090200

050007000

000045700

000100030

001000068

008500010

090000400


표준출력

[Solved]

812753649

943682175

675491283

154237896

369845721

287169534

521974368

438526917

796318452



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 함수를 쓰면 됩니다.