# Sudoku Solver questions on style and algorithm

I am working towards a CSC degree right now and wanted to try and practice writing good code that could be easily maintained and read in industry. I wrote the following program in Java that takes a multi-dimensional array representing an Sudoku and uses recursive backtracking to find a solution.

If you were an industry professional looking for applicants to your position and I sent you this as an example of code I had worked on what would you look at? What are things that would be a strike against me and what are things that would would make me look good.

This is kind of a weird scenario but I am just trying to make myself as competitive as possible once I get out of school. Also I have dyslexia, please let me know if you find an misspelled words I really struggle with that.

And here is a link to a repository where I pushed everything.

import java.util.Stack;

/**
* A simple class that solves a Sudoky.
* @author Luke Kelly
* @version 1.0
*/
class SudokuSolver {
/**
* Solves the given Sudoku, preconditions:
* 1. Empty space is reperesnted by 0s.
* 2. The sudoku is not already invalid(No duplicates in a row, colum, or 3x3 box,except zeros).
* 3. The sudoku is a normal 9x9 sudoku.
* @return a solved sudoku is the sudoku is solvable, null if not.
*/
public static  int[][] solveSudoku(int[][] original) {
//Clone the original so I don't change the original array
int[][] workingSudoku = cloneSudoku(original);
//Find all the emtpy indexes in the array, this simplifes the algorithm.
Stack<Integer[]> allEmtpyIndexes = findAllEmptySpaces(workingSudoku);
//Solve it, if they method returns false the sudoku is unsolvable.
if(solveSudoku(workingSudoku, allEmtpyIndexes)){
return workingSudoku;
}else{
return null;
}
}

/**
* Private recursive helper for solveSudoku
* @param workingSudoku the Sudoku we are trying to solve
* @param allEmptyIndexes a Stack holding all the emtpy locations
* @return true if the sudoku is solved, false if not.
*/
private static boolean solveSudoku(int[][] workingSudoku,
Stack<Integer[]> allEmptyIndexes) {
/* Algorithm Explanation:
1. Grab the first index that is empty from the stack,
2. Grab all information from that index.
3. Loop through all the numbers from 1-9 and see if they fit work in the empty space.
i.  If the number is allowed, put it in that index, and restart the loop from the next index.
a. If the recursive call returns true then we know that number works in that location return true;
b. If the recursive call retruns false then we know that number does not work,
place a EMPTY_CELL back in that location and continue back at step 3.
ii. If none of the numbers work, we put this index back in the stack, and return false
4. If at top of stack and return false then we know all possible permutations were tried return false
else we return true because we have a solved puzzle.
*/
int EMPTY_CELL = 0; //Place holder for an Emtpy cell
while (!allEmptyIndexes.isEmpty()) {
//1.
Integer[] workingIndex = allEmptyIndexes.pop();
//2.
int row = workingIndex[0];
int col = workingIndex[1];
//3.
for (int number = 1; number <= 9; number++) {
if (isAllowed(workingSudoku, row, col, number)) {
//3 i.
workingSudoku[row][col] = number;
if (solveSudoku(workingSudoku, allEmptyIndexes)){
//3 i a.
return true;
} else {
//3 i b.
workingSudoku[row][col] = EMPTY_CELL;
}
}

}
//3 ii.
return false;
}
return true;
}

/**
* Checks if that number is already in the row, colum, 3x3 box that our
* index is in.
* @param workingSudoku the Sudoku we are working in
* @param rowIndex the index of the row we are working in
* @param colIndex the index of the colum we are working in
* @param number the number we are trying to place there
* @return true if the number works, false if it doesn't.
*/
private static boolean isAllowed(int[][] workingSudoku, int rowIndex, int colIndex, int number) {
return !(containsInRow(workingSudoku, rowIndex, number) ||
containsInCol(workingSudoku, colIndex, number) ||
containsInBox(workingSudoku, rowIndex, colIndex, number));
}

/**
* Checks if the given number exists in this row.
* @param sudoku the Sudoku we are working in.
* @param rowIndex the index of the row.
* @param number The number we are checking against.
* @return true if the number is in there, false if not.
*/
private static boolean containsInRow(int[][] sudoku, int rowIndex, int number) {
for (int i = 0; i < 9; i++) {
if (sudoku[rowIndex][i] == number) {
return true;
}
}
return false;
}

/**
* Checks if the given number exists in this colum.
* @param sudoku the Sudoku we are working in.
* @param colIndex the index of the colum.
* @param number The number we are checking against.
* @return true if the number is in there, false if not.
*/
private static boolean containsInCol(int[][] sudoku, int colIndex, int number) {
for (int i = 0; i < 9; i++) {
if (sudoku[i][colIndex] == number) {
return true;
}
}
return false;
}

/**
* Checks if the given number exists in the box.
* @param sudoku the Sudoku we are working in.
* @param row the index of the row.
* @param col the index of the colum.
* @param number The number we are checking against.
* @return true if the number is in there, false if not.
*/
private static boolean containsInBox(int[][] sudoku, int row, int col, int number) {
int r = row - row % 3;
int c = col - col % 3;
for (int i = r; i < r + 3; i++) {
for (int j = c; j < c + 3; j++) {
if (sudoku[i][j] == number) {
return true;
}
}
}
return false;
}

/**
* Finds all the emtpy indexes in the Sudoku.
* @param sudoku the sudoku we are searching through.
* @return A stack with all the empty indexes in the Sudoku.
*/
private static Stack<Integer[]> findAllEmptySpaces(int[][] sudoku) {
Stack<Integer[]> allIndexes = new Stack<>();
int size = sudoku.length - 1;
for (int outer = size; outer >= 0; outer--) {
for (int inner = size; inner >= 0; inner--) {
if (sudoku[outer][inner] == 0) {
allIndexes.push(new Integer[] { outer, inner, 1 });
}
}

}
return allIndexes;
}

/**
* Clones the given sudoku, so we can make changes with out affecting the
* original.
* @param original the original Sudoku
* @return a copy of the original.
*/
private static int[][] cloneSudoku(int[][] original) {
int sizeSudoku = original.length;
int[][] newArr = new int[sizeSudoku][sizeSudoku];
for (int i = 0; i < sizeSudoku; i++) {
newArr[i] = original[i].clone();
}
return newArr;
}
}


