fork(7) download
copy 
  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
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/YCWGxZ
Sudoku solver
language:
C++14 (gcc 8.3)
created:
8 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!