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.javapackage 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.javapackage 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.javapackage 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.javapackage 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.
Sudoku Solver - uses DFS and Constraint Propagation
java;sudoku