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.