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