fork(5) download
copy 
  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
comments (?)
stdin
copy 
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400
stdout
copy 
[Solved]
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
https://ideone.com/IeoQa8
Sudoku solver (bitmask)
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!