// (c) 2026-2026 Fair Isaac Corporation
import java.util.Arrays;
import java.util.Collection;
import com.dashoptimization.ColumnType;
import com.dashoptimization.DefaultMessageListener;
import com.dashoptimization.maps.HashMap3;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;
import static com.dashoptimization.objects.Utils.sum;
/** 9x9 Sudoku puzzle to illustrate solution enumeration.
* This is a pure feasibility problem, i.e., the objective function is all-zero.
* We first solve with prefixed values that allow exactly one solution. Then
* we add clear one of the fixings and enumerate all solutions the new board
* allows.
*/
public final class Sudoku {
/** The available row indices (first row has index zero). */
private static final Collection<Integer> ROWS = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8);
/** The available column indices (first column has index zero). */
private static final Collection<Integer> COLS = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8);
/** The available values (1 through 9). */
private static final Collection<Integer> VALS = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
/** Values that are fixed in the beginning.
* These fixings allow exactly one feasible solution.
* Data set from "The Guardian", 15 July, 2005. http://www.guardian.co.uk/sudoku
*/
private static final int[][] PRESET = {
{ 0, 0, 0, 7, 0, 5, 6, 9, 0 },
{ 0, 0, 8, 0, 4, 0, 0, 0, 7 },
{ 0, 2, 0, 0, 0, 3, 0, 0, 0 },
{ 0, 0, 2, 0, 0, 0, 9, 0, 0 },
{ 0, 0, 0, 9, 0, 0, 0, 8, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 5 },
{ 0, 0, 0, 0, 0, 4, 0, 0, 0 },
{ 0, 0, 6, 0, 0, 0, 3, 0, 4 },
{ 0, 0, 0, 8, 2, 1, 0, 5, 0 },
};
/** Solve the 9x9 Sudoku puzzle with the given fixed values.
* @param fixed The values that are fixed on the board.
* @param enumerate If <code>true</code> then we enumerate all solutions,
* otherwise we stop on the first solution. Note that
* enumeration can become expensive the more solutions
* there are.
*/
private static void solve(int[][] fixed, boolean enumerate) {
try (XpressProblem prob = new XpressProblem()) {
// Create the variables. One binary variable for each combination of
// row, column, value.
// We store the variables in a map rather than a 3D array since rows and
// columns index from 0, but values index from 1.
HashMap3<Integer,Integer,Integer,Variable> b = prob.addVariables(ROWS, COLS, VALS)
.withName("b(%d,%d,%d)")
.withType(ColumnType.Binary)
.toMap();
// Fix the variables that should be fixed on the initial board.
for (int r : ROWS) {
for (int c : COLS) {
if (fixed[r][c] > 0) {
b.get(r, c, fixed[r][c]).fix(1.0);
}
}
}
// Each cell must have a number.
prob.addConstraints(ROWS, COLS, (r, c) -> sum(VALS, v -> b.get(r, c, v)).eq(1.0));
// Each number must appear exactly once in a row.
prob.addConstraints(ROWS, VALS, (r,v) -> sum(COLS, c -> b.get(r, c, v)).eq(1.0));
// Each number must appear exactly once in a column.
prob.addConstraints(COLS, VALS, (c,v) -> sum(ROWS, r -> b.get(r, c, v)).eq(1.0));
// In 3x3 squares all values must be different.
for (int k = 0; k < 3; ++k) {
Collection<Integer> colidx = Arrays.asList(3 * k, 1 + 3 * k, 2 + 3 * k);
for (int v : VALS) {
prob.addConstraint(sum(Arrays.asList(0, 1, 2), colidx,
(x, y) -> b.get(x, y, v)).eq(1.0));
prob.addConstraint(sum(Arrays.asList(3, 4, 5), colidx,
(x, y) -> b.get(x, y, v)).eq(1.0));
prob.addConstraint(sum(Arrays.asList(6, 7, 8), colidx,
(x, y) -> b.get(x, y, v)).eq(1.0));
}
}
// Enable log output and prepare for numeration (if requested).
prob.callbacks.addMessageCallback(DefaultMessageListener::console);
if (enumerate) {
prob.controls().setPoolEnumStrategy(com.dashoptimization.XPRSenumerations.PoolEnumStrategy.FULL);
prob.controls().setPoolLimit(Integer.MAX_VALUE); // Find all solutions.
}
// Find all solutions.
prob.optimize();
// Print solutions.
// Note that we only print the first 10 solutions to not flood the screen.
for (int s = 0; s < Math.min(10, prob.attributes().getPoolSize()); ++s) {
System.out.println("Solution " + s + ":");
printSolution(b, prob.getPoolSolution(s));
}
}
}
/** Print a board to the console.
* @param board A 9x9 array that specifies the numbers that are set in
* board. A zero means "not set".
*/
private static void printBoard(int[][] board) {
for (int r = 0; r < board.length; ++r) {
String fill = (r == 3 || r == 6) ? "===+" : "---+";
System.out.print("+");
for (int c = 0; c < board[r].length; ++c) {
System.out.print(fill);
if (c == 2 || c == 5)
System.out.print('+');
}
System.out.println();
System.out.print("|");
for (int c = 0; c < board[r].length; ++c) {
System.out.printf(" %c |", (board[r][c] == 0) ? ' ' : (char)(board[r][c] + '0'));
if (c == 2 || c == 5)
System.out.print('|');
}
System.out.println();
}
System.out.print("+");
for (int c = 0; c < board[0].length; ++c) {
System.out.print("---+");
if (c == 2 || c == 5)
System.out.print('+');
}
System.out.println();
}
/** Print a soolution.
* Constructs a board from a solution and then prints it.
* @param b The binary variables.
* @param sol The solution values for <code>b</code>.
*/
private static void printSolution(HashMap3<Integer,Integer,Integer,Variable> b, double[] sol) {
int[][] result = new int[9][9];
for (int r : ROWS) {
for (int c : COLS) {
for (int v : VALS) {
if (b.get(r, c, v).getValue(sol) > 0.5) {
result[r][c] = v;
}
}
}
}
printBoard(result);
}
public static void main(String[] args) {
// First solve with the preset board. This should allow exactly one solution.
solve(PRESET, false);
// Now remove some fixed values and enumerate all solutions.
PRESET[0][3] = 0;
solve(PRESET, true);
}
}
|
