5
\$\begingroup\$

I was compelled to look into a Sudoku Solver in Java using the principles I have learned in a course, namely I wanted to make something that included backtracking and forward checking.

Has anybody else managed to produce a Sudoku solver that uses the forward checking algorithm that is more efficient than the backtracking on its own?

I have produced this, and found that my code must be very inefficient as it's a lot slower than just backtracking, even on complex problems.

Any advice on how I should implement the forward checking algorithm would be nice. Initially I had HashMaps with the cell number as a Key and an ArrayList as the domain. I then considered that this is wildly inefficient and changed the code to a String array which used the cell number as an index and then put a string in it containing the domain.

This was a heck of a lot more efficient, but is still a lot worse than just backtracking.

package sudokuai;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author Nik Bradley $date $time
 */

/**
 * Concrete Sudoku_AI algorithm implementation using Backtracking With Forward Checking
 */
class Sudoku_AI_Backtracking_ForwardChecking implements Sudoku_AI {

    private static final String NAME = "Backtracking with Forward Checking";

    private static final int GRIDSIZE_ROW = 9;
    private static final int GRIDSIZE_COLUMN = 9;
    private static final int BOXSIZE = 3;

    private Integer[][] solution = new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
    private String[] backupDomains,domains = new String[GRIDSIZE_ROW*GRIDSIZE_COLUMN+1];
    //private HashMap domains = new HashMap(81);
    //private HashMap backupDomains;

    private boolean emptyDomainFlag;

    public Sudoku_AI_Backtracking_ForwardChecking() {
    }

