fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class Sudoku_rec {
  4. 	class Grid {	//포인터like 사용을 위한 클래스
  5. 		public int v;
  6. 		Grid(int n) {v = n;}
  7. 	}
  8. 	class Set {
  9. 		int rn, cn;
  10. 		boolean[] num;
  11. 		Set(int rn, int cn) {
  12. 			this.rn = rn;
  13. 			this.cn = cn;
  14. 			num = new boolean[] { true, true, true, true, true, true, true,
  15. 					true, true };
  16. 		}
  17. 	};
  18.  
  19. 	Grid r[][] = new Grid[9][9]; // 행
  20. 	Grid c[][] = new Grid[9][9]; // 열
  21. 	Grid s[][] = new Grid[9][9]; // 구역
  22.  
  23. 	/* 본격 스도쿠 풀이 함수 */
  24. 	Sudoku_rec() {	//열,행,섹터 포인터
  25. 		for (int i = 0; i < 9; i++)
  26. 			for (int j = 0; j < 9; j++)
  27. 				c[j][i] = r[i][j] = new Grid(0);
  28. 		for (int rn = 0; rn < 9; rn += 3)
  29. 			for (int cn = 0; cn < 9; cn += 3)
  30. 				for (int i = 0; i < 3; i++)
  31. 					for (int j = 0; j < 3; j++)
  32. 						s[rn + (cn / 3)][i * 3 + j] = r[rn + i][cn + j];
  33. 	}
  34.  
  35. 	int sizeofNumset(Set set) { // 가능한 숫자 개수 카운터
  36. 		int cnt = 0;
  37. 		for (boolean b : set.num)
  38. 			if (b) cnt++;
  39. 		return cnt;
  40. 	}
  41.  
  42. 	Set findAblNum(int rn, int cn) { // 해당 칸의 가능한 숫자 세트 탐색
  43. 		Set nums = new Set(rn, cn); // true로 초기화
  44. 		int sn = rn / 3 * 3 + cn / 3; // 섹터 번호 구함
  45. 		for (int i = 0; i < 9; i++) {
  46. 			// 행(*r),열(*c),섹터(*s) 탐색
  47. 			if (r[rn][i].v > 0) // 채워져 있으면
  48. 				nums.num[r[rn][i].v - 1] = false; // 마킹
  49. 			if (c[cn][i].v > 0)
  50. 				nums.num[c[cn][i].v - 1] = false;
  51. 			if (s[sn][i].v > 0)
  52. 				nums.num[s[sn][i].v - 1] = false;
  53. 		}
  54. 		return nums;
  55. 	}
  56.  
  57. 	Set findMinPossible() { // 가장 경우의 수가 적은칸의 세트 리턴
  58. 		int size = 10;
  59. 		Set minset = null;
  60. 		for (int i = 0; i < 9; i++) {
  61. 			for (int j = 0; j < 9; j++) {
  62. 				if (r[i][j].v > 0)
  63. 					continue; // 채워진칸 무시
  64. 				Set temp = findAblNum(i, j);
  65. 				int nsize = sizeofNumset(temp);
  66. 				if (nsize == 0) // 빈칸인데 가능한 숫자가 없으면
  67. 					return new Set(10, 10); // 오답 표시 리턴
  68. 				else if (nsize == 1) // 가능한 숫자가 하나일 경우 바로 리턴
  69. 					return temp;
  70. 				else if (nsize < size) {
  71. 					size = nsize;
  72. 					minset = temp;
  73. 				}
  74. 			}
  75. 		}
  76. 		return minset;
  77. 	}
  78.  
  79. 	boolean solve() {
  80. 		Set set = findMinPossible(); // 가장 경우의 수가 적은 칸 탐색
  81. 		if (set == null) // 더 이상 빈칸이 없음을 뜻함.
  82. 			return true; // 풀린것!
  83. 		if (set.rn > 9) // 불가능한 칸이 있음을 뜻함
  84. 			return false;
  85. 		for (int i = 1; i <= 9; i++) { // 숫자 1~9를 채우는 부분
  86. 			if (!set.num[i - 1])
  87. 				continue; // 불가능한 숫자는 스킵
  88. 			r[set.rn][set.cn].v = i; // 가능한 숫자를 채움
  89. 			if (solve()) // 채운걸 풀어봄
  90. 				return true; // 그게 풀렸으면 탈출
  91. 		}
  92. 		// 채울 수 있는 숫자가 없거나 다 채워봤는데 안된거니까
  93. 		r[set.rn][set.cn].v = 0; // 지우고
  94. 		return false; // 오답 리턴
  95. 	}
  96.  
  97. 	void run() {
  98. 		Scanner sc = new Scanner(System.in);
  99. 		for (int i = 0; i < 9; i++) {
  100. 			char input[] = sc.nextLine().toCharArray();
  101. 			for (int j = 0; j < 9; j++)
  102. 				r[i][j].v = input[j] - '0';
  103. 		}
  104. 		sc.close();
  105.  
  106. 		System.out.println(solve() ? "[Solved]" : "[No solution]");
  107.  
  108. 		//결과 출력
  109. 		for (int i = 0; i < 9; i++) {
  110. 			for (int j = 0; j < 9; j++)
  111. 				System.out.print(r[i][j].v);
  112. 			System.out.println();
  113. 		}
  114. 	}
  115.  
  116. 	public static void main(String[] args) {
  117. 		new Sudoku_rec().run();
  118. 	}
  119. }
Success #stdin #stdout 0.2s 321344KB
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/ab4xF8
Sudoku solver
language:
Java (HotSpot 12)
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!