# Sudoku Solver in Java

This is an assignment posted here.

This is my first foray into OO for me. Is this design OK? Or is there something very wrong that I'm not seeing at all. Any suggestions are most welcome and needed.

import java.util.*;

/*
* Encapsulates a Sudoku grid to be solved.
* This project is based on the assignment given in CS108 Stanford.
*/
public class Sudoku {

/* "Spot" inner class that represents a single spot
* on the grid of the Sudoku game.
* Each Spot object knows its place on the Sudoku grid as
* it stores the row and column number as fields.
*/
private class Spot implements Comparable<Spot> {

/* Properties/fields of each individual Spot */
private int row, col;
private int value;
private int part;

/* Stores all possible values for a Spot that is empty
* according to the rules of the game */
private HashSet<Integer> possibleValues;

Spot(int x, int y, int val) {
row = x;
col = y;
value = val;
part = getPart(x, y);

possibleValues = new HashSet<>();
}

Spot(Spot s) {
this(s.row, s.col, s.value);
part = s.part;
possibleValues = new HashSet<>(s.possibleValues);
}

/* Sets the value for this Spot on the Solution Grid (solutionGrid) */
void setValue(int val) {
value = val;
}

/* Returns the value of this Spot */
int getValue() {
return value;
}

/* Returns the part of the grid where this Spot belongs */
int getPartForSpot() {
return part;
}

/* Returns true iff this Spot is not filled */
boolean isEmpty() {
return value == 0;
}

/* Returns a HashSet of all legal values that can be
* filled in this Spot.
*/
HashSet<Integer> getPossibleValues() {
if (value != 0) return null;

/* temporarily assign all 9 numbers */
for (int i = 1; i <= Sudoku.SIZE; i++)

/* Remove all the values that cannot be placed at this Spot */
possibleValues.removeAll(valInRows.get(row));
possibleValues.removeAll(valInCols.get(col));
possibleValues.removeAll(valInParts.get(part));
return possibleValues;
}

/* Updates the Spot on the solution grid with the row and col of
* this Spot with the current value that this spot holds.
*/
public void updateValueInGrid() {
solutionGrid[row][col].value = value;
}

public int getRow() {
return row;
}

public int getCol() {
return col;
}

@Override
public int compareTo(Spot that) {
return this.possibleValues.size() - that.possibleValues.size();
}

@Override
public boolean equals(Object o) {
if (o == null) return false;
if (!(o instanceof Spot)) return false;

Spot that = (Spot) o;
return this.row == that.row && this.col == that.col;
}

@Override
public int hashCode() {
return possibleValues.size() * 25;
}

@Override
public String toString() {
return value + "";
}

/* Helper method that returns the Part in which the
* coordinates x and y belong on the grid.
*/
private int getPart(int x, int y) {
if (x < 3) {
if (y < 3) return PART1;
else if (y < 6) return PART4;
else return PART7;
}
if (x < 6) {
if (y < 3) return PART2;
else if (y < 6) return PART5;
else return PART8;
}
else {
if (y < 3) return PART3;
else if (y < 6) return PART6;
else return PART9;
}
}
} // End of Spot class

/* Member variables for the puzzle and solution grids */
private Spot[][] puzzleGrid;
private Spot[][] solutionGrid;

/* List of all the possible solutions for the puzzle represented as
* an ArrayList of only the Spots that needed to be filled with a
* solution */
private List<ArrayList<Spot>> solutions;

/* The ivars to store the current State of the Grid.
* valInRows:- has a HashSet at each index that stores all the filled
* in values for that particular row
* valInCols:- Same as valInRows but for the columns
* valInParts:- For the 3x3 parts of the grid */
private ArrayList<HashSet<Integer>> valInRows, valInCols, valInParts;

private long timeTakenForSolution;

/* Parts of the grid each of size 3x3. Counting from the
* top left to top right then the next row below.
* 0 1 2
* 3 4 5
* 6 7 8
*/
private static final int PART1 = 0;
private static final int PART2 = 1;
private static final int PART3 = 2;
private static final int PART4 = 3;
private static final int PART5 = 4;
private static final int PART6 = 5;
private static final int PART7 = 6;
private static final int PART8 = 7;
private static final int PART9 = 8;

// Provided easy 1 6 grid
public static final int[][] easyGrid = Sudoku.stringsToGrid(
"1 6 4 0 0 0 0 0 2",
"2 0 0 4 0 3 9 1 0",
"0 0 5 0 8 0 4 0 7",
"0 9 0 0 0 6 5 0 0",
"5 0 0 1 0 2 0 0 8",
"0 0 8 9 0 0 0 3 0",
"8 0 9 0 4 0 2 0 0",
"0 7 3 5 0 9 0 0 1",
"4 0 0 0 0 0 6 7 9");

// Provided medium 5 3 grid
public static final int[][] mediumGrid = Sudoku.stringsToGrid(
"530070000",
"600195000",
"098000060",
"800060003",
"400803001",
"700020006",
"060000280",
"000419005",
"000080079");

// Provided hard 3 7 grid
// 1 solution this way, 6 solutions if the 7 is changed to 0
public static final int[][] hardGrid = Sudoku.stringsToGrid(
"3 7 0 0 0 0 0 8 0",
"0 0 1 0 9 3 0 0 0",
"0 4 0 7 8 0 0 0 3",
"0 9 3 8 0 0 0 1 2",
"0 0 0 0 4 0 0 0 0",
"5 2 0 0 0 6 7 9 0",
"6 0 0 0 2 1 0 4 0",
"0 0 0 5 3 0 9 0 0",
"0 3 0 0 0 0 0 5 1");

public static final int SIZE = 9;  // size of the whole 9x9 puzzle
public static final int PART = 3;  // size of each 3x3 part
public static final int MAX_SOLUTIONS = 100;

// Provided various static utility methods to
// convert data formats to int[][] grid.

/**
* Returns a 2-d grid parsed from strings, one string per row.
* The "..." is a Java 5 feature that essentially
* makes "rows" a String[] array.
* (provided utility)
* @param rows array of row strings
* @return grid
*/
public static int[][] stringsToGrid(String... rows) {
int[][] result = new int[rows.length][];
for (int row = 0; row<rows.length; row++) {
result[row] = stringToInts(rows[row]);
}
return result;
}

/**
* Given a single string containing 81 numbers, returns a 9x9 grid.
* Skips all the non-numbers in the text.
* (provided utility)
* @param text string of 81 numbers
* @return grid
*/
public static int[][] textToGrid(String text) {
int[] nums = stringToInts(text);
if (nums.length != SIZE*SIZE) {
throw new RuntimeException("Needed 81 numbers, but got:" + nums.length);
}

int[][] result = new int[SIZE][SIZE];
int count = 0;
for (int row = 0; row<SIZE; row++) {
for (int col=0; col<SIZE; col++) {
result[row][col] = nums[count];
count++;
}
}
return result;
}

/**
* Given a string containing digits, like "1 23 4",
* returns an int[] of those digits {1 2 3 4}.
* (provided utility)
* @param string string containing ints
* @return array of ints
*/
public static int[] stringToInts(String string) {
int[] a = new int[string.length()];
int found = 0;
for (int i=0; i<string.length(); i++) {
if (Character.isDigit(string.charAt(i))) {
a[found] = Integer.parseInt(string.substring(i, i+1));
found++;
}
}
int[] result = new int[found];
System.arraycopy(a, 0, result, 0, found);
return result;
}

/**
* Sets up the Sudoku puzzle grid based on the integers given
* as a 2D array or matrix.
*/
public Sudoku(int[][] ints) {
puzzleGrid = new Spot[SIZE][SIZE];
solutionGrid = new Spot[SIZE][SIZE];

solutions = new ArrayList<>();

valInRows = new ArrayList<HashSet<Integer>>(SIZE);
valInCols = new ArrayList<HashSet<Integer>>(SIZE);
valInParts = new ArrayList<HashSet<Integer>>(SIZE);

/* Initializing all the HashSets */
for (int i = 0; i < SIZE; i++) {
}

/* Setting up the Sudoku puzzle grid with the appropriate Spots.
* And adding all the values in the relevant Rows, Cols and Parts
* to set up the initial state of the grid. */
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
int val = ints[i][j];
Spot newSpot = new Spot(i, j, val);
puzzleGrid[i][j] = newSpot;

if (!newSpot.isEmpty()) {
}
}
}
}

