# Alternative methods of solving Sudoku

I am learning Java as my first programming language and have written a bit of code. I would love to read expert reviews on this code and suggestions to improve right from naming conventions to logic. Please let me know if there is any kind of mistake.

public class Sudoku {

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
int[][] array = { { 0, 2, 0, 5, 0, 0, 0, 9, 0 },
{ 5, 0, 0, 0, 7, 9, 0, 0, 4 },
{ 3, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 6, 0, 0, 0, 0, 0, 8, 0, 7 },
{ 0, 7, 5, 0, 2, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 0, 0, 4, 0, 0 },
{ 0, 0, 0, 3, 0, 8, 9, 0, 2 },
{ 7, 0, 0, 0, 6, 0, 0, 4, 0 },
{ 0, 3, 0, 2, 0, 0, 1, 0, 0 } };
solve(array);
System.out.println("Solution is ");
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
System.out.print(" " + array[row][col] + " ");
}
System.out.println();
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Time taken (in MilliSeconds)= " + totalTime);
}

public static boolean solve(int[][] array) {
if (isSum45(array)) {
return true;
}
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (array[row][col] == 0) {
for (int num = 1; num <= 9; num++) {
if (noConflict(array, row, col, num)) {
array[row][col] = num;
if (solve(array)) {
return true;
}
}
array[row][col] = 0;
}
return false;
}
}
}
return false;
}

// This method edited is after taking suggestions from this forum
public static boolean noConflict(int[][] array, int row, int col, int num) {
for (int k = 0; k < 9; k++) {
if (array[row][k] == num) {
return false;
}
if (array[k][col] == num) {
return false;
}
}
int m = row - (row % 3);
int n = col - (col % 3);
for (int p = m; p < m + 3; p++) {
for (int q = n; q < n + 3; q++) {
if (array[p][q] == num) {
return false;
}
}
}
return true;
}

public static boolean isSum45(int[][] array) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
int sum = 0;
int m = row - (row % 3);
int n = col - (col % 3);
for (int p = m; p < m + 3; p++) {
for (int q = n; q < n + 3; q++) {
sum = sum + array[p][q];
}
}
if (sum != 45) {
return false;
}
}
}
return true;
}
}

• Your noConflict is a waste of processor. You should be looking only for the number you try to set, so instead of: add to list every number in row and column, check if num is in the list, return; you can only do: check if number is in row or column, return when found. It will be much faster. – fernando.reyes Jan 15 '14 at 22:26
• @fernando.reyes I couldn't get your point correctly. What if the number is in the current grid? With that in mind I wrote like that. – user35013 Jan 15 '14 at 22:31
• I miss that part, let's rephrase it. The first for with two ifs, instead of adding everything to the list, if (array[row][k] == num ) return false; and that saves some loop cycles – fernando.reyes Jan 15 '14 at 22:55
• @fernando.reyes I changed the code as suggested by you. Thanks once again. – user35013 Jan 16 '14 at 12:21
• Sudoku was the topic of a recent WeekEnd Challenge here on CodeReview. you should consider scanning those answers for ideas. Additionally, there is a relatively comprehensive Java solution on the CodeReview GitHub which may provide some inspiration. – rolfl Jan 16 '14 at 16:20

Overall, this is pretty good code for a beginner's solution to a relatively complex problem.

But your code does have me a little lost. For one, I'm not quite sure why you're using recursion here. It seems like that will be a lot more memory intensive than it needs to be for a straightforward problem. It also confused me for a good ten minutes why you were checking for isSum45 to return that the problem is solved, when the sum for the entire board is actually 405.

I would rewrite this as an iterative solution rather than a recursive solution. I think the recursion adds a lot of unnecessary complexity to the code and flow. I don't have the time at the moment to rewrite it as such, so I'll just give some other general comments on your code.

solve(array);
System.out.println("Solution is ");
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
System.out.print(" " + array[row][col] + " ");
}
System.out.println();
}


I'm not a big fan of the above implementation because it relies on the solve() method modifying the original array in place. It also makes your paradigm of returning a boolean from the solve() method irrelevant; you never compare or check for it. I think it would be a better design if you preserve the original board and create a new int[][] solved variable which you return from the method.

for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (array[row][col] == 0) {
for (int num = 1; num <= 9; num++) {
if (noConflict(array, row, col, num)) {
array[row][col] = num;
if (solve(array)) {
return true;
}
}
array[row][col] = 0;
}
return false;
}
}
}


On a positive note, I really like that you named your loop variables row and col versus i and j as so many people do. It makes your code much more readable. But one of the principles of good code design is to avoid this kind of intense nesting as much as possible. You can do this like the following:

for(int row = 0; row < array.length; row++) {
for(int column = 0; column < array[row].length; column++) {
if(array[row][column] != 0) continue;
for(int num = 1; num <= 9; num++) {
if(!noConflict(array, row, column, num)) continue;
array[row][column] = num;
if(solve(array)) return true;
array[row][column] = 0
}
return false;
}
}


This makes your code a bit less complex and a bit more readable. I completely avoid your if(solve(array)) block by simply returning the boolean directly from the recursive method call (EDITED: As David Harkness says in the comments below, this actually changes how the method functions, so I've removed that bit.). Also note that it my loops I compare row and column to array.length and array[row].length, respectively. This isn't a huge deal if you always know you're going to be handling boards which are 9x9, however when you're designing code you should always try to make your code as flexible as possible. The more flexible it is and the more scenarios it can handle, the more powerful it is.

public static boolean noConflict(int[][] array, int row, int col, int num) {


This is just general nitpicking, but you should only expose methods as public which actually need to be public. The solve method makes sense as a public method because it's the part of the API that you will want to use in other parts of the application. This method, however, is purely internal and thus should be private. Also, method names should pretty much always be verbs or verb phrases. I might rename this method to something like noConflictExists or isNoConflict. Actually, because of the nature of how I rewrote your loops above, I would change it to conflictExists or isConflict that way my usage of it is more intuitive. These notes also apply to your isSum45 method, which is public and might use a more intuitive name for code readability.

Also, in those two methods, what happened to your beautiful variable names?!? Why did you suddenly move to using single letters instead of something more descriptive?

• Thanks for your appreciation and review. Do you really think that the sudoku can be solved based on your rewrite of solve()? Please check once and let me know if I am wrong. – user35013 Jan 16 '14 at 15:40
• The isSum45() is actually the base case for the recursive backtracking algorithm. This condition will be met only when the entire board is filled with the correct numbers i.e. 1 to 9 whose sum is actually 45. The method checks whether the sub grids follow the rule of the game or not. Hope you got my point. – user35013 Jan 16 '14 at 15:51
• @Phoenix Sure. My rewrite doesn't actually change any of the functionality of your code, just the readability by reducing the number of nestings. I'm sure your method does work great for the recursion. :) – asteri Jan 16 '14 at 15:56
• You can't simply return the result of the recursive call to solve. If the result is false you must try the next number, or it will give up on the first incorrect guess. While I've found the recursive brute-force approach to be the simplest to implement and understand, you do make other good points so +1. – David Harkness Jan 16 '14 at 19:45
• @DavidHarkness Ah, good point. When skimming it, my brain only processed the if(true) return true style. Will fix. :) – asteri Jan 16 '14 at 19:47