fork download
copy 
  1.  
  2. /**
  3.  * Solve Soduku using backtracking
  4.  * 
  5.  * @author Prateek
  6.  */
  7.  class SolveSoduku {
  8.  
  9. 	private static final int BLANK = 0;
  10.  
  11. 	// Soduku to be solved
  12. 	private static int[][] soduku;
  13.  
  14. 	// Size of Soduku
  15. 	private final int size;
  16. 	// Size of the Block in which checking to be done, it is sqrt of size of
  17. 	// soduku
  18. 	private int boxSize;
  19.  
  20. 	/**
  21. 	 * Constructor
  22. 	 * 
  23. 	 * @param soduku
  24. 	 * @throws Exception
  25. 	 */
  26. 	public SolveSoduku(int[][] soduku) throws Exception {
  27. 		this.soduku = soduku;
  28.  
  29. 		if (soduku.length == soduku[0].length) {// Square marix required
  30. 			this.size = soduku.length;
  31. 			this.boxSize = (int) Math.sqrt(this.size);
  32. 		} else
  33. 			throw new Exception("Invalid Matrix");
  34. 	}
  35.  
  36. 	/**
  37. 	 * Subroutine to solve the Soduku
  38. 	 * @return true if soduku is solvable
  39. 	 */
  40. 	public boolean solve(int row, int col) {
  41.  
  42. 		if (soduku[row][col] != BLANK)
  43. 			nextCell(row, col);
  44.  
  45. 		else {
  46. 			// Try the vacant cell with every Number
  47. 			for (int num = 1; num <= size; num++) {
  48.  
  49. 				// check if current number can fit the cell with the given
  50. 				// constraints
  51. 				if (isValid(row, col, num)) {
  52. 					soduku[row][col] = num; // Assuming to be true
  53.  
  54. 					if (row == size - 1 && col == size - 1) {
  55. 						printSoduku();
  56. 						return true;
  57. 					}
  58.  
  59. 					if (solve(row, col)) // will be called again and other cells
  60. 						return true;				// will be processed
  61.  
  62. 					// printSoduku();
  63. 					soduku[row][col] = BLANK; // Reverting
  64. 				}
  65. 			}
  66. 		}
  67. 		return false; // will be reached if for any cell none of the number(1-9)
  68. 						// fit
  69. 	}
  70.  
  71. 	/**
  72. 	 * Find the next free cell
  73. 	 * @return , true if free cell found and currentRow and currentColumn are set
  74. 	 */
  75. 	private void nextCell(int row, int col) {
  76. 		if (col < size - 1)
  77. 			solve(row, col + 1);
  78. 		else if (row < size - 1)
  79. 			solve(row + 1, 0);
  80. 	}
  81.  
  82. 	/**
  83. 	 * check validity of number at the given position, combining the result of 3
  84. 	 * conditions
  85. 	 * @return true, if the number can fit at the current position
  86. 	 */
  87. 	private boolean isValid(int row, int col, int num) {
  88. 		return checkRow(row, col, num) && checkCol(row, col, num)
  89. 				&& checkBox(row - row % boxSize, col - col % boxSize, num);
  90. 	}
  91.  
  92. 	/**
  93. 	 * Check particular for the existance of given number (in a particular row)
  94. 	 * @return true if the number does not exist
  95. 	 */
  96. 	private boolean checkRow(int row, int col, int num) {
  97. 		for (int c = 0; c < size; c++)
  98. 			if (soduku[row][c] == num)
  99. 				return false;
  100. 		return true;
  101. 	}
  102.  
  103. 	/**
  104. 	 * Check particular for the existance of given number (in a particular col)
  105. 	 * @return true if the number does not exist
  106. 	 */
  107. 	private boolean checkCol(int row, int col, int num) {
  108. 		for (int r = 0; r < size; r++)
  109. 			if (soduku[r][col] == num)
  110. 				return false;
  111. 		return true;
  112. 	}
  113.  
  114. 	/**
  115. 	 * Check particular for the existance of given given BOX
  116. 	 * @return true if the number does not exist
  117. 	 */
  118. 	private boolean checkBox(int row, int col, int num) {
  119. 		for (int r = 0; r < boxSize; r++) {
  120. 			for (int c = 0; c < boxSize; c++) {
  121. 				if (soduku[r + row][c + col] == num)
  122. 					return false;
  123. 			}
  124. 		}
  125. 		return true;
  126. 	}
  127.  
  128. 	public static void main(String[] args) throws Exception {
  129. 		int[][] soduku = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
  130. 				{ 5, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 8, 7, 0, 0, 0, 0, 3, 1 },
  131.  
  132. 				{ 0, 0, 3, 0, 1, 0, 0, 8, 0 }, { 9, 0, 0, 8, 6, 3, 0, 0, 5 },
  133. 				{ 0, 5, 0, 0, 9, 0, 6, 0, 0 },
  134.  
  135. 				{ 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 },
  136. 				{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
  137.  
  138. 		SolveSoduku obj = new SolveSoduku(soduku);
  139. 		obj.solve(0, 0);
  140. 		// obj.printSoduku();
  141. 	}
  142.  
  143. 	private void printSoduku() {
  144. 		for (int row = 0; row < size; ++row) {
  145. 			if (row % boxSize == 0)
  146. 				System.out.println("+-------+-------+-------+");
  147.  
  148. 			for (int col = 0; col < size; col++) {
  149. 				if (col % boxSize == 0)
  150. 					System.out.print("| ");
  151.  
  152. 				System.out.print(soduku[row][col] == 0 ? "  "
  153. 						: soduku[row][col] + " ");
  154. 			}
  155. 			System.out.println("|");
  156. 		}
  157. 		System.out.println("+-------+-------+-------+");
  158. 	}
  159. }
  160.  
Success #stdin #stdout 0.07s 380160KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
+-------+-------+-------+
| 3 1 6 | 5 7 8 | 4 9 2 |
| 5 2 9 | 1 3 4 | 7 6 8 |
| 4 8 7 | 6 2 9 | 5 3 1 |
+-------+-------+-------+
| 2 6 3 | 4 1 5 | 9 8 7 |
| 9 7 4 | 8 6 3 | 1 2 5 |
| 8 5 1 | 7 9 2 | 6 4 3 |
+-------+-------+-------+
| 1 3 8 | 9 4 7 | 2 5 6 |
| 6 9 2 | 3 5 1 | 8 7 4 |
| 7 4 5 | 2 8 6 | 3 1 9 |
+-------+-------+-------+
https://ideone.com/e3so7K
Soduku
language:
Java (12.0.1)
created:
10 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!