/**
* Sets up the Sudoku puzzle grid based on the given text. The
* text must contain 81 numbers. Whitespaces are ignored.
* If the text is invalid, an exception is thrown.
* @param text string of 81 numbers
*/
public Sudoku(String text) {
this(Sudoku.textToGrid(text));
}

/**
* Solves the puzzle and returns the number of solutions.
* @return number of solutions
*/
public int solve() {
/* List of all the empty spots in the puzzleGrid */
ArrayList<Spot> emptySpots = getEmptySpotsList();

/* List of Spots that will hold the solution values for the puzzleGrid */
ArrayList<Spot> solvedSpots = new ArrayList<>();

long startTime = System.currentTimeMillis();

solveSudoku(emptySpots, solvedSpots, 0);

long endTime = System.currentTimeMillis();
timeTakenForSolution = endTime - startTime;

if (solutions.size() == 0) /* If no solution found */
return 0;

/* Update the solutionGrid field */
fillSolutionGrid();

return solutions.size();
}

/* Recursive method solves the puzzleGrid
* Strategy:
* =========
* 1. The emptySpots are sorted by the number of possibleValues
*    as solutions. So start with the one that has the least possible
*    values to check.
* 2. Fill each emptySpot recursively but backtrack immediately when
*    a Spot is reached which cannot be filled by any of its possibleValues.
* 3. Keep adding the filled(solved) spots to the List "solvedSpots"
* 4. When a complete solution is reached add the current solvedSpots
*    list to the list of solutions.
* 5. Return only when all possible solutions have been exhausted.
*
* Note: index holds the current index of the emptySpots ArrayList.
*/
private void solveSudoku(ArrayList<Spot> emptySpots,
ArrayList<Spot> solvedSpots, int index) {

/* Only allow MAX_SOLUTIONS */
if (solutions.size() >= Sudoku.MAX_SOLUTIONS)
return;

/* Base Case: When the current chain of values has arrived at a solution */
if (index >= emptySpots.size()) {
return;
}

/* Current emptySpot that is being considered to be filled */
Spot currentSpot = new Spot(emptySpots.get(index));

/* Try all the possible values for this empty Spot */
for (int value : currentSpot.possibleValues) {

/* Check if the value is valid according to the current
* state of the grid */
if (valueIsValid(value, currentSpot)) {
currentSpot.setValue(value);
updateGridStateWithValue(value, currentSpot);

int newIndex = index + 1;
solveSudoku(emptySpots, solvedSpots, newIndex);

/* Backtrack when the method above returns */
emptySpots.get(index).setValue(0);
solvedSpots.remove(currentSpot);
updateGridStateWithValue(value, currentSpot);
}
}
}

