Constraint Programming Part III - Sudoku

Sudoku is a puzzle with the objective to fill number 1 to 9 into 9x9 table, with the constraints that, each row, each column, and each 3x3 block, cannot contain duplicated members.


(image from wikipedia)

Source for Sudoku class you can download from here. The source of Sudoku table is array of integer, named "table".

int[] table

The size of array is 81, index 0-8 represents each cell in the first row, 9-17 for the second row, and so on. Following functions are to convert index to row, column, and grid number.

static int getRow(int x) {
    return x / 9;
}
static int getCol(int x) {
    return x % 9;
}
static int getGrid(int x) {
    return (getRow(x) / 3) * 3 + (getCol(x) / 3);
}

And this function is to test whether 2 input arguments are in the same row, or column or grid.

static bool Conflict(int x, int y) {
    return (getRow(x) == getRow(y)) ||
           (getCol(x) == getCol(y)) ||
           (getGrid(x) == getGrid(y));
}

Before start constraint programming, extract the known positions, and known values from Sudoku table.

int[] position = 0.To(80).OrderByDescending(x => table[x] > 0).ToArray();
int[] valued = table.Where(x => x > 0).ToArray();

Position is array of index of known values. All known value indexes will move to the front. This will make arranger class processes known values before unknown value. And now start constraint programming.

var solutions = 1.To(9).Arrange(81);

This is instantiation of arrager class to arrange 1-9 for the size of 81. And next append the constraint.

solutions.AppendConstraint(set => set.Length < valued.Length,
    set => cell => cell == valued[set.Length]
);

This AppendConstraint command is different from AppendConstraint command in previous post. This AppendConstraint command takes 2 arguments. First argument is argument to condition when the constraint should be applied. Second argument is constraint body. Above command can be translated that, when number of members in set less than number of known value, new member value must equal to known value. And next is constraint for Sudoku.

solutions.AppendConstraint(set => set.Length >= valued.Length,
    set => cell => !set.Any((x, i) => x == cell && Conflict(position[i], position[set.Length]))
);

Above command can be translated that, when number of members greater than or equal to number of known values, new member cannot make any both duplicated in value and conflict in position.

Now the command is completed. Next is to rearrange index into normal position.

var solution = solutions.FirstOrDefault();
if (solution == null)
    return null;
int idx = 0;
return new Sudoku(solution.OrderBy(x => position[idx++]).ToArray());

Test the class.

int[] table = { 5, 3, 0, 0, 7, 0, 0, 0, 0,
                6, 0, 0, 1, 9, 5, 0, 0, 0,
                0, 9, 8, 0, 0, 0, 0, 6, 0,
                8, 0, 0, 0, 6, 0, 0, 0, 3,
                4, 0, 0, 8, 0, 3, 0, 0, 1,
                7, 0, 0, 0, 2, 0, 0, 0, 6,
                0, 6, 0, 0, 0, 0, 2, 8, 0,
                0, 0, 0, 4, 1, 9, 0, 0, 5,
                0, 0, 0, 0, 8, 0, 0, 7, 9};
Console.WriteLine(new Sudoku(table).ToSolvedSudoku());

//5, 3, 4, 6, 7, 8, 9, 1, 2
//6, 7, 2, 1, 9, 5, 3, 4, 8
//1, 9, 8, 3, 4, 2, 5, 6, 7
//8, 5, 9, 7, 6, 1, 4, 2, 3
//4, 2, 6, 8, 5, 3, 7, 9, 1
//7, 1, 3, 9, 2, 4, 8, 5, 6
//9, 6, 1, 5, 3, 7, 2, 8, 4
//2, 8, 7, 4, 1, 9, 6, 3, 5
//3, 4, 5, 2, 8, 6, 1, 7, 9

The Sudoku is now solve! Next we will do constraint programming using only LinQ.