fork download
copy 
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. class Sudoku {
  5. 	private final int SIZE = 9;
  6. 	private final int[] MASK = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
  7. 	private int[] row, col, group;
  8. 	private int[][] map;
  9. 	private int blank;
  10. 	private boolean solved;
  11. 	private int count;
  12.  
  13. 	private void solve() {
  14. 		Scanner sc = new Scanner(System.in);
  15. 		while(sc.hasNext()) {
  16. 			String[] data = new String[SIZE];
  17. 			for(int i=0;i<SIZE;i++) {
  18. 				data[i] = sc.nextLine();
  19. 			}
  20.  
  21. 			solved = false;
  22. 			blank = 0;
  23. 			count = 0;
  24. 			row = new int[SIZE];
  25. 			col = new int[SIZE];
  26. 			group = new int[SIZE];
  27. 			map = new int[SIZE][SIZE];
  28. 			Arrays.fill(row, 0);
  29. 			Arrays.fill(col, 0);
  30. 			Arrays.fill(group, 0);
  31. 			for(int i=0;i<SIZE;i++) {
  32. 				for(int j=0;j<SIZE;j++) {
  33. 					map[i][j] = data[i].charAt(j)-'0';
  34. 					if(map[i][j]==0) {
  35. 						blank++;
  36. 					} else {
  37. 						setBit(j, i, map[i][j]);
  38. 					}
  39. 				}
  40. 			}
  41. 			find(0, 0);
  42. 			if(!solved) {
  43. 				System.out.println("先生…解けません…！");
  44. 			}
  45. 		}
  46. 	}
  47.  
  48. 	private void find(int x, int y) {
  49. 		if(count==blank) {
  50. 			put(map);
  51. 			solved = true;
  52. 		} else {
  53. 			while(map[y][x]!=0) {
  54. 				if(x+1==SIZE) y = (y + 1) % SIZE;
  55. 				x = (x + 1) % SIZE;
  56. 			}
  57. 			for(int i=1;i<=9;i++) {
  58. 				if(!testBit(x, y, i)) {
  59. 					setBit(x, y, i);
  60. 					map[y][x] = i;
  61. 					count++;
  62. 					find(x, y);
  63. 					if(solved) return;
  64. 					count--;
  65. 					map[y][x] = 0;
  66. 					clearBit(x, y, i);
  67. 				}
  68. 			}
  69. 		}
  70. 	}
  71.  
  72. 	private void setBit(int x, int y, int n) {
  73. 		row[y] |= MASK[n];
  74. 		col[x] |= MASK[n];
  75. 		group[getGroup(x, y)] |= MASK[n];
  76. 	}
  77.  
  78. 	private void clearBit(int x, int y, int n) {
  79. 		row[y] &= ~MASK[n];
  80. 		col[x] &= ~MASK[n];
  81. 		group[getGroup(x, y)] &= ~MASK[n];
  82. 	}
  83.  
  84. 	private boolean testBit(int x, int y, int n) {
  85. 		return ((row[y] & MASK[n]) > 0) || ((col[x] & MASK[n]) > 0) || ((group[getGroup(x, y)] & MASK[n]) > 0);
  86. 	}
  87.  
  88. 	private int getGroup(int x, int y) {
  89. 		return (y / 3) * 3 + (x / 3);
  90. 	}
  91.  
  92. 	private void put(int[][] map) {
  93. 		for(int i=0;i<SIZE;i++) {
  94. 			for(int j=0;j<SIZE;j++) {
  95. 				System.out.printf("%d", map[i][j]);
  96. 			}
  97. 			System.out.println();
  98. 		}
  99. 		System.out.println();
  100. 	}
  101.  
  102. 	public static void main(String[] args) { 
  103. 		new Sudoku().solve();
  104. 	}
  105. }
Success #stdin #stdout 0.12s 213888KB
comments (?)
stdin
copy 
200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003
stdout
copy 
245981376
169273584
837564219
976125438
513498627
482736951
391657842
728349165
654812793
https://ideone.com/4SEeK
language:
Java (HotSpot 12)
created:
12 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!