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.

Constraint Programming Part II - 8 Queens Puzzle

To download class used in this article, download Arranger class. Please note that, Arranger class is also use code in Extension methods for delegate types article.

After put the classes into your project, create more extension methods.

public static Arranger<T, T[]> Arrange<T>(this IEnumerable<T> source, int length) {
    return new Arranger<T, T[]>(source, new T[0],
        (current, item, i) => current.Append(item),
        current => current.Length == length);
}
public static Arranger<T1, T2> Arrange<T1, T2>(this IEnumerable<T1> source, T2 seed, Func<T2, T1, int, T2> func, Func<T2, bool> yield) {
    return new Arranger<T1, T2>(source, seed, func, yield);
}

Basic use of this class is easy, you can write just one line of code.

"ABC".Arrange(2).ForEach(x => Console.WriteLine(x.ListMembers()));
//A A
//A B
//A C
//B A
//B B
//B C
//C A
//C B
//C C

As result, the class generates all possible solutions to arrange A, B and C with length of 2. We can call this arrangement as PermutationWithRepetition. This model is suited with problems that each member's position is matter and each member can be duplicated to each other. Example of this model is English word. The word "Hello", letter H - e - l - l - o were chosen. Position is matter because if we change to "Helol", the word is changed to be meaningless. PermutationWithRepetition is the default model.

Now try next model, Permutation. We can set model from the property ArrangementModel.

var solutions = "ABC".Arrange(2);
solutions.ArrangementModel = ArrangementModel.Permutation;
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A B
//A C
//B A
//B C
//C A
//C B

You can see that duplicated members are eliminated. Permutation is suited with problems that position is matter and each member cannot appear twice. Example is playing jigsaw puzzle. Position is important to build every piece of jigsaw to be a picture. But you cannot use a piece of jigsaw twice.

Next model CombinationWithRepetition

var solutions = "ABC".Arrange(2);
solutions.ArrangementModel = ArrangementModel.CombinationWithRepetition;
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A A
//A B
//A C
//B B
//B C
//C C

When compare with PermutationWithRepetition, CombinationWithRepetition show only distinct result. This model is suited with problems that position is not matter, and each member can be duplicated. Example is changing for money. You can change 50 cents, 25 cents and 25 cents for 1 dollars. Position is not matter {50c, 25c, 25c} is equal to {25c, 25c, 50c}.

Last model, Combination

var solutions = "ABC".Arrange(2);
solutions.ArrangementModel = ArrangementModel.Combination;
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A B
//A C
//B C

When compare with CombinationWithRepetition, duplicated members is eliminated. This model is suited with problems that position is not matter, and each member cannot appear twice. Example is playing cards. You may get card Ace of clubs and Jack clubs. Position is not matter, {A club, J club} is equal to {J club, A club}. And you cannot have the same card in a hand.

Beside models, you can append constraint to the arranger.

var solutions = "ABC".Arrange(2);
solutions.AppendConstraint(set => c => c != 'B');
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A A
//A C
//C A
//C C

AppendConstraint limits the options while arranger chooses each member. You may notice that the function pass into AppendConstraint has 2 lambda operator (=>). It is partial function application. "Set" argument is set of members that arranger has already chosen, "c" argument is member to be chosen. Example above, the solution has a constraint that member to be chosen cannot be B. Therefore, there is no B in the results.

With ArrangementModel and AppendConstraint, now we can construct 8 queens puzzle solutions.

var sol = 0.To(7).Arrange(8);
sol.ArrangementModel = ArrangementModel.Permutation;
sol.AppendConstraint(set => q =>
    set.All((x, i) => (set.Length - i != Math.Abs(x - q)))
);

0.To(7) is input source represents column index 0 (A) to column index 7 (H) to put a queen. Arrange(8) is to create solutions of 8 queens. ArrangementModel.Permutation means each queens cannot be in the same column index. And AppendConstraint limits that the new queen cannot put diagonal to queens that already in the set.

With just 3 statements, code is finished. Now output the results.