    public void initDomains() {

        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                //creates 81 domains with the values 1-9 in them
                int cell = (i * 9) + 1 + j;
                domains[cell]="123456789";
            }
        }
    }

    /**
     * Largely inefficient, looks through every cell with data assigned and
     * checks if there are too many assignments of the same value in each row
     * column and box for that specific cell.
     */
    @Override
    public boolean isSolvable(Integer[][] currentBoard) {

        Integer[][] board = new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            System.arraycopy(currentBoard[i], 0, board[i], 0, GRIDSIZE_COLUMN);
        }

        /* Finds the number of cells that have data on the board */
        int numberOfCells = getCellCount(board);

        for (int i = 0; i < numberOfCells; i++) {
            int[] cell = getNextCell(board);

            int[] counts = countUsage(board[cell[0]][cell[1]], cell, board);

            if (counts[0] + counts[1] + counts[2] == 3) {
                board[cell[0]][cell[1]] = null;
            } else {
                return false;
            }
        }

        return true;
    }

    /**
     * Counts the amount of cells with data in them on the board.
     */
    private int getCellCount(Integer[][] board) {
        int count = 0;
        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                if (board[i][j] != null) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * Gets the next cell with data in it on the board
     */
    private int[] getNextCell(Integer[][] board) {
        int[] cell = new int[2];
        all:
        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                if (board[i][j] != null) {
                    cell[0] = i;
                    cell[1] = j;
                    break all;      /* used to break out of both loops when a cell is found */

                }
            }
        }
        return cell;
    }

    /**
     * Created for debugging, not used.
     *
     * Would print out a list of the domains, then do a first round of forward
     * checking and then reprint the domains.
     */
    private void doInitialDomains() {

        System.out.println(domains);

        //INITIAL FORWARD CHECK
        initial_ForwardCheck();

        System.out.println(domains);
    }

    /**
     * This method kicks off the solver AI, it does an initial forward check
     * which checks all cells on the board and reduces their domains.
     *
     * It then starts the solve method and if it gets a success it returns the
     * solution to the calling method. If it fails to find a solution it creates
     * a new grid with null values and returns it
     */
    @Override
    public Integer[][] getSolution() {

        emptyDomainFlag = false;
        initDomains();

        //INITIAL FORWARD CHECK
        initial_ForwardCheck();

        if (solveSudoku()) {
            //domains.clear();
            return solution;
        } else {
            return new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
        }

    }

    /**
     * The solve algorithm performs a recursive search through values in the
     * domains and attempts to assign them to a cell starting from the upper
     * left cell and proceeds row by row
     */
    private boolean solveSudoku() {

        /* Finds the next empty cell */
        int[] nextCell = findNextCell();

        /* checks if the cell is not empty, if so we have finished */
        if (solution[nextCell[0]][nextCell[1]] != null) {
            return true;
        }

        /**
         * Converts the coords of the cell into a number between 1-81
         * representing the cell then it uses that to get the ArrayList of
         * domains from a HashMap, key = int of cell (1-81)
         */
        int cell = (nextCell[0] * 9) + 1 + nextCell[1];

//        for (int i=0;i<domains.size();i++){
//            domainSave.put(i+1, domains.get(i));
//        }
        //domainSave.putAll(domains);
        String mainDomain = domains[cell];
        String domain = mainDomain;

        /**
         * Loops through all available domains in the ArrayList and attempts to
         * use them calls isSafe to ensure that the value can be used in the row
         * / column / box without clashing with constraints.
         *
         * If it can be used within constraints, assign it and then empty the
         * relevant domains as long as the domains all have possible values,
         * call this method to solve the next cell if not remove the value and
         * start again.
         *
         * No remaining options = backtrack
         */

        for (int i=0;i<domain.length();i++){
            int value = Integer.valueOf(domain.substring(i, i+1));
            if (isSafe((Integer) value, nextCell, solution)) {

                String[] domainSave = domains.clone();

                //domainSave = (HashMap) domains.clone();

                solution[nextCell[0]][nextCell[1]] = value;

                emptyDomains(nextCell);

                if (!emptyDomainFlag) {
                    if (solveSudoku()) {
                        return true;
                    }
                }
                solution[nextCell[0]][nextCell[1]] = null;
                domains = domainSave;
                emptyDomainFlag = false;
            }
        }
        return false;       // Triggers backtracking
    }

    /**
     * deepCopy allows us to use the HashMap class to alter domains.
     * 
     * @param original the original HashMap to be copied
     * @returns a duplicate NEW HashMap of the original.
     */
    public static HashMap deepCopy(HashMap original){
        HashMap copy = new HashMap();
        for (Object ob : original.entrySet()){
            HashMap.Entry entry = (HashMap.Entry) ob;
            copy.put(entry.getKey(),new ArrayList((ArrayList) entry.getValue()));
        }
        return copy;
    }

    /**
     * Empties the relevant domains for the cell just updated.
     *
     * It first creates a backup of the domains and then empties them all while
     * there is no flag set that there is an empty domain.
     *
     * Once done if there is an empty domain it clears the domains and rolls
     * them back again
     */
    public void emptyDomains(int[] cell) {

        fcRow(cell);
        if (!emptyDomainFlag) {
            fcCol(cell);
        }
        if (!emptyDomainFlag) {
            fcBox(cell);
        }
    }

    /**
     * Finds the next empty cell
     */
    private int[] findNextCell() {
        int[] cell = new int[2];
        all:
        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                if (solution[i][j] == null) {
                    cell[0] = i;
                    cell[1] = j;
                    break all;
                }
            }
        }
        return cell;
    }

    /**
     * counts the amount of occurrences of data within rows / columns / boxes
     * and returns the numbers in an array.
     */
    private int[] countUsage(int value, int[] cell, Integer[][] board) {
        int countRow = 0;
        int countCol = 0;
        int countBox = 0;

        for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
            if (board[cell[0]][i] == null) {
            } else if (board[cell[0]][i] == value) {
                countRow++;
            }
        }

        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            if (board[i][cell[1]] == null) {
            } else if (board[i][cell[1]] == value) {
                countCol++;
            }
        }

        /* Figures out the start of the current 3x3 box */
        int boxRow = cell[0] - (cell[0] % 3);
        int boxCol = cell[1] - (cell[1] % 3);

        for (int i = 0; i < BOXSIZE; i++) {
            for (int j = 0; j < BOXSIZE; j++) {
                if (board[i + boxRow][j + boxCol] == null) {
                } else if (board[i + boxRow][j + boxCol] == value) {
                    countBox++;
                }
            }
        }

        int[] counts = {countRow, countCol, countBox};
        return counts;
    }

    /**
     * Checks if a value is used in the row already, returns false if it is.
     */
    private boolean usedInRow(int value, int row, Integer[][] board) {
        boolean safe = true;
        for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
            if (board[row][i] == null) {
            } else if (board[row][i] == value) {
                safe = false;
                break;
            }
        }
        return safe;
    }

    /**
     * Checks if a value is used in the column already, returns false if it is.
     */
    private boolean usedInColumn(int value, int column, Integer[][] board) {
        boolean safe = true;
        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            if (board[i][column] == null) {
            } else if (board[i][column] == value) {
                safe = false;
                break;
            }
        }
        return safe;
    }

    /**
     * Checks if a value is used in the box already, returns false if it is.
     */
    private boolean usedInBox(int value, int[] cell, Integer[][] board) {
        boolean safe = true;

        /**
         * boxRow is the starting row of the current box, determined by the
         * cells x coord - the mod by 3 boxCol is the starting column of the
         * current box, determined by the cells y coord - the mod by 3
         */
        int boxRow = cell[0] - (cell[0] % 3);
        int boxCol = cell[1] - (cell[1] % 3);

        //* loop through the box and check if any of the values match the selected one */
        for (int i = 0; i < BOXSIZE; i++) {
            for (int j = 0; j < BOXSIZE; j++) {
                if (board[i + boxRow][j + boxCol] == null) {
                } else if (board[i + boxRow][j + boxCol] == value) {
                    safe = false;
                    break;
                }
            }
        }

        return safe;
    }

    /**
     * Calls each of the methods to check if a value is already in either row /
     * column / box and if it is return false.
     */
    private boolean isSafe(int value, int[] cell, Integer[][] board) {

        //Check if a number has already been used in the column or row or box
        return usedInRow(value, cell[0], board) && usedInColumn(value, cell[1], board) && usedInBox(value, cell, board);
    }

    /**
     * Performs the initial forward check once a puzzle has been sent to the
     * solver
     */
    public void initial_ForwardCheck() {
        setupInitialDomains();
        fcAllRow();
        fcAllCol();
        fcAllBox();

    }

    public static String stripChars(String input, String strip) {
    StringBuilder result = new StringBuilder();
    for (char c : input.toCharArray()) {
        if (strip.indexOf(c) == -1) {
            result.append(c);
        }
    }
    return result.toString();
}

    /**
     * Finds out if the cell has a value if so remove all possible domain
     * values.
     *
     * Once done it adds the value of the cell back to the domain
     */
    private void setupInitialDomains() {
        for (int i = 0; i < GRIDSIZE_ROW; i++) {
            //Get all the values in the row
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                if (solution[i][j] != null) {
                    int cell = (i * 9) + 1 + j;   
                    domains[cell] = solution[i][j].toString();  
                }
            }
        }
    }

    /**
     * Remove the values from all of the domains in the row
     */
    public void removeRowDomainValues(int row, String initialValues) {
        String domain;
        for (int j = 0; j < GRIDSIZE_COLUMN; j++) {

            /* convert I,J coord into numerical value of 81 to find the domain */
            int cell = (row * 9) + 1 + j;

            domain = domains[cell];
            domain = stripChars(domain,initialValues);

            domains[cell] = domain;

            if (solution[row][j] != null){
                domains[cell] = (solution[row][j].toString());
            }

            /* if a domain shrinks to nothing we have an invalid solution, turn back now! */
            if (domains[cell].length() < 1) {
                //System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
                emptyDomainFlag = true;
                break;
            }
        }
    }

    /**
     * Remove the values from all of the domains in the column
     */
    public void removeColDomainValues(int col, String initialValues) {
        String domain;
        for (int j = 0; j < GRIDSIZE_ROW; j++) {
            /* convert I,J coord into numerical value of 81 to find the domain */
            int cell = (j * 9) + 1 + col;

            domain = domains[cell];
            domain = stripChars(domain,initialValues);

            domains[cell] = domain;

            if (solution[j][col] != null){
                domains[cell] = (solution[j][col].toString());
            }

            /* if a domain shrinks to nothing we have an invalid solution, turn back now! */
            if (domains[cell].length() < 1) {
                //System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
                emptyDomainFlag = true;
                break;
            }
        }
    }

    private void removeBoxDomainValues(int boxRow, int boxCol, String initialValues) {
        String domain;

        escape:

        for (int cellRow = boxRow; cellRow < boxRow+BOXSIZE; cellRow++) {
            for (int cellCol = boxCol; cellCol < boxCol+BOXSIZE; cellCol++) {

                /* convert coords into numerical value of 81 to find the domain */
                int cell = (cellRow * 9) + 1 + cellCol;


                domain = domains[cell];
                domain = stripChars(domain,initialValues);

                domains[cell] = domain;

                if (solution[cellRow][cellCol] != null){
                    domains[cell] = (solution[cellRow][cellCol].toString());
                }

                /* if a domain shrinks to nothing we have an invalid solution, turn back now! */
                if (domains[cell].length() < 1) {
                    //System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
                    emptyDomainFlag = true;
                    break escape;       //breaks from all loops
                }
            }
        }
    }

    /**
     * Forward Checks every row in the puzzle
     */
    private void fcAllRow() {

        for (int i = 0; i < GRIDSIZE_ROW; i++) {

            String initialValues = "";
            /* Get all the values in the row */
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                if (solution[i][j] != null) {
                    initialValues = initialValues+solution[i][j].toString();
                }
            }

            /* If there are values that need to be removed from domains remove them */
            if (initialValues.length() > 0) {
                removeRowDomainValues(i, initialValues);
            }
            /* if we have created an empty domain stop doing forward checking */
            if (emptyDomainFlag) {
                break;
            }
        }
    }

    /**
     * Forward Checks every column in the puzzle
     */
    private void fcAllCol() {

        for (int i = 0; i < GRIDSIZE_COLUMN; i++) {

            String initialValues = "";
            /* Get all the values in the column */
            for (int j = 0; j < GRIDSIZE_ROW; j++) {
                if (solution[j][i] != null) {
                    initialValues = initialValues+solution[j][i].toString();
                }
            }
            /* If there are values that need to be removed from domains remove them */
            if (initialValues.length() > 0) {
                removeColDomainValues(i, initialValues);
            }

            /* if we have created an empty domain stop doing forward checking */
            if (emptyDomainFlag) {
                break;
            }
        }
    }

    /**
     * Forward Checks every box in the puzzle
     */
    private void fcAllBox() {      

        int cellRow, cellCol;

        escape:
        /**
         * Loop through all the boxes Finds the top left square of each 3x3 box.
         */
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                String initialValues = "";

                /* loops through each cell in a 3x3 box */
                for (int x = 0; x < BOXSIZE; x++) {
                    for (int y = 0; y < BOXSIZE; y++) {
                        cellRow = (3 * i) + x;
                        cellCol = (3 * j) + y;

                        if (solution[cellRow][cellCol] != null) {
                            initialValues = initialValues+solution[cellRow][cellCol].toString();
                        }
                    }
                }

                /* If there are values that need to be removed from domains remove them */
                if (initialValues.length() > 0) {
                    removeBoxDomainValues(i*3, j*3, initialValues);
                }

                /* if we have created an empty domain stop doing forward checking */
                if (emptyDomainFlag) {
                    break escape;       //Break all loops
                }
            }
        }
    }

    /**
     * Forward check just 1 row, determined by the @param currentCell.
     */
    private void fcRow(int[] currentCell) {
        String initialValues = "";

        if (solution[currentCell[0]][currentCell[1]] != null) {
            initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();
        }

        /* If there are values that need to be removed from domains remove them */
        if (initialValues.length() > 0) {
            removeRowDomainValues(currentCell[0], initialValues);
        }
    }

    /**
     * Forward check just 1 column, determined by the @param currentCell.
     */
    private void fcCol(int[] currentCell) {
        String initialValues = "";

        if (solution[currentCell[0]][currentCell[1]] != null) {
            initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();
        }

        /* If there are values that need to be removed from domains remove them */
        if (initialValues.length() > 0) {
            removeColDomainValues(currentCell[1], initialValues);
        }
    }

    private void fcBox(int[] currentCell) {
        String initialValues = "";

        /* Finds the top left square of the current 3x3 box. */
        int boxRow = currentCell[0] - (currentCell[0] % 3);
        int boxCol = currentCell[1] - (currentCell[1] % 3);

        initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();

        /* If there are values that need to be removed from domains remove them */
        if (initialValues.length() > 0) {
            removeBoxDomainValues(boxRow, boxCol, initialValues);
        }

    }

    @Override
    public String getName() {
        return NAME;
    }

    @Override
    public void setSolution(Integer[][] userInputPuzzle) {
        this.solution = userInputPuzzle;
    }

}
\$\endgroup\$
6
\$\begingroup\$