I also wrote a simple JUnit test file.

import static org.junit.Assert.fail;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

import org.junit.Before;
import org.junit.Test;

/**
* Simple test clas to test my Solve Sudoku.
*
* @author Luke Kelly
* @version 1.0
*/
public class TestSolver {
// The size of a sudoku
private int DIMENSIONS_OF_SUDOKU = 9;
// Interger representation of an emtpy space
private int EMPTY_SPACE = 0;
// The original sudoku generated every time.
int[][] sudoku = new int[DIMENSIONS_OF_SUDOKU][DIMENSIONS_OF_SUDOKU];

/*
* Generates a random sudoku from the python file I found online.
*/
@Before
public void generateRandomSudoku() {
// Python command to tell terminal
String command = "python ";
// Location of the file.
String pathToFile = "Path to Generator";//Change this before you run.

// The process that will run to create the file.
Process generator;
try {
// Run python script to generate a sudoku file.
generator = Runtime.getRuntime().exec(command + pathToFile);
/*
* Wait for file to be created, the python process will close itself
* when it is done.
*/
generator.waitFor();
} catch (IOException e) {
/*
* Used in the testCreateFile test to make sure the generator is
* working properly
*/
fail("Could not run the python script");
} catch (InterruptedException e) {
/*
* Used in the testCreateFile test to make sure the generator is
* working properly
*/
fail("The process was interrupted");
}

// File location of the file
File puzzle = new File("Path to puzzle");//Change this before you run

try {
// Scanner to read through the file.
Scanner inFile = new Scanner(puzzle);
int outer = 0;
while (inFile.hasNextLine()) {
String line = inFile.nextLine();
for (int i = 0; i < DIMENSIONS_OF_SUDOKU; i++) {
// Stores the int value of the char in the array.
sudoku[outer][i] = (line.charAt(i) - '0');
}
outer++;
}
inFile.close();
} catch (FileNotFoundException e) {
/*
* Used in the testCreateFile test to make sure the generator is
* working properly
*/
fail("Puzzle file was not created.");
}
}

@Test
/**
* Test to make sure the file generator is working properly.
*/
public void testCreateFile() {
generateRandomSudoku();
}

@Test
public void testSolver() {
// Check 10 different Sudokus.
int numTests = 10;
for (int testNumber = 0; testNumber < numTests; testNumber++) {
generateRandomSudoku();
int[][] solvedSudoku = SudokuSolver.solveSudoku(this.sudoku);
if (!checkSameSudoku(solvedSudoku))
fail("The sudoku was not the same as the original " + testNumber);
if (!isComplete(solvedSudoku)) {
for (int[] integers : solvedSudoku) {
System.out.println(Arrays.toString(integers));
}
fail("The sudoku was not correct " + testNumber);
}
}
}

/**
* Checks if the given sudoku is complete and that there are no duplicate
* nubmers.
*/
private boolean isComplete(int[][] compSudoku) {
// Check if all rows are correct first.
for (int outer = 0; outer < DIMENSIONS_OF_SUDOKU; outer++) {
// Add one to DIMENSIONS_OF_SUDOKU because the number 9 is allowed.
boolean[] hasBeenUsed = new boolean[DIMENSIONS_OF_SUDOKU + 1];
Arrays.fill(hasBeenUsed, false);
for (int inner = 0; inner < DIMENSIONS_OF_SUDOKU; inner++) {
int value = compSudoku[outer][inner];
boolean check = checkValue(hasBeenUsed, value);
if (!check)
return false;
}
}

// Check if all colums are correct second.
for (int outer = 0; outer < DIMENSIONS_OF_SUDOKU; outer++) {
// Add one to DIMENSIONS_OF_SUDOKU because the number 9 is allowed.
boolean[] hasBeenUsed = new boolean[DIMENSIONS_OF_SUDOKU + 1];
Arrays.fill(hasBeenUsed, false);
for (int inner = 0; inner < DIMENSIONS_OF_SUDOKU; inner++) {
int value = compSudoku[inner][outer];
boolean check = checkValue(hasBeenUsed, value);
if (!check)
return false;
}
}
/* If we get here then we know all colums and rows are correct */
return true;
}

private boolean checkValue(boolean[] hasBeenUsed, int value) {
boolean returnedValue = true;
//If the value has already been used.
if (hasBeenUsed[value] == true) {
returnedValue = false;
/*If the value is less than max number allowed
If the value is less than one
If the value is less is an Emtpy space.
return false.*/

} else if (value > DIMENSIONS_OF_SUDOKU || value < 1 || value == EMPTY_SPACE) {
returnedValue = false;
} else {
//Allowed number store it so it can't be used again.
hasBeenUsed[value] = true;
//ReturnedValue is already set to true so don't change it.
}
return returnedValue;
}

/**
* Checks if the given sudoku is the same as the original.
*/
private boolean checkSameSudoku(int[][] compSudoku) {
//Loop through every index.
for (int outer = 0; outer < DIMENSIONS_OF_SUDOKU; outer++) {
for (int inner = 0; inner < DIMENSIONS_OF_SUDOKU; inner++) {
/*
* If there isn't and empty space in the original at this index
* check this location agains the completed Sudoku.
*/
if (sudoku[outer][inner] != EMPTY_SPACE) {
if (sudoku[outer][inner] != compSudoku[outer][inner])
//If they are not the same return false.
return false;
}
}
}
return true;
}

}