/* Fills the solutionGrid field with the first solution that was
* found while solving the puzzle.
*/
private void fillSolutionGrid() {
ArrayList<Spot> solvedSpots = solutions.get(0);

for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
solutionGrid[i][j] = new Spot(puzzleGrid[i][j]);
}
}

for (Spot spot : solvedSpots)
spot.updateValueInGrid();
}

/* Checks if the given value is valid for the given currentSpot by
* checking it against all values in this Spot's row, column and Part
*/
private boolean valueIsValid(int value, Spot currentSpot) {
int row = currentSpot.getRow();
int col = currentSpot.getCol();
int part = currentSpot.getPartForSpot();

return (!valInRows.get(row).contains(value)) &&
(!valInCols.get(col).contains(value)) &&
(!valInParts.get(part).contains(value));
}

/* Updates the state of the grid. If the given value already exists
* as a part of the grid state, then it is removed otherwise it is
* added to the current state.
*/
private void updateGridStateWithValue(int value, Spot currentSpot) {
HashSet<Integer> valsInCurrentRow = valInRows.get(currentSpot.getRow());
HashSet<Integer> valsInCurrentCol = valInCols.get(currentSpot.getCol());
HashSet<Integer> valsInCurrentPart = valInParts.get(currentSpot.getPartForSpot());

if (valsInCurrentRow.contains(value))
valsInCurrentRow.remove(value);
else

if (valsInCurrentCol.contains(value))
valsInCurrentCol.remove(value);
else

if (valsInCurrentPart.contains(value))
valsInCurrentPart.remove(value);
else

}

/* Helper method to compute the possible values for each empty spot and
* return the spots as an ArrayList sorted by the number of possible values
* from low to high.
*/
private ArrayList<Spot> getEmptySpotsList() {
ArrayList<Spot> result = new ArrayList<>();
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
Spot thisSpot = puzzleGrid[i][j];
if (thisSpot.isEmpty()) {
thisSpot.getPossibleValues();
}
}
}
Collections.sort(result);
return result;
}

/**
* Returns the Solution to the Sudoku puzzle as a String.
* @return solution to the puzzle
*/
public String getSolutionText() {
if (solutions.size() == 0) return "No Solutions";
String result = "";
for (Spot[] sArr : solutionGrid) {
result += "[";
for (Spot s : sArr)
result += s.toString() + ", ";
result += "] \n";
}
return result;
}

/**
* Returns the elapsed time spent find the solutions for
* the puzzle
* @return time taken to solve the puzzle
*/
public long getElapsed() {
return timeTakenForSolution;
}

@Override
public String toString() {
String result = "";
for (Spot[] sArr : puzzleGrid) {
result += "[";
for (Spot s : sArr)
result += s.toString() + ", ";
result += "] \n";
}
return result;
}

/* Just for simple testing */
public static void main(String[] args) {
Sudoku sudoku;
sudoku = new Sudoku(easyGrid);

System.out.println(sudoku); // print the raw problem
int count = sudoku.solve();
System.out.println("solutions:" + count);
System.out.println("elapsed:" + sudoku.getElapsed() + "ms");
System.out.println(sudoku.getSolutionText());
}

}


the code is good in general, but there are some comments:

1. Always try to expose abstract type rather than concrete implementations, so use List instead ArrayList, and Set instead of HashSet for fields types and return types, and this gives you more flexibility if you want to migrate to a different concrete type, OOP is about hiding implementation more than hiding data.
2. Use the this so you don't use horrible names for parameters, for example

Spot(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}

3. getPart is private, which is good, so it can't be overridden by subclasses because its being called in the constructor, but I would say declare it as final, so it stays safe even if you change its accessibility later
4. You can use String.valueOf instead of

@Override
public String toString() {
return value + "";
}

• Thank you.. I learned a lot more about interfaces by searching about the things you suggested. And also String.valueOf was new to me :) – rdsarna Oct 15 '14 at 18:33
• Brilliant, we are here to help :) – Sleiman Jneidi Oct 15 '14 at 21:55

Immutable fields are good. It's a lot easier to work with things that are guaranteed to never change. So whenever it's possible to make something final, do it. For example, all these lines:

private int row, col;
private Spot[][] puzzleGrid;
private Spot[][] solutionGrid;
private List<ArrayList<Spot>> solutions;


... and many others, could have been final (your code still compiles), so make them final.

Use interface types in variable declarations, method parameters and method return types, whenever possible. For example instead of HashSet in these examples:

private HashSet<Integer> possibleValues;

HashSet<Integer> getPossibleValues() {
// ...
}


Use a Set instead:

private Set<Integer> possibleValues;

Set<Integer> getPossibleValues() {
// ...
}


The only time you should use implementation types like HashSet instead of Set in declarations is if you need a specific feature of the implementation. If interface methods are all you need, then you should use the interface type always.

Sometimes you use the <> (diamond operator), sometimes not:

solutions = new ArrayList<>();

valInRows = new ArrayList<HashSet<Integer>>(SIZE);
valInCols = new ArrayList<HashSet<Integer>>(SIZE);
valInParts = new ArrayList<HashSet<Integer>>(SIZE);


Just use it always:

solutions = new ArrayList<>();

valInRows = new ArrayList<>(SIZE);
valInCols = new ArrayList<>(SIZE);
valInParts = new ArrayList<>(SIZE);


In this if-else:

if (x < 6) {
if (y < 3) return PART2;
else if (y < 6) return PART5;
else return PART8;
}
else {
if (y < 3) return PART3;
else if (y < 6) return PART6;
else return PART9;
}


Notice that all execution branches of the x < 6 part will return. So you don't actually need the else, you could write simpler like this:

if (x < 6) {
if (y < 3) return PART2;
else if (y < 6) return PART5;
else return PART8;
}
if (y < 3) return PART3;
else if (y < 6) return PART6;
else return PART9;


Instead of printing text in a main method, use proper unit tests to verify the correctness of the implementation, for example:

@Test
public void testEasyGrid() {
Sudoku sudoku = new Sudoku(Sudoku.easyGrid);
int count = sudoku.solve();
assertEquals(1, count);
assertEquals(
"[1, 6, 4, 7, 9, 5, 3, 8, 2, ] \n" +
"[2, 8, 7, 4, 6, 3, 9, 1, 5, ] \n" +
"[9, 3, 5, 2, 8, 1, 4, 6, 7, ] \n" +
"[7, 9, 1, 8, 7, 6, 5, 2, 4, ] \n" +
"[5, 4, 6, 1, 3, 2, 7, 9, 8, ] \n" +
"[7, 2, 8, 9, 5, 4, 1, 3, 6, ] \n" +
"[8, 1, 9, 6, 4, 7, 2, 5, 3, ] \n" +
"[6, 7, 3, 5, 2, 9, 8, 4, 1, ] \n" +
"[4, 5, 2, 3, 1, 8, 6, 7, 9, ] \n", sudoku.getSolutionText());
}

• Thank you for the suggestion about making vars final. I read up on it and it is considered a good practice. – rdsarna Oct 15 '14 at 18:34
/* Helper method that returns the Part in which the
* coordinates x and y belong on the grid.
*/
private int getPart(int x, int y) {
if (x < 3) {
if (y < 3) return PART1;
else if (y < 6) return PART4;
else return PART7;
}
if (x < 6) {
if (y < 3) return PART2;
else if (y < 6) return PART5;
else return PART8;
}
else {
if (y < 3) return PART3;
else if (y < 6) return PART6;
else return PART9;
}
}


Ugh... This is actually entirely based on two mathematical operations: Division and Modulo.

Also, your PART1, PART2, etc. variables... what is the real usage of those? PARTx = x - 1. This "off by one" thing is very common in programming, and does not deserve 9 named variables to be solved.

So let's take a look here:

• If x is less than 3, then either PART 1, 4 or 7 is returned.
• If x is between 3 and 5 (inclusive), then either PART 2, 5, 8 is returned. So one more than the above.
• If x is 6 or more, then PART 3, 6, 9 is returned. Again, one more than the above.

And for y:

• If y is less than 3, then PART 1, 2, or 3 is returned.
• If y is between 3 and 5, then PART 4, 5, or 6 is returned. (I didn't even double-check with your code this time, I just know).
• If y is 6 or more, then PART 7, 8, or 9 is returned.

As your PARTs are essentially the int value x - 1, it's better to return those values directly.

The calculation for this is simply:

private int getPart(int x, int y) {
int xGroup = x / 3;
int yGroup = y / 3;
return yGroup * 3 + xGroup;
}


Look at how clean that got!

### Extensibility

Right now you only support a classic 9x9 Sudoku. If you change the way you treat rows, columns and 'boxes' though, and consider all of those as just a SudokuRule, then your code suddenly becomes much more flexible and can solve many more kinds of Sudokus.

Really, when you think about it, what is the difference between a row and a column? What is the difference between a box and a row? It is only the fields that belong to that 'rule'. A row is a restriction of what numbers can be placed there. The simple rule is that all numbers within a row is unique. A column is also this, all numbers in a column must be unique. The same goes for a box. So if you store these rules as a data structure, then you can create these rules as you which, to solve a Hyper-Sudoku, Nonomino, and even a Samurai Sudoku!

• Thank you for that neat condense code. I didn't think of calculating the different parts in this manner but I shall keep it in mind for the future too. I shall have to really understand the Sudoku code you linked to. I got the gist of your thoughts on Extensibility and I'm trying to refactor my code in a way that I understood. Thanks a lot!! – rdsarna Oct 18 '14 at 12:53

Unfortunately, your code doesn't solve sudoku correctly. For example

public static final int[][] hardGrid = Sudoku.stringsToGrid(
"3 7 0 0 0 0 0 8 0",
"0 0 1 0 9 3 0 0 0",
"0 4 0 7 8 0 0 0 3",
"0 9 3 8 0 0 0 1 2",
"0 0 0 0 4 0 0 0 0",
"5 2 0 0 0 6 7 9 0",
"6 0 0 0 2 1 0 4 0",
"0 0 0 5 3 0 9 0 0",
"0 3 0 0 0 0 0 5 1");


is solved as

[3, 7, 9, 1, 6, 4, 4, 8, 9, ]
[8, 6, 1, 4, 9, 3, 5, 7, 7, ]
[9, 4, 9, 7, 8, 5, 1, 6, 3, ]
[7, 9, 3, 8, 7, 7, 6, 1, 2, ]
[7, 1, 6, 2, 4, 9, 8, 3, 5, ]
[5, 2, 8, 3, 1, 6, 7, 9, 4, ]
[6, 8, 7, 9, 2, 1, 8, 4, 8, ]
[1, 8, 2, 5, 3, 4, 9, 7, 6, ]
[9, 3, 4, 6, 7, 8, 2, 5, 1, ]


Looking at the first line we can see two 4-s in a row. This is not correct

• Welcome to Code Review! It's great that you found a bug in OP's code; it would be nice to expand a bit on why this is happening though. – Mathieu Guindon Dec 6 '14 at 19:10
• Hi Anton, Thank you for reporting that bug. I identified said bug myself a couple of days after posting the code for review here. It was occurring because the Spots in the grid were being passed by reference. So even after a solution was found, the Spots were changing as the algorithm looked for more solutions. I fixed the bug by creating a new List of solvedSpots every time while adding to the list of solutions. I'm new here too, so I do not know how to handle such a situation. Should I update the question or add an answer that points out and corrects the bug? – rdsarna Dec 7 '14 at 16:27
• I think it would be great, if you add the part of code that solves the problem as a comment to your own post. Or you can edit your post and add the solution at the end. – Anton Dec 7 '14 at 16:52
• Actually I have tried the solution you offered and found out that it doesn't fix the bug entirely. Problems still occur, if you try to solve "hardGrid". The fixed algorithm returns no sollutions – Anton Dec 7 '14 at 18:47
• I added a new answer with the fix for this bug. I actually didn't give the correct answer in the comment above. Sorry for that. – rdsarna Dec 7 '14 at 21:41

I have found a bug in the originally posted code. As pointed out by Anton, the resulting solution is not correct in quite a few cases.

This snippet in the recursive method solveSudoku() is the culprit -

    /* Check if the value is valid according to the current
* state of the grid */
if (valueIsValid(value, currentSpot)) {
currentSpot.setValue(value);
updateGridStateWithValue(value, currentSpot);

int newIndex = index + 1;
solveSudoku(emptySpots, solvedSpots, newIndex);

/* Backtrack when the method above returns */
emptySpots.get(index).setValue(0);
solvedSpots.remove(currentSpot);
updateGridStateWithValue(value, currentSpot);
}


The problem statement is solvedSpots.add(currentSpot);. The bug is occurring because currentSpot is being passed by reference. So even after a solution is found by the recursive method, the Spots keeps changing as the algorithm looks for more solutions. I fixed the bug by creating a new Spot as a copy of currentSpot every time while adding to the list of solvedSpots. solvedSpots.add(new Spot(currentSpot));

This solved the problem for me. Please let me know if its still buggy.