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<String, String> 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<String, String> 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<String, String> 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<String, String> cMap = new LinkedHashMap<>(this.candidateMap);
for (Map.Entry<String, String> entry : cMap.entrySet()) {
String square = entry.getKey();
String candidates = entry.getValue();
// check for wrong solution
if (candidates.isEmpty()) {
return null;
}
// check for finalised
if (candidates.length() == 1) {
for (String peer : PEERS.get(square)) {
String peerValues = cMap.get(peer);
if (peerValues.length() > 1 &&
peerValues.contains(candidates)) {
eliminations++;
peerValues = peerValues.replace(candidates, "");
cMap.put(peer, peerValues);
}
}
}
}
return eliminations == 0 ? this : new Board(cMap);
}
/**
* Returns <code>true</code> if every square is marked and has only one
* candidate.
*
* @return <code>true</code> if every square is marked and has only one
* candidate.
*/
public boolean isSolved() {
for (String values : candidateMap.values()) {
if (values.length() > 1) {
return false;
}
}
return true;
}
/**
* Returns <code>true</code> if there is any repetition in any of the units.
*
* @return <code>true</code> if there is any repetition in any of the units.
*/
public boolean isWrong() {
for (List<String> unit : UNITS) {
for (char number : CANDIDATES.toCharArray()) {
int count = 0;
for (String square : unit) {
String candidates = candidateMap.get(square);
if (candidates.length() == 1 &&
candidates.charAt(0) == number)
count++;
}
if (count > 1) return true;
}
}
return false;
}
/**
* Returns the square with the minimum number of candidates. This is
* useful in search to reduce the rate of choosing the wrong branch.
*
* @return The square with the minimum number of candidates.
*/
public Map.Entry<String, String> minimumCandidatePair() {
Map.Entry<String, String> minimum = null;
int number = SIZE + 1;
for (Map.Entry<String, String> entry : candidateMap.entrySet()) {
String candidates = entry.getValue();
if (number > candidates.length() && candidates.length() > 1) {
number = candidates.length();
minimum = entry;
}
}
return minimum;
}
/**
* Returns the current Board state as a String. The unmarked squared are
* represented by a '.'.
*
* @return The current Board state as a String.
*/
public String toString() {
StringJoiner fullJoiner = new StringJoiner(
"\n",
"\n+-----------------------+\n",
"\n+-----------------------+\n");
StringJoiner lineJoiner = new StringJoiner(" ", "| ", " |");
int i = 1, j = 1;
for (String value : candidateMap.values()) {
lineJoiner.add(value.length() == 1 ? value : ".");
if (i % SIZE == 0) {
fullJoiner.add(lineJoiner.toString());
lineJoiner = new StringJoiner(" ", "| ", " |");
if (j % UNIT == 0 && j != SIZE) {
fullJoiner.add("|-------+-------+-------|");
}
j++;
} else if (i % UNIT == 0) {
lineJoiner.add("|");
}
i++;
}
return fullJoiner.toString();
}
}
Constants.java
package core;
import java.util.*;
/**
* This class generates and stores constants that will be used frequently
* throughout the project.
*
* @author Subhomoy Haldar
* @version 1.0
*/
public class Constants {
/**
* The side of the smaller square unit.
*/
public static final int UNIT = 3;
/**
* The number of squares in one unit.
*/
public static final int SIZE = UNIT * UNIT;
/**
* The total number of squares in the game.
*/
public static final int NUMBER_OF_SQUARES = SIZE * SIZE;
/**
* The String containing all the possible candidates.
*/
public static final String CANDIDATES;
/**
* The list of all the squares in the game.
*/
public static final List<String> SQUARES;
/**
* The list of all units (rows, columns, squares) in the game.
*/
public static final List<List<String>> UNITS;
/**
* The map between every square and its set of peers.
*/
public static final Map<String, Set<String>> PEERS;
/**
* The maximum number of times the Generator will run the shuffle loop.
*/
protected static final int MAX_SHUFFLE = 20;
static {
// All the possibilities linearly stored in this String
StringBuilder builder = new StringBuilder(SIZE);
for (int i = 1; i <= SIZE; i++) {
builder.append(i);
}
CANDIDATES = builder.toString();
// Generate the square labels
List<String> squareList = new ArrayList<>(NUMBER_OF_SQUARES);
char row = 'A';
char col;
for (int i = 0; i < SIZE; i++, row++) {
col = '1';
for (int j = 0; j < SIZE; j++, col++) {
String square = "" + row + col;
squareList.add(square);
}
}
SQUARES = Collections.unmodifiableList(squareList);
// Generate the units
List<List<String>> temporaryLists = new ArrayList<>(SIZE * 3);
// First, the rows
row = 'A';
for (int i = 0; i < SIZE; i++, row++) {
List<String> squares = new ArrayList<>(SIZE);
col = '1';
for (int j = 0; j < SIZE; j++, col++) {
squares.add("" + row + col);
}
temporaryLists.add(squares);
}
// Second, the columns
col = '1';
for (int i = 0; i < SIZE; i++, col++) {
row = 'A';
List<String> squares = new ArrayList<>(SIZE);
for (int j = 0; j < SIZE; j++, row++) {
squares.add("" + row + col);
}
temporaryLists.add(squares);
}
// Third, the squares
int xOffset = 0;
int yOffset = 0;
while (xOffset < UNIT && yOffset < UNIT) {
List<String> squares = new ArrayList<>(SIZE);
for (int i = 0; i < UNIT; i++) {
for (int j = 0; j < UNIT; j++) {
col = (char) ('1' + xOffset * UNIT + j);
row = (char) ('A' + yOffset * UNIT + i);
squares.add("" + row + col);
}
}
temporaryLists.add(squares);
xOffset++;
if (xOffset == UNIT) {
xOffset = 0;
yOffset++;
}
}
UNITS = Collections.unmodifiableList(temporaryLists);
// The peers for each square
Map<String, Set<String>> peerMap = new HashMap<>(NUMBER_OF_SQUARES);
for (String square : SQUARES) {
Set<String> peers = new HashSet<>(SIZE * 3 + 2 * (SIZE - UNIT));
UNITS.stream()
.filter(unit -> unit.contains(square))
.forEach(peers::addAll);
peers.remove(square);
peerMap.put(square, peers);
}
PEERS = Collections.unmodifiableMap(peerMap);
}
}
Parser.java
package core;
import java.util.LinkedHashMap;
import java.util.Map;
import static core.Constants.*;
/**
* Handles the parsing of various formats and produces a Board.
*
* @author Subhomoy Haldar
* @version 1.0
*/
public class Parser {
/**
* Parses a given String and tries to generate a Board with the required
* state and mappings.
* <p>
* This parser will only accept numbers 1 through 9 (or Constants#SIZE)
* and map them to their respective squares. '0' and '.' represent blank
* squares. <b>All other characters are ignored.</b>
*
* @param input The input String to parse.
* @return The corresponding Board.
* @throws IllegalArgumentException If the input is invalid.
*/
public static Board parse(String input) throws IllegalArgumentException {
Map<String, String> state = new LinkedHashMap<>(NUMBER_OF_SQUARES);
int i = 0;
for (String square : SQUARES) {
try {
char c;
do {
c = input.charAt(i++);
} while (!(CANDIDATES.indexOf(c) > -1 || c == '0' || c == '.'));
state.put(square, CANDIDATES.indexOf(c) > -1
? String.valueOf(c)
: CANDIDATES);
} catch (StringIndexOutOfBoundsException ignore) {
throw new IllegalArgumentException("Input cannot be parsed.");
}
}
return new Board(state);
}
/**
* Parses the given trusted array. It is used internally to generate the
* initial Board randomly.
*
* @param trustedArray The trusted array to parse.
* @return The corresponding Board.
*/
protected static Board parse(int[][] trustedArray) {
Map<String, String> state = new LinkedHashMap<>(NUMBER_OF_SQUARES);
int i = 0, j = 0;
for (String square : SQUARES) {
char c = (char) ('0' + trustedArray[i][j++]);
state.put(square, CANDIDATES.indexOf(c) > -1
? String.valueOf(c)
: CANDIDATES
);
if (j == SIZE) {
j = 0;
i++;
}
}
return new Board(state);
}
}
Main.java
package core;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
/**
* The main class that handles search and constraint propagation methods. It
* serves as the entry-point.
*
* @author Subhomoy Haldar
* @version 1.0
*/
public class Main {
/**
* A handy template for reference.
*/
private static final String BLANK = "" +
"+-----------------------+\n" +
"| . . . | . . . | . . . |\n" +
"| . . . | . . . | . . . |\n" +
"| . . . | . . . | . . . |\n" +
"|-------+-------+-------|\n" +
"| . . . | . . . | . . . |\n" +
"| . . . | . . . | . . . |\n" +
"| . . . | . . . | . . . |\n" +
"|-------+-------+-------|\n" +
"| . . . | . . . | . . . |\n" +
"| . . . | . . . | . . . |\n" +
"| . . . | . . . | . . . |\n" +
"+-----------------------+";
/**
* The entry point for the program. Currently it does not accept any input.
* It won't be difficult to do that. I encourage everyone to tinker with
* the code.
*
* @param args The command-line arguments (which are ignored)
*/
public static void main(String[] args) {
// The following is supposed to be the world's "hardest" Sudoku puzzle.
Board board = Parser.parse("" +
"+-----------------------+\n" +
"| 8 . . | . . . | . . . |\n" +
"| . . 3 | 6 . . | . . . |\n" +
"| . 7 . | . 9 . | 2 . . |\n" +
"|-------+-------+-------|\n" +
"| . 5 . | . . 7 | . . . |\n" +
"| . . . | . 4 5 | 7 . . |\n" +
"| . . . | 1 . . | . 3 . |\n" +
"|-------+-------+-------|\n" +
"| . . 1 | . . . | . 6 8 |\n" +
"| . . 8 | 5 . . | . 1 . |\n" +
"| . 9 . | . . . | 4 . . |\n" +
"+-----------------------+"
);
//Board board = Parser.parse(Generator.generateSolved());
System.out.println(board);
List<Board> solutions = new ArrayList<>();
search(board, solutions);
if (solutions.isEmpty()) {
System.out.println("No solution found. Input is invalid.");
} else if (solutions.size() == 1) {
System.out.println(solutions.get(0));
} else {
System.out.println("Invalid Sudoku : multiple solutions.");
System.out.println("Number of solutions = " + solutions.size());
System.out.println("The solutions are ... ");
System.out.println(solutions);
}
}
/**
* Carries on constraint propagation till no further values can be
* eliminated.
*
* @param board The starting point for propagation.
* @return The end result of propagation.
*/
private static Board propagateTillPossible(Board board) {
while (true) {
Board newBoard = board.propagate();
if (newBoard == null || newBoard == board) return newBoard;
board = newBoard;
}
}
/**
* Performs a DFS (Depth-First-Search) of the possible states. Eliminates
* as many state possibilities as possible using constraint propagation.
*
* @param board The state to work with.
*/
private static void search(Board board, List<Board> solutions) {
// The board provided is faulty
if (board == null || board.isWrong())
return;
// Solution obtained
if (board.isSolved()) {
solutions.add(board);
return;
}
// Proceeding with the square with minimum candidates helps to reduce
// the chance of failure. For example, if we proceed with 7 (say)
// possibilities, we may fail 6 out of 7 times. However, if we
// proceed with 2 (say), we may fail at most half of the time.
Map.Entry<String, String> pair = board.minimumCandidatePair();
// Try out every possibility and see how far (or deep into the search
// space) we can go. At least one branch is guaranteed to yield a
// solution.
for (char c : pair.getValue().toCharArray()) {
String value = String.valueOf(c);
Board next = new Board(board, pair.getKey(), value);
next = propagateTillPossible(next);
search(next, solutions);
}
}
}
I'm not posting Generator.java because it's still unfinished.
Comments/criticism welcome on any aspect.