Sudoku Solver - uses DFS and Constraint Propagation

Disclaimer: My code is translated from Peter Norvig's Python code.

This simple code uses only two techniques: Constraint Satisfaction and Depth-First-Search. Backtracking is not implemented.

Here's the code:

Board.java

```
package core;

import java.util.*;

import static core.Constants.*;

/**
* This class represents a particular Board "state", with immutable mappings.
* These can be considered as nodes in the search tree without any links. The
* creation of Nodes is done separately in Main.java, during search.
*
* @author Subhomoy Haldar
* @version 1.0
*/
public class Board {

/**
* This immutable map stores the relations between the squares and the
* possible values.
*/
private final Map candidateMap;

/**
* Creates a new Board with the given trusted map. Used internally by Main.
*
* @param trustedCandidateMap The trusted map to be used.
*/
protected Board(final Map trustedCandidateMap) {
candidateMap = Collections.unmodifiableMap(trustedCandidateMap);
}

/**
* It is used to create a new Board from a pre-existing one with just one
* change to be effected.
*
* @param previous The previous state/node in the tree.
* @param square The square to manipulate.
* @param trustedValue The value to assign to the square.
*/
protected Board(final Board previous, String square, String trustedValue) {
Map temporaryMap
= new LinkedHashMap<>(previous.candidateMap);
temporaryMap.put(square, trustedValue);
candidateMap = Collections.unmodifiableMap(temporaryMap);
}

/**
* Performs constraint propagation. It is basically removing the
* possibilities based on marked squares. Those with only one possible
* candidate end up being marked.
*
* @return The result of applying constraint propagation.
*/
public Board propagate() {
int eliminations = 0;
Map cMap = new Lin

Use of String

I do not like the use of String for representing board position and grid candidates. For board positions I think you would have been better to just use grid index \$0\le i\lt 9^2\$. Not only is this more effective because you don't have to do a lot of string comparisons and manipulation, and you don't have to compute the string hash for every lookup in the candidateMap, but it is also more clear to read.

For the candidates for a given position I think that a Set would be better. Again it communicates the intent better and HashSet allows faster, \$\mathcal{O}\left(1\right)\$ lookup compared to String.contains which is \$\mathcal{O}\left(n\right)\$.

I think overall using Map> for candidateMap would be much cleaner and easier to read.

Single Responsibility Principle

The propagate() function checks for wrong solutions and performs constraint propagation. Because you have isWrong() which you are checking in the DFS then then I don't think that propagate() needs to, or even should check for wrong solutions.

Constants

I think that some of the constants, SQUARES, UNITS, PEERS are a bit hard to understand at a glance. I think mainly this is due to the use of String everywhere. And I think that they subtract from readability.

For example look at the UNITS constant, it is used at exactly one place, in isWrong(). When reading isWrong() I have to look at both the constants and the code and figure out how they relate. For me I would have liked to just read the complete logic in isWrong() without flicking back and forth between constants and board. Same thing goes for PEERS and propagate.

With that in mind I'm not going to review Constants.java further, even though I think the name is spectacularly bad, at least name it SudokuConstants same thing with Parser and Board.

Parser

I don't find the parser particularly interesting and the comments I have already given about use of String would make any review here moot I think.

PropagateTillPossible

The name is a bit hard to understand, possible what? Reading the code I see that it repeatedly propagates until either the solution is deemed invalid or there is no change in the board. To be honest I think that this should be done by Board.Propagate() simply because I can't think of a case where you wouldn't want to propagate all the way.

DFS with Back-Tracking

The depth first search that you have implemented is using back-tracking. The conceptual implementation is this:

dfs(node, solutions)
    if(reject(node)) (#3)
        return
    if(accept(node))
        solutions.add(node)

    child = first(node) (#1)
    while(child != nil)
        dfs(child)
        child = next(child) (#2)
    end
end

where reject(node) returns true only if the node can never become a solution (i.e. Board.isWrong()). And accept returns true only if the node is a valid solution (i.e. Board.isSolved()). The function first return the first child of node in the search tree in your case this is minimumCandidatePair() and taking the first candidate. The function next returns the next sibling of child in the search tree, in your case it is equivalent to taking the next candidate grid value from the minimumCandidatePair().

StackExchange Code Review Q#123142, answer score: 3