fork(2) download
  1. #include <stdio.h>
  2. #define RN 9
  3. #define CN 13
  4. //#include <intrin.h> //Visual C++용 __popcnt()함수 쓰기 위함
  5.  
  6. int sudoku[9][9]; //9x9 스도쿠판
  7. int* r[9][9]; //스도쿠판의 행 우선 참조
  8. int* c[9][9]; //스도쿠판의 열 우선 참조
  9. int* s[9][9]; //스도쿠판의 3x3 섹터 우선 참조
  10. int nums[1+ 9] = { 0, 1, 2, 4, 8, 16, 32, 64, 128, 256 }; //1~9번 숫자를 비트로 표현
  11. typedef int Set; //0~8비트 불리언, 9~12 rn, 13~17 cn
  12.  
  13. void init() { //참조 포인터 초기화
  14. for (int i = 0; i < 9; i++)
  15. for (int j = 0; j < 9; j++)
  16. r[i][j] = c[j][i] = &sudoku[i][j];
  17. for (int rn = 0; rn < 9; rn += 3)
  18. for (int cn = 0; cn < 9; cn += 3)
  19. for (int i = 0; i < 3; i++)
  20. for (int j = 0; j < 3; j++)
  21. s[rn + (cn / 3)][i * 3 + j] = &sudoku[rn + i][cn + j];
  22. }
  23.  
  24. Set findAblNum(int rn, int cn) { //해당 칸의 가능한 숫자 세트 탐색
  25. Set numset = 511; //0~8비트 true로 초기화
  26. numset |= rn << RN;
  27. numset |= cn << CN;
  28. int sn = rn / 3 * 3 + cn / 3; //섹터 번호 구함
  29. for (int i = 0; i < 9; i++) {
  30. //행(*r),열(*c),섹터(*s) 탐색
  31. if (*r[rn][i] > 0) //채워져 있으면
  32. numset &= ~nums[*r[rn][i]]; //false로 마킹
  33. if (*c[cn][i] > 0)
  34. numset &= ~nums[*c[cn][i]];
  35. if (*s[sn][i] > 0)
  36. numset &= ~nums[*s[sn][i]];
  37. }
  38. return numset;
  39. }
  40. Set findMinPossible() { //가장 경우의 수가 적은칸의 세트 리턴
  41. int size = 10;
  42. Set minset = 170 << RN; //{10,10} 초기화
  43. for (int i = 0; i < 9; i++) {
  44. for (int j = 0; j < 9; j++) {
  45. if (sudoku[i][j] > 0) continue; //채워진칸 무시
  46. Set temp = findAblNum(i, j);
  47. int nsize = __builtin_popcount(temp & 511); //__popcnt(temp&511); VC용
  48. if (!nsize) //빈칸인데 가능한 숫자가 없으면
  49. return 255 << RN; //오답 표시 리턴
  50. else if (nsize == 1) //가능한 숫자가 하나일 경우 바로 리턴
  51. return temp;
  52. else if (nsize < size) {
  53. size = nsize;
  54. minset = temp;
  55. }
  56. }
  57. }
  58. return minset;
  59. }
  60.  
  61. bool solve() {
  62. Set set = findMinPossible(); //가장 경우의 수가 적은 칸 탐색
  63. int rn = ((set >> RN) & 15);
  64. int cn = ((set >> CN) & 15);
  65. if (rn > 10)
  66. return false;
  67. if (rn == 10) //더 이상 빈칸이 없음을 뜻함.
  68. return true; //풀린것!
  69. for (int i = 1; i <= 9; i++) { //숫자 1~9를 채우는 부분
  70. if (set & nums[i]) { //채울 수 있는 숫자이면
  71. sudoku[rn][cn] = i; //숫자를 채움
  72. if (solve()) //채운걸 풀어봄
  73. return true; // 그게 풀렸으면 탈출
  74. }
  75. }
  76. // 채울 수 있는 숫자가 없거나 다 채워봤는데 안된거니까
  77. sudoku[rn][cn] = 0; //지우고
  78. return false; //오답 리턴
  79. }
  80.  
  81. int main() {
  82. init(); //참조 포인터 초기화
  83. char input[10]; //입력
  84.  
  85. //문자를 숫자로 변환
  86. for (int i = 0; i < 9; i++) {
  87. scanf("%s", input);
  88. for (int j = 0; j < 9; j++)
  89. sudoku[i][j] = input[j] - '0';
  90. }
  91.  
  92. printf("%s\n", solve() ? "[Solved]" : "[No solution]"); //풀어
  93.  
  94. //결과 출력
  95. for (int i = 0; i < 9; i++) {
  96. for (int j = 0; j < 9; j++)
  97. printf("%d", sudoku[i][j]);
  98. printf("\n");
  99. }
  100. }
  101.  
Success #stdin #stdout 0.02s 3416KB
stdin
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400
stdout
[Solved]
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452