## Minor typos / grammar

Note: most IDEs have a spellchecker and will highlight wrongly spelled words

You have an extra space between static and int on line 16. - Most code bases have checkstyle or similair processes to prevent this sort of error, so I wouldn't worry about these sort of things. I just wanted to include it for completeness.

I suggest changing the class comment to "solves a Sudoku board" instead of "solves a Sudoky". A bit knit picky but same goes for the class comment "solves the given sudoku" vs "solves the given Sudoku board"

"reperesnted" should be "represented"

"colum" should be "column"

"emtpy" should be "empty" ...

You can use formatting in your javadocs. Assuming you are using an IDE such as eclipse you can highlight the method to see what the javadoc looks like:

/**
* Solves the given Sudoku, preconditions:
* <ul>
* <li>Empty space is reperesnted by 0s</li>
* <li>The sudoku is not already invalid (No duplicates in a row, colum, or 3x3 box,except zeros)</li>
* <li>The sudoku is a normal 9x9 sudoku</li>
* </ul>
* @return a solved sudoku if the sudoku is solvable, null if not
*/
public static int[][] solveSudoku(int[][] original) {


Otherwise you can generate Javadoc documentation and see what it looks like.

## Single responsibility principle

Try to think of methods by themselves. For example, the javadoc for 'solvesudoku' mentions it's a helper method for another method. Try to avoid this mindset. Reading the javadoc I'd like to know what the method does, without going through the javadoc for other methods.

## Method / variable naming

"solveSudoku" does not make sense. "isSudokuSolved" or "isSudokuBoardSolved" makes more sense.

## Avoid magic numbers / magic strings

For example numbers "9" and "3" could be declared as static variables at the top. I'd also suggest doing the same for your empty space variable (0) so it's easier to find / change.

## Testing

I was disappointed to see your test references a Python file you found online. Tbh I didn't bother trying to test your code, there's just too much logic in the test classes for me to want to bother with.

As an industry professional, here's what immediately comes to my mind:

• class SudokuSolver: package private class? Why?
• inconsistent spacing (two spaces before the int[][] solveSudoku, sometimes spaces before opening braces, sometimes not, ... - yes, we notice these details!)
• Use of Stack class (see opening comment in API-doc, e.g. https://docs.oracle.com/javase/10/docs/api/java/util/Stack.html)
• Integer[] to represent a set of coordinates. Ususally, if you have a business concept behind a given set of variables, it is worth to create a class which has a correct name for that, so that every reader can immediately grasp the concept. Better: create a Coordinates class (or Point or whatever)
• int EMPTY_CELL = 0 if this is a variable, this should be named emptyCell. As a constant, it should be static final in the class, and probably public as well, so that the user can utilize the constant to create the input.
• I like the explanatory comment for the algorithm combined with the simple commentens // 1, // 2 etc. - makes it very clear to me.
• Use of recursion: even if the problem is small, (i.e. you'll have a maximum recursion depth of 81 - n where n is the number of initially filled fields) the technique of recursion itself is mostly a red light, as it tends to be uncontrollable very fast. So (in my book): either unroll the recursion to replace it with an iterative solution, or at least add a comment that you thought this out and why there is no risk in doing it recursively. (Note that this is not true in pure functional languages ;-))
• Unit test based on random generation: NO. There is no guarantee that after a given software change the random test will actually catch a new bug. (E.g. maybe you "accidentally" generate a sudoku which is solvable by only looking at rows and columns, and never even uses the box-check.)

Hope that helps. (And BTW: with this code, you'd get my consent to start in the company as a junior software engineer :-))

• Thanks for your input! I have a quick question about the use of Stack though. Are you saying I should of used something other than a Stack? I read the opening comments and it says use a Deque, should I have used that? Jan 4 '20 at 7:15
• I just noticed I was using add instead of push, is that what you were talking about? Jan 4 '20 at 7:18
• Yes, use a deque of any kind, e.g. a linked list.
– mtj
Jan 4 '20 at 8:45

I did not bother to read your test code in detail, as that code looks totally unexpected to me.

In the test for a sudoku solver there must be at least one full example sudoku that is solved and validated.

The test must not depend on external files and it must not run external programs since a sudoku solver gets an incomplete sudoku board as input and returns a complete sudoku board as output. That's all.

In a completely unrelated project I have some code that demonstrates how simple a unit test can be, and how the code can almost disappear behind the actually interesting test data.

Regarding your main code: it is bad style to have several static methods that all operate on a two-imensional int array. It's much better to define a data type called Sudoku that encapsulates and hides the array. That way your code can concentrate on solving sudokus instead of dealing with the low-level array terminology.