【舌尖上的演算法】Day30 -- Algorithm X and Sudoku

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Hank Lee
 * Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
 */
public class MatrixUtils {
	
public static Map<String, List<String>> combinations = new HashMap<>();
    
	/**
	 * The generation methods to prepare matrix
	 * @param size the size of sudoku. For example, a 4x4 sudoku grid will give "4".
	 * @param sqrt the sqrt of the size of sudoku. For example, a 4x4 sudoku grid will give "2".
	 * @param symbols the symbols used in grid
	 * @param numberOfConstraints the number of constraints
	 * @param cages the cages for killer sudoku
	 * @return matrixes
	 */
    public static List<Matrix> generateMatrix(Integer size, Integer sqrt, Integer[] symbols, int numberOfConstraints) {

		// Prepare to matrix
    	List<Matrix> matrixs = null;
    	matrixs = new ArrayList<>();
		for (int row = 0; row < size; row++) {
			for (int col = 0; col < size; col++) {
				for (int value : symbols) {
					Integer[] constraints = new Integer[size*size*numberOfConstraints];
					
					// One value constraint: 
					// constraint number : row x size + col
					constraints[row * size + col] = 1;
					
					// Row constraint:
					// constraint number : size^2 + row x size + value - 1
					constraints[((int) Math.pow(size,2)) + row * size + value - 1] = 1;
					
					// Column constraint:
					// constraint number : 2 x size^2 + col x size + value - 1
					constraints[2 * ((int) Math.pow(size,2)) + col * size + value - 1] = 1;
					
					// Box constraint:
					// constraint number : 3 x size^2 + (row / sqrt) x size x sqrt + (col / sqrt) x size + value - 1
					constraints[3 * ((int) Math.pow(size,2)) + (row / sqrt) * size * sqrt + (col / sqrt) * size + value - 1] = 1;
					
					matrixs.add(new Matrix(row, col, value, constraints));
					
				}
			}
		}
	
		
		// To print the matrix
//		printMatrix(matrixs, size);
		return matrixs;
    }
    
    
    /**
     * To print the matrix in the console
     * 
     * @param matrixes the matrix
     * @param size the size of sudoku. For example, a 4x4 sudoku grid will give "4".
     */
    public static void printMatrix(List<Matrix> matrixes, int size) {
    	//1,1,1 | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c | c c c c c c c c c c c c c c c c 
		System.out.println("r,c,v | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c");
		System.out.println("-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------");
		
		for (Matrix m : matrixes) {
			System.out.print(m.row+","+m.col+","+m.value+" | ");
			for (int i = 0; i < m.constraints.length; i++) {
				if (i != 0 && i % (size*size) == 0)
					System.out.print("| ");
				Integer val = m.constraints[i];
				System.out.print((val == null ? " ":m.constraints[i])+" ");
			}
			System.out.println();
			if (m.value % size == 0)
				System.out.println("-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------");
		}
    	
    }

}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Algorithm X solver for standard Sudoku.
 * @author Hank Lee
 * Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
 */
public class AlgorXSolver {
	// prepare the object to store matrix, partial solutions and the columns deleted
	List<Matrix> matrixes = null;
	List<Matrix> solutions = new ArrayList<>();
	List<Integer> deletedColumns = new ArrayList<>();
	Integer size = null;

	public AlgorXSolver() {
	} // end of AlgorXSolver()

	/**
	 * The public solve method for other programs to call
	 */
	public boolean solve(SudokuGrid sudokuGrid) {

		int numConstraints = 4;

		// if the matrix is empty, it need to be generated by the size of sudoku grid
		// and symbols and the number of constraints.
		if (matrixes == null)
			matrixes = MatrixUtils.generateMatrix(sudokuGrid.size, sudokuGrid.sqrt, sudokuGrid.symbols, numConstraints);

		// As some cells have been inserted value,
		// we need to get rid of those rows and columns related to them in the matrix
		removeRowsByGrid(sudokuGrid);

		// the total number of constraints need to be satisfied in the matrix
		size = sudokuGrid.size * sudokuGrid.size * numConstraints;

		// call the private solve method to find the solution of the standard sudoku
		if (solve(matrixes, deletedColumns)) {
			// After finding the solutions,
			// add the value to each cell of the standard sudoku grind.
			for (Matrix matrix : solutions) {
				sudokuGrid.grid[matrix.row][matrix.col] = matrix.value;
			}
			return true;
		}

		return false;
	} // end of solve()

	/**
	 * The exact method to solve standard sudoku problem
	 * 
	 * @param matrixes       the matrixes to analyse
	 * @param deletedColumns those deleted columns of constraints in matrix
	 * @return the problem is solved or not.
	 */
	@SuppressWarnings("unchecked")
	private Boolean solve(List<Matrix> matrixes, List<Integer> deletedColumns) {

		// If Matrix is empty, the problem is solved; terminate successfully.
		if (matrixes.size() == 0) {
			return true;
		}

		// Find the minimize sum of column constraints in the current matrix
		// and get the matrixes of potential solution
		Map<String, Object> minMap = findMinSumByColumn(matrixes, deletedColumns);
		List<Matrix> potentialSols = (List<Matrix>) minMap.get("potentialSols");

		// If the index is null, it means that it cannot find a solution based on the
		// current situation.
		if (minMap.get("idx") == null) {
			return false;
		}

		// If the min value is 0, then the size of potential solution will be 0,
		// which means the process is terminated unsuccessfully.
		if (potentialSols.size() == 0) {
			return false;
		}

		// To store the current matrix and deleted columns for backtracking recovery
		List<Matrix> tempmatrixes = new ArrayList<>();
		tempmatrixes.addAll(matrixes);
		List<Integer> tempDeletedColumns = new ArrayList<>();
		tempDeletedColumns.addAll(deletedColumns);

		for (Matrix matrix : potentialSols) {
			// add the partial solutions
			solutions.add(matrix);

			// find which columns should be deleted
			for (int i = 0; i < matrix.constraints.length; i++) {
				if (matrix.constraints[i] != null && matrix.constraints[i] == 1) {
					deletedColumns.add(i);
				}
			}

			// remove matrix based on the deleted columns
			for (Integer i : deletedColumns) {
				// delete row by idx
				matrixes.removeIf(x -> x.constraints[i] != null);
			}

			// Use the modified matrix to find partial solutions recursively.
			if (solve(matrixes, deletedColumns)) {
				return true;

				// if it returns false, it means that the partial solution is wrong,
				// and the process need to be recovered to the previous state, which is
				// backtracking.
			} else {
				solutions.remove(matrix);
				matrixes.removeAll(matrixes);
				matrixes.addAll(tempmatrixes);
				deletedColumns.removeAll(deletedColumns);
				deletedColumns.addAll(tempDeletedColumns);
			}
		}

		return false;
	}