Console.WriteLine("  A B C D E F G H");
sol.First().ForEach((q, i) =>
    Console.WriteLine("{0} " + "_ ".Repeat(q) + "Q " + "_ ".Repeat(7 - q), i + 1)
);
Console.WriteLine();
Console.WriteLine("Total solutions: {0}", sol.Count());
//  A B C D E F G H
//1 Q _ _ _ _ _ _ _
//2 _ _ _ _ Q _ _ _
//3 _ _ _ _ _ _ _ Q
//4 _ _ _ _ _ Q _ _
//5 _ _ Q _ _ _ _ _
//6 _ _ _ _ _ _ Q _
//7 _ Q _ _ _ _ _ _
//8 _ _ _ Q _ _ _ _
//
//Total solutions: 92

Next post, solve harder problem which is Sudoku.

Constraint Programming Part I - Introduction

Constraint programming is programming for searching the solutions by specifying the constraints of a problem, and then generating the satisfied solutions. Constraint programming is unlike Brute-force search, which Brute-force generates all possible solutions and then tests all solutions for the answer. Constraint programming can reduce a huge time to search by discarding large set of unsatisfied solutions.

A solution is a combination set of finite domains. And a satisfied solution is the solution that satisfies all constraints. For instance, in Sudoku, a solution is a set of 1 to 9 with size of 9 rows and 9 columns. Satisfied solutions are values of all cells in each column, each row, and each 3 x 3 grid must be unique.

Constraint programming can solve solutions by "guess-and-check", this can be done by technics called backtracking and local consistency.

BackTracking is recursive algorithm to guess a value, and check if the value is satisfied the constraints. If the value is satisfied, it will recurse and guess a value for next item. The recursion will be done until solution is valid. If no solution is valid, it will rollback and guess next value, and continue searching for valid solutions again.

Local consistency is algorithm to cut off number of items in a domain. This will reduce time and space to search. Moreover, local consistency is also checker for satisfied solutions.

For instance, for 4-queens problem, you have to place 4 queens on 4 x 4 board, with the constraint that all 4 queens must not eat each other. In this problem, there are 4 variables, which are queens for row 1, 2, 3, 4. And there are 4 items in a finite domain, which are column A, B, C, D. And there are 2 constraints, all queens cannot be in the same column, and all queens cannot place diagonally to previous queens.

To start, constraint programming will pick value for the first queen, which is column A.

  A B C D
1 Q . . .
2 . . _ _
3 . _ . _
4 . _ _ .

With local consistency, it enforces that in second row, you cannot place queen on column A and B. In third row, you cannot place queen on column A and C, and for forth row, you cannot place queen on column A and D.

Next, constraint programming will pick value for the second queen, which is column C.

  A B C D
1 Q . . .
2 . . Q .
3 . . . .
4 . _ . .

You can see that, when we place second queen on column C, we cannot continue place queen on third row. Therefore, the solution is failed. Constraint programming will backtrack and try pick next value for the second queen, which is column D.

  A B C D
1 Q . . .
2 . . . Q
3 . _ . .
4 . . _ .

Next, for the third queen.

  A B C D
1 Q . . .
2 . . . Q
3 . Q . .
4 . . . .

Again, we cannot continue place queen for the forth row. Constraint programming will backtrack. The third row has only one option. Backtracking will perform again to the second row, unfortunately, second row used all available options. Then, we have to backtrack to the first row. Next value for the first row is column B.

  A B C D
1 . Q . .
2 . . . _
3 _ . _ .
4 _ . _ _

Next, for second row.

  A B C D
1 . Q . .
2 . . . Q
3 _ . . .
4 _ . _ .

Next, for third row.

  A B C D
1 . Q . .
2 . . . Q
3 Q . . .
4 . . _ .

Next, for the last row.

  A B C D
1 . Q . .
2 . . . Q
3 Q . . .
4 . . Q .

No conflict, solution is completed! Constraint programming can continue find whether there are any other solutions.

Next, we will start programming, and solve 8 queens problem.