8
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Has your question been resolved? If so, please consider accepting an answer. \$\endgroup\$
    – Emily L.
    Jul 10, 2019 at 7:01

1 Answer 1

3
\$\begingroup\$

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<Integer> 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<Integer, Set<Integer>> 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().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.