Don't use strings to represent bits

I scanned over your code very quickly and the first thing to stick out was that you are using strings called domains all over the place. These domains are used as an array of characters, each of which is a possibility left in a row/column/box. Each domain starts with the value "123456789" and then characters are stripped from each domain as numbers are filled in.

What you should do instead of using a string is to simply use an int to represent a domain. The first 9 bits of the int will represent whether each of the nine numbers is still possible. So each int will start off with the value 0x1ff which in binary is 111111111. Then when you want to strip a possibility, you use the & operator like this:

// value is in the range 0..8.  If you want to use 1..9, use (value-1)
domain &= ~(1 << value);

Code like this:

    String initialValues = "";
    initialValues = initialValues+solution[currentCell[0]][currentCell[1]].toString();

would turn into this:

    int initialValues = 0;
    initialValues |= (1 << solution[currentCell[0]][currentCell[1]]);

One based vs Zero based

I know that Sudoku involves the numbers 1..9. But in your program, I think that it simplifies a lot of logic to solve using zero based numbers, i.e. 0..8. This applies to array indexing, bit numbering, row/column calculations, etc. When you finally want to print out some kind of information to the user, you can convert the numbers back to 1..9 at that point.

Two dimensional arrays vs one dimensional arrays

It's strange that you use two dimensional arrays sometimes (board,solution) but one dimensional arrays at other times (domains). I think you should just use one dimensional arrays everywhere. It would simplify things in that you don't have to use an int[2] cell type just to hold a row/column pair.

Hardcoded numbers

At the top of the file, you define this values nicely:

private static final int GRIDSIZE_ROW = 9;
private static final int GRIDSIZE_COLUMN = 9;
private static final int BOXSIZE = 3;

But then in your program, you don't consistently use them. I still see a lot of 3s and 9s all over the place. Examples:

    int cell = (i * 9) + 1 + j;
    int boxRow = cell[0] - (cell[0] % 3);
    int boxCol = cell[1] - (cell[1] % 3);

Other things

  1. This line was pretty ugly:

               break all;      /* used to break out of both loops when a cell is found */
    

    It could have just been:

               return cell;
    
  2. deepCopy() is dead code. It's probably a leftover from when you used a HashMap.

How to loop through all bits

int domainBits = 0x124; // Example value, could be any combination
while (domainBits != 0) {
    int lowestBitNumber = Integer.numberOfTrailingZeros(domainBits);
    domainBits &= ~(1 << lowestBitNumber);
    // Do stuff here on lowestBitNumber
}

In the above example, domainBits starts at 0x124 which is 100100100 in binary. The loop will loop three times. The first time, lowestBitNumber will be 2, the second time 5, the third time 8. These correspond to the three bits set in domainBits.

\$\endgroup\$
  • \$\begingroup\$ Thanks for taking the time to review it, i couldn't think of a simpler method of handling domain management but yours seems perfect I am going to implement it, as to my hardcoded, i was trying to prepare for additional sudoku models such as a 2x2, 4x4 or 5x5 grids but i kinda gave up on it midway through dev, but will look to fix that again, so that it will work with any model. Additionally i like your suggestion on that particularly ugly break statement, i didn't have my thinking cap on obviously as your suggestion is pretty simple and well obvious.. The deepcopy was indeed prior to using str \$\endgroup\$ – bradleykins May 14 '15 at 20:49
  • \$\begingroup\$ Can you provide a manner for converting the int into the next available value? \$\endgroup\$ – bradleykins May 14 '15 at 21:26
  • \$\begingroup\$ I guess, I'd stick with the 1-based representation. Excluding 0 is simple enough and the advantage of having a representation exactly corresponding with the problem domain is huge. +++ @bradleykins IIUYC you need to find a bit equal to 1. There are methods like Integer.numberOfTrailingZeros which do this very efficiently. Also bitCount is very useful. You could instead simply loop like (for int i=1; i<=9; ++i) {int mask = 1 << i; ...} which would be slower, but still a clear win when compared to using Strings. \$\endgroup\$ – maaartinus May 14 '15 at 21:49
  • \$\begingroup\$ thx maaartinus ill give that a go \$\endgroup\$ – bradleykins May 14 '15 at 22:19
  • \$\begingroup\$ @JS1 Im having bother trying to use this method of bits instead, when i want to change the domain to remove excluded bits, its messing the entire int up, im guessing because it is an int number? any advice? \$\endgroup\$ – bradleykins May 15 '15 at 16:13
4
\$\begingroup\$

Please be aware, I am now going to update some other areas of the code (boardsize hardcoding etc and anything else I have ignored for this bit except moving to zero based, and the 2D arrays kinda need a bit more thinking about to change as the API of this class passes them to other classes, so I'll need to rejig those if I do go full blown 1D.

    package sudokuai;

    /**
     * @author Nik Bradley $date $time
     */

    /**
     * Concrete Sudoku_AI algorithm implementation using Backtracking With Forward Checking
     */
    class Sudoku_AI_Backtracking_ForwardChecking implements Sudoku_AI {

        private static final String NAME = "Backtracking with Forward Checking";

        private static final int GRIDSIZE_ROW = 9;
        private static final int GRIDSIZE_COLUMN = 9;
        private static final int BOXSIZE = 3;

        private int steps =0;

        private Integer[][] solution = new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
        private int[] domains = new int[82];

        private boolean emptyDomainFlag;

        public Sudoku_AI_Backtracking_ForwardChecking() {
        }

        public void initDomains() {

            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                    //creates 81 domains with the values 1-9 in them
                    int cell = (i * 9) + 1 + j;  
                    domains[cell] = 0x1ff;              // bits represent 1 base values eg 987654321
                }
            }
        }

        /**
         * Largely inefficient, looks through every cell with data assigned and
         * checks if there are too many assignments of the same value in each row
         * column and box for that specific cell.
         */
        @Override
        public boolean isSolvable(Integer[][] currentBoard) {

            Integer[][] board = new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                System.arraycopy(currentBoard[i], 0, board[i], 0, GRIDSIZE_COLUMN);
            }

            /* Finds the number of cells that have data on the board */
            int numberOfCells = getCellCount(board);

            for (int i = 0; i < numberOfCells; i++) {
                int[] cell = getNextCell(board);

                int[] counts = countUsage(board[cell[0]][cell[1]], cell, board);

                if (counts[0] + counts[1] + counts[2] == 3) {
                    board[cell[0]][cell[1]] = null;
                } else {
                    return false;
                }
            }

            return true;
        }

        /**
         * Counts the amount of cells with data in them on the board.
         */
        private int getCellCount(Integer[][] board) {
            int count = 0;
            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                    if (board[i][j] != null) {
                        count++;
                    }
                }
            }
            return count;
        }

        /**
         * Gets the next cell with data in it on the board
         */
        private int[] getNextCell(Integer[][] board) {
            int[] cell = new int[2];
            all:
            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                    if (board[i][j] != null) {
                        cell[0] = i;
                        cell[1] = j;
                        break all;      /* used to break out of both loops when a cell is found */

                    }
                }
            }
            return cell;
        }

        @Override
        public Integer[][] getSolution() {

            emptyDomainFlag = false;
            initDomains();

            //INITIAL FORWARD CHECK
            initial_ForwardCheck();

            if (solveSudoku()) {
                return solution;
            } else {
                return new Integer[GRIDSIZE_ROW][GRIDSIZE_COLUMN];
            }

        }

        /**
         * The solve algorithm performs a recursive search through values in the
         * domains and attempts to assign them to a cell starting from the upper
         * left cell and proceeds row by row
         */
        private boolean solveSudoku() {

            /* Finds the next empty cell */
            int[] nextCell = findNextCell();

            /* checks if the cell is not empty, if so we have finished */
            if (solution[nextCell[0]][nextCell[1]] != null) {
                System.out.println("Steps = "+steps);
                return true;
            }

            /**
             * Converts the coords of the cell into a number between 1-81
             * representing the cell then it uses that to get the ArrayList of
             * domains from a HashMap, key = int of cell (1-81)
             */
            int cell = (nextCell[0] * 9) + 1 + nextCell[1];

    //        for (int i=0;i<domains.size();i++){
    //            domainSave.put(i+1, domains.get(i));
    //        }
            //domainSave.putAll(domains);
            int[] domainSave = domains.clone();

            /**
             * Loops through all available domains in the ArrayList and attempts to
             * use them calls isSafe to ensure that the value can be used in the row
             * / column / box without clashing with constraints.
             *
             * If it can be used within constraints, assign it and then empty the
             * relevant domains as long as the domains all have possible values,
             * call this method to solve the next cell if not remove the value and
             * start again.
             *
             * No remaining options = backtrack
             */
            int domain = domains[cell];
            while (domain != 0) {

                steps++;
                int lowestBitIndex = Integer.numberOfTrailingZeros(domain);
                domain = domain & ~(1 << lowestBitIndex);  

                solution[nextCell[0]][nextCell[1]] = lowestBitIndex+1;

                emptyDomains(nextCell);

                if (!emptyDomainFlag) {
                    if (solveSudoku()) {
                        return true;
                    }
                }
                solution[nextCell[0]][nextCell[1]] = null;
                domains = domainSave.clone();
                emptyDomainFlag = false;

            }
            domains = domainSave;
            return false;       // Triggers backtracking
        }  

        /**
         * Empties the relevant domains for the cell just updated.
         *
         * It first creates a backup of the domains and then empties them all while
         * there is no flag set that there is an empty domain.
         *
         * Once done if there is an empty domain it clears the domains and rolls
         * them back again
         */
        public void emptyDomains(int[] cell) {
            fcRow(cell);
            if (!emptyDomainFlag) {
                fcCol(cell);
            }
            if (!emptyDomainFlag) {
                fcBox(cell);
            }
        }

        /**
         * Finds the next empty cell
         */
        private int[] findNextCell() {
            int[] cell = new int[2];
            all:
            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                    if (solution[i][j] == null) {
                        cell[0] = i;
                        cell[1] = j;
                        break all;
                    }
                }
            }
            return cell;
        }

        /**
         * counts the amount of occurrences of data within rows / columns / boxes
         * and returns the numbers in an array.
         */
        private int[] countUsage(int value, int[] cell, Integer[][] board) {
            int countRow = 0;
            int countCol = 0;
            int countBox = 0;

            for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
                if (board[cell[0]][i] == null) {
                } else if (board[cell[0]][i] == value) {
                    countRow++;
                }
            }

            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                if (board[i][cell[1]] == null) {
                } else if (board[i][cell[1]] == value) {
                    countCol++;
                }
            }

            /* Figures out the start of the current 3x3 box */
            int boxRow = cell[0] - (cell[0] % 3);
            int boxCol = cell[1] - (cell[1] % 3);

            for (int i = 0; i < BOXSIZE; i++) {
                for (int j = 0; j < BOXSIZE; j++) {
                    if (board[i + boxRow][j + boxCol] == null) {
                    } else if (board[i + boxRow][j + boxCol] == value) {
                        countBox++;
                    }
                }
            }

            int[] counts = {countRow, countCol, countBox};
            return counts;
        }

        /**
         * Checks if a value is used in the row already, returns false if it is.
         */
        private boolean usedInRow(int value, int row, Integer[][] board) {
            boolean safe = true;
            for (int i = 0; i < GRIDSIZE_COLUMN; i++) {
                if (board[row][i] == null) {
                } else if (board[row][i] == value) {
                    safe = false;
                    break;
                }
            }
            return safe;
        }

        /**
         * Checks if a value is used in the column already, returns false if it is.
         */
        private boolean usedInColumn(int value, int column, Integer[][] board) {
            boolean safe = true;
            for (int i = 0; i < GRIDSIZE_ROW; i++) {
                if (board[i][column] == null) {
                } else if (board[i][column] == value) {
                    safe = false;
                    break;
                }
            }
            return safe;
        }

        /**
         * Checks if a value is used in the box already, returns false if it is.
         */
        private boolean usedInBox(int value, int[] cell, Integer[][] board) {
            boolean safe = true;

            /**
             * boxRow is the starting row of the current box, determined by the
             * cells x coord - the mod by 3 boxCol is the starting column of the
             * current box, determined by the cells y coord - the mod by 3
             */
            int boxRow = cell[0] - (cell[0] % 3);
            int boxCol = cell[1] - (cell[1] % 3);

            //* loop through the box and check if any of the values match the selected one */
            for (int i = 0; i < BOXSIZE; i++) {
                for (int j = 0; j < BOXSIZE; j++) {
                    if (board[i + boxRow][j + boxCol] == null) {
                    } else if (board[i + boxRow][j + boxCol] == value) {
                        safe = false;
                        break;
                    }
                }
            }

            return safe;
        }

        /**
         * Calls each of the methods to check if a value is already in either row /
         * column / box and if it is return false.
         */
        private boolean isSafe(int value, int[] cell, Integer[][] board) {

            //Check if a number has already been used in the column or row or box
            return usedInRow(value, cell[0], board) && usedInColumn(value, cell[1], board) && usedInBox(value, cell, board);
        }

        /**
         * Performs the initial forward check once a puzzle has been sent to the
         * solver
         */
        public void initial_ForwardCheck() {
            setupInitialDomains();
            fcAllRow();
            fcAllCol();
            fcAllBox();

        }

        public static String stripChars(String input, String strip) {
        StringBuilder result = new StringBuilder();
        for (char c : input.toCharArray()) {
            if (strip.indexOf(c) == -1) {
                result.append(c);
            }
        }
        return result.toString();
    }

        /**
         * Finds out if the cell has a value if so remove all possible domain
         * values.
         *
         * Once done it adds the value of the cell back to the domain
         */
        private void setupInitialDomains() {
            for (int i = 0; i < GRIDSIZE_ROW; i++) {            //each row
                for (int j = 0; j < GRIDSIZE_COLUMN; j++) {     //each column
                    if (solution[i][j] != null) {
                        int cell = (i * 9) + 1 + j; 

                        int value = solution[i][j];

                        int newDomain = (1 << value-1);
                        domains[cell] = newDomain;
                    }
                }
            }
        }

        /**
         * Remove the values from all of the domains in the row
         */
        public void removeRowDomainValues(int row, int initialValues) {
            for (int j = 0; j < GRIDSIZE_COLUMN; j++) {

                /* convert I,J coord into numerical value of 81 to find the domain */
                int cell = (row * 9) + 1 + j;

                domains[cell] &= ~initialValues;

                if (solution[row][j] != null){
                    int value = solution[row][j];
                    int bitValue = (1<<value-1);
                    //domains[cell] |= bitValue;        //add to existing bits, but there shouldnt be any so...
                    domains[cell] = bitValue;
                }

                /* if a domain shrinks to nothing we have an invalid solution, turn back now! */
                if (domains[cell] < 1) {
                    //System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
                    emptyDomainFlag = true;
                    break;
                }
            }
        }

        /**
         * Remove the values from all of the domains in the column
         */
        public void removeColDomainValues(int col, int initialValues) {
            for (int j = 0; j < GRIDSIZE_ROW; j++) {
                /* convert I,J coord into numerical value of 81 to find the domain */
                int cell = (j * 9) + 1 + col;

                domains[cell] &= ~initialValues;

                if (solution[j][col] != null){
                    int value = solution[j][col];
                    int bitValue = (1<<value-1);
                    //domains[cell] |= bitValue;        //add to existing bits, but there shouldnt be any so...
                    domains[cell] = bitValue;
                }

                /* if a domain shrinks to nothing we have an invalid solution, turn back now! */
                if (domains[cell] < 1) {
                    //System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
                    emptyDomainFlag = true;
                    break;
                }
            }
        }

        private void removeBoxDomainValues(int boxRow, int boxCol, int initialValues) {

            escape:

            for (int cellRow = boxRow; cellRow < boxRow+BOXSIZE; cellRow++) {
                for (int cellCol = boxCol; cellCol < boxCol+BOXSIZE; cellCol++) {

                    /* convert coords into numerical value of 81 to find the domain */
                    int cell = (cellRow * 9) + 1 + cellCol;

                    domains[cell] &= ~initialValues;

                    if (solution[cellRow][cellCol] != null){
                        int value = solution[cellRow][cellCol];
                        int bitValue = (1<<value-1);
                        //domains[cell] |= bitValue;        //add to existing bits, but there shouldnt be any so...
                        domains[cell] = bitValue;
                    }

                    /* if a domain shrinks to nothing we have an invalid solution, turn back now! */
                    if (domains[cell] < 1) {
                        //System.out.println("Empty Domain --->"+cell+" Domain:"+domain);
                        emptyDomainFlag = true;
                        break escape;       //breaks from all loops
                    }
                }
            }
        }

        /**
         * Forward Checks every row in the puzzle
         */
        private void fcAllRow() {

            for (int i = 0; i < GRIDSIZE_ROW; i++) {

                int initialValues = 0;
                /* Get all the values in the row */
                for (int j = 0; j < GRIDSIZE_COLUMN; j++) {
                    if (solution[i][j] != null) {
                        initialValues |= (1 << (solution[i][j] -1));
                    }
                }

                /* If there are values that need to be removed from domains remove them */
                if (initialValues != 0) {
                    removeRowDomainValues(i, initialValues);
                }
                /* if we have created an empty domain stop doing forward checking */
                if (emptyDomainFlag) {
                    break;
                }
            }
        }

        /**
         * Forward Checks every column in the puzzle
         */
        private void fcAllCol() {

            for (int i = 0; i < GRIDSIZE_COLUMN; i++) {

                int initialValues = 0;
                /* Get all the values in the column */
                for (int j = 0; j < GRIDSIZE_ROW; j++) {
                    if (solution[j][i] != null) {
                        initialValues |= (1 << (solution[i][j] -1));
                    }
                }
                /* If there are values that need to be removed from domains remove them */
                if (initialValues != 0) {
                    removeColDomainValues(i, initialValues);
                }

                /* if we have created an empty domain stop doing forward checking */
                if (emptyDomainFlag) {
                    break;
                }
            }
        }

        /**
         * Forward Checks every box in the puzzle
         */
        private void fcAllBox() {      

            int cellRow, cellCol;

            escape:
            /**
             * Loop through all the boxes Finds the top left square of each 3x3 box.
             */
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    int initialValues = 0;

                    /* loops through each cell in a 3x3 box */
                    for (int x = 0; x < BOXSIZE; x++) {
                        for (int y = 0; y < BOXSIZE; y++) {
                            cellRow = (3 * i) + x;
                            cellCol = (3 * j) + y;

                            if (solution[cellRow][cellCol] != null) {
                                //creates a binary number representing domains 
                                //| Bitwise inclusive operand adds the value to the initial values int
                                initialValues |= (1 << (solution[cellRow][cellCol] -1));
                            }
                        }
                    }

                    /* If there are values that need to be removed from domains remove them */
                    if (initialValues != 0) {
                        removeBoxDomainValues(i*3, j*3, initialValues);
                    }

                    /* if we have created an empty domain stop doing forward checking */
                    if (emptyDomainFlag) {
                        break escape;       //Break all loops
                    }
                }
            }
        }

        /**
         * Forward check just 1 row, determined by the @param currentCell.
         */
        private void fcRow(int[] currentCell) {
            int initialValues = 0;
            int currentValue = solution[currentCell[0]][currentCell[1]];
            if (solution[currentCell[0]][currentCell[1]] != null) {
                initialValues = (1<<(currentValue-1));
            }

            /* If there are values that need to be removed from domains remove them */
            if (initialValues != 0) {
                removeRowDomainValues(currentCell[0], initialValues);
            }
        }

        /**
         * Forward check just 1 column, determined by the @param currentCell.
         */
        private void fcCol(int[] currentCell) {
            int initialValues = 0;
            int currentValue = solution[currentCell[0]][currentCell[1]];
            if (solution[currentCell[0]][currentCell[1]] != null) {
                initialValues = (1<<(currentValue-1));
            }

            /* If there are values that need to be removed from domains remove them */
            if (initialValues != 0) {
                removeColDomainValues(currentCell[1], initialValues);
            }
        }

        private void fcBox(int[] currentCell) {
            int initialValues = 0;
            int currentValue = solution[currentCell[0]][currentCell[1]];

            /* Finds the top left square of the current 3x3 box. */
            int boxRow = currentCell[0] - (currentCell[0] % 3);
            int boxCol = currentCell[1] - (currentCell[1] % 3);


            if (solution[currentCell[0]][currentCell[1]] != null) {
                initialValues = (1<<(currentValue-1));
            }

            /* If there are values that need to be removed from domains remove them */
            if (initialValues != 0) {
                removeBoxDomainValues(boxRow, boxCol, initialValues);
            }

        }

        @Override
        public String getName() {
            return NAME;
        }

        @Override
        public void setSolution(Integer[][] userInputPuzzle) {
            this.solution = userInputPuzzle;
        }

    }

I will also be removing lots of dead code such as my stripchars method and the array deep copy (if I haven't already) and some others like isSolvable.

\$\endgroup\$
  • \$\begingroup\$ Thanks @bradleyking! I try run your code using the setSolution method with my inputPuzzle (null on empty values), but the algorithm not found a solution. You know what might be happening? \$\endgroup\$ – falvojr Apr 22 '16 at 21:06
  • 1
    \$\begingroup\$ Sorry @falvojr for the late response. I never put any null checking anywhere in the system so your null request will probably be crashing things left right and center. I would advise altering setSolution to something nice: @Override public void setSolution(Integer[][] userInputPuzzle) { if (userInputPuzzle != null){ this.solution = userInputPuzzle; } else{ DISPLAY METHOD OR SOMETHING TO SEND BACK TO INFORM USER! } \$\endgroup\$ – bradleykins Jun 10 '16 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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