Courses/CS 460/Fall 2006/Sudoku solution in JaCoP
From CSWiki
[edit] Sample execution
The input to main() is a sequence of words on the command line. Each word is 9 characters long. If a character is a digit in the range 1 .. 9, it is taken as a fixed grid value. Otherwise, it is taken as an open grid square.
Input: (In this example, '0' is used as an unspecified square.)
010904080 403000105 080000020 300090008 000106000 900040001 050000030 807000906 060805010
Output
Initially . 1 . | 9 . 4 | . 8 . 4 . 3 | . . . | 1 . 5 . 8 . | . . . | . 2 . --------------------- 3 . . | . 9 . | . . 8 . . . | 1 . 6 | . . . 9 . . | . 4 . | . . 1 --------------------- . 5 . | . . . | . 3 . 8 . 7 | . . . | 9 . 6 . 6 . | 8 . 5 | . 1 . After consistency . 1 2 | 9 . 4 | . 8 . 4 9 3 | . . . | 1 . 5 . 8 . | . . . | . 2 9 --------------------- 3 . 1 | . 9 . | . 4 8 . . . | 1 . 6 | . 9 . 9 . . | . 4 . | . . 1 --------------------- 1 5 4 | . . 9 | 8 3 2 8 3 7 | 4 . . | 9 5 6 2 6 9 | 8 3 5 | . 1 . *** Number of decisions: 83 *** Search depth: 83 *** Backtracks: 1 Problem solved. After searchOne 6 1 2 | 9 5 4 | 3 8 7 4 9 3 | 2 8 7 | 1 6 5 7 8 5 | 6 1 3 | 4 2 9 --------------------- 3 7 1 | 5 9 2 | 6 4 8 5 4 8 | 1 7 6 | 2 9 3 9 2 6 | 3 4 8 | 5 7 1 --------------------- 1 5 4 | 7 6 9 | 8 3 2 8 3 7 | 4 2 1 | 9 5 6 2 6 9 | 8 3 5 | 7 1 4 *** Execution time: 31 ms + 31 ms = 62 ms
[edit] Code
package examples;
import java.util.ArrayList;
import JaCoP.*;
/*
Conceptis Easy
010904080
403000105
080000020
300090008
000106000
900040001
050000030
807000906
060805010
Conceptis Very Hard
600010500
803000000
000060020
030108090
100090004
050203010
070030000
000000306
004050009
Paul's pages outlaw
000008700
005090020
001030006
004000050
090007080
060001300
200040900
030060400
009100000
Paul's pages outlaw
004700200
090080001
050000000
300600700
200000008
001040009
000000050
600030040
007008300
*/
public class Sudoku {
/**
* This artificial class is needed so that we can declare the subgrids
* as FDVList[][]. We want subgrids to be a 3x3 array of ArrayLists.
* (Don't want a 3x3 array of FDV[] since we will have trouble
* figuring out where we are in each array.)
* So we want to write something like this.
* ArrayList<FDV>[][] subgrids = new ArrayList<FDV>[sqrtOrder][sqrtOrder];
* But that isn't allowed. See
* http://java.sun.com/docs/books/tutorial/extra/generics/fineprint.html
* We could write
* ArrayList<?>[][] subgrids = new ArrayList<?>[sqrtOrder][sqrtOrder];
* But then to do something like
* subgrids[i/3][j/3].add(fdv)
* we must cast it as follows
* ((ArrayList<FDV>)subgrids[i/3][j/3]).add(fdv)
* and include: @SuppressWarnings("unchecked")
* This is required since ArrayList<?> is an ArrayList of
* unspecified type, which can't have elements added to it.
* So we are making subgrids a 3x3 array of FDVList.
* Hence the need for the class FDVList.
* It must be declared static so that it can be referred to statically.
*/
static class FDVList extends ArrayList<FDV> {
private static final long serialVersionUID = 1L;
}
static FDstore store = new FDstore();
public static void main(String[] args) {
FDV[][] grid = readInputsAndImposeConstraints(args);
printGrid("Initially", grid);
long t1 = System.currentTimeMillis();
Solver.consistency(store);
long t2 = System.currentTimeMillis() - t1;
printGrid("After consistency", grid);
long t3 = System.currentTimeMillis();
boolean result =
Solver.searchOne(store, store, new SearchOne(), new IndomainMin(),
new Delete(new MostConstrainedDynamic()));
long t4 = System.currentTimeMillis() - t3;
System.out.println("\nProblem " + (result? "" : "not ") + "solved.");
printGrid("\nAfter searchOne", grid);
System.out.println("*** Execution time: " +
t2 + " ms + " + t4 + " ms = " + (t2 + t4) + " ms");
}
/**
* Create the grid of FDVs and put them in the rows, coluumns, and subgrids arrays
* @param args input fixed values
* @param rows
* @param columns
* @param subgrids
*/
private static void createFDVs(String[] args, FDV[][] rows, FDV[][] columns, FDVList[][] subgrids) {
int order = args.length;
for (int i = 0; i < order; i++) {
for (int j = 0; j < order; j++) {
char c = args[i].charAt(j);
int min = 1;
int max = 9;
if (Character.isDigit(c) && c != '0') {
min = max = Character.getNumericValue(c);
}
FDV fdv = new FDV(store, i + "-" + j, min, max);
columns[j][i] = rows[i][j] = fdv;
subgrids[i/3][j/3].add(fdv);
}
}
}
private static void imposeConstraints(FDV[][] rows, FDV[][] columns, FDVList[][] subgrids) {
int order = rows.length;
// Impose constraints on rows and columns
for (int k = 0; k < order; k++) {
store.impose(new Alldiff(rows[k]));
store.impose(new Alldiff(columns[k]));
}
// Impose constraints on subgrids
int sqrtOrder = (int) Math.sqrt(order);
for (int k1 = 0; k1 < sqrtOrder; k1++) {
for (int k2 = 0; k2 < sqrtOrder; k2++) {
store.impose(new Alldiff(subgrids[k1][k2]));
}
}
}
private static void printGrid(String label, FDV[][] grid) {
System.out.println(label);
int i = 0;
for (FDV[] line: grid) {
int j = 0;
for (FDV fdv: line) {
System.out.print(" " + (fdv.singleton() ? fdv.value() : "."));
if (j++%3 == 2 && j < 8) System.out.print(" |");
}
System.out.println();
if (i++%3 == 2 && i < 8) {
System.out.print(" ");
for (int k = 0; k < 7; k++) System.out.print("---");
System.out.println();
}
}
System.out.println();
}
/**
* Read the input array, create the grid of FDVs, and impose
* the constraints: all rows are distinct; all columns are distinct;
* all subgrids are distinct.
* @param args the input fixed values
* @return the grid
*/
private static FDV[][] readInputsAndImposeConstraints(String[] args) {
int order = args.length;
FDV[][] rows = new FDV[order][order];
FDV[][] columns = new FDV[order][order];
int sqrtOrder = (int) Math.sqrt(order);
// A 3x3 array of ArrayList<FDV>, one for each subgrid.
FDVList[][] subgrids = new FDVList[sqrtOrder][sqrtOrder];
for (int k1 = 0; k1 < sqrtOrder; k1++)
for (int k2 = 0; k2 < sqrtOrder; k2++)
subgrids[k1][k2] = new FDVList();
createFDVs(args, rows, columns, subgrids);
imposeConstraints(rows, columns, subgrids);
return rows;
}
}