	/**
	 * The method is used to find the minimize sum of columns in the current matrix
	 * and based on the column, prepare to matrixes which are potential solutions.
	 * 
	 * @param matrixes       the current matrix
	 * @param deletedColumns the column deleted
	 * @return
	 */
	private Map<String, Object> findMinSumByColumn(List<Matrix> matrixes, List<Integer> deletedColumns) {

		Integer[] sum = new Integer[size];
		Integer min = null;
		Integer idx = null;

		for (Matrix m : matrixes) {
			for (int i = 0; i < size; i++) {
				if (m.constraints[i] != null) {
					if (sum[i] == null)
						sum[i] = 0;
					sum[i] = sum[i] + m.constraints[i];
				}
			}
		}

		for (int i = 0; i < size; i++) {
			// if the index of column can be found in the list of deleted columns
			// it means that the column should be skipped.
			if (deletedColumns.contains(i)) {
				continue;
			}
			if (sum[i] == null) {
				idx = i;
				break;
			}
			if (min == null || min > sum[i]) {
				min = sum[i];
				idx = i;
			}
		}

		List<Matrix> potentialSols = new ArrayList<>();

		if (min != null) {
			for (Matrix m : matrixes) {
				if (m.constraints[idx] != null) {
					potentialSols.add(m);
				}
			}
		}

		Map<String, Object> minMap = new HashMap<>();
		minMap.put("potentialSols", potentialSols);
		minMap.put("idx", idx);

		assert (idx == null);

		return minMap;
	}

	/**
	 * Remove the rows and columns if the cell contains a value
	 * 
	 * @param sudokuGrid the sudoku grid
	 */
	private void removeRowsByGrid(SudokuGrid sudokuGrid) {

		for (int i = 0; i < sudokuGrid.size; i++) {
			for (int j = 0; j < sudokuGrid.size; j++) {
				if (sudokuGrid.grid[i][j] != null) {
					// delete row by idx
					for (Matrix m : matrixes) {
						if (m.row == i && m.col == j && m.value == sudokuGrid.grid[i][j]) {
							matrixes.remove(m);

							for (int k = 0; k < m.constraints.length; k++) {
								if (m.constraints[k] != null && m.constraints[k] == 1) {
									deletedColumns.add(k);
								}
							}

							for (Integer n : deletedColumns) {
								// delete row by idx
								matrixes.removeIf(x -> x.constraints[n] != null);
							}

							break;
						}
					}
				}
			}
		}
	}

}

/**
 * @author Hank Lee
 * Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
 *
 */
public class SudokuGrid {
	
	public Integer size = 0;
	public Integer[] symbols = null;
	public Integer[][] grid = null;
	public Integer sqrt = 0;
	
	public boolean validate() {
    	
    	for (int currentY = 0; currentY < size; currentY++) {
    		for (int currentX = 0; currentX < size; currentX++) {
    			int currentNumber = grid[currentY][currentX];
    			if (!this.basicValidate(this, currentNumber, currentX, currentY))
    				return false;
    		}
    	}
		
		return true;
    }

	
	/**
	 * To do the basic validation of sudoku grid.
	 * In the method, it only checks basic 3 constraints, 
	 * which are box-value constraints, row-value constraints and column-value constraints
	 * 
	 * @param sudokuGrid the sudoku grid
	 * @param currentNumber the current number to check
	 * @param currentX the current column of the cell
	 * @param currentY the current row of the cell
	 * @return true: valid, false: invalid
	 */
	public boolean basicValidate(SudokuGrid sudokuGrid, int currentNumber, int currentX, int currentY) {
		

		// compare each number in one row
		for (int x = 0; x < sudokuGrid.size; x++) {
			if (currentX != x && sudokuGrid.grid[currentY][x] != null && currentNumber == sudokuGrid.grid[currentY][x])
				return false;
		}
		
		// compare each number in one column
		for (int y = 0; y < sudokuGrid.size; y++) {
			if (currentY != y && sudokuGrid.grid[y][currentX] != null && currentNumber == sudokuGrid.grid[y][currentX])
				return false;
		}
		
		// compare each number in one sub-grid
		int modX = currentX / sudokuGrid.sqrt;
		int modY = currentY / sudokuGrid.sqrt;
		
		for (int y = (modY*sudokuGrid.sqrt); y<((modY+1)*sudokuGrid.sqrt); y++) {
			for (int x = (modX*sudokuGrid.sqrt); x<((modX+1)*sudokuGrid.sqrt); x++) {
				if (currentX != x && currentY != y && sudokuGrid.grid[y][x] != null && sudokuGrid.grid[y][x] == currentNumber)
					return false;
			}
		}
		
		return true;
		
	}
}