C# Constraint Puzzle Solver

Implement a constraint solver to find all possible solutions to a numeric puzzle with logic rules. Use recursion.

Constraint puzzle. You find yourself on a mysterious island. After a few days you find a large house where a rich man lives. The calm sea is near.

One day the rich man shows you a puzzle. It is a puzzle of constraints. On it, each number must be less than its left neighbor. Each must be greater than the one above it.

Next: You are handed a small piece of paper. Here are the rules. Just 3 numbers are already filled in on the puzzle.

Constraint rules: 1. Each cell is less than its left neighbor. 2. Each cell is greater than its top neighbor. 3. All numbers are integers. 4. All numbers are 0 or greater. 5. All cells must have a number. Puzzle: 100 ? ? ? ? ? 120 5 ? Count all possible arrangements.

A puzzle approach. We must fill in the missing numbers will all possibilities. We can use a constraint solver (a recursive algorithm) to find (and count) all solutions to the puzzle.

HashedSolutions: We place each result (and partial result) in this hash. This avoids repeating work.

HashSet

GlobalMax: Finds the largest integer in any square. We use this an upper bound (no number we add may exceed this max).

GetAsPosition: Get a value at a pair of coordinates. This searches through our List of Tuples.

List Tuple

GetString: Convert the data we have added to a string so it can be hashed and printed more easily (this is slow).

AddItem: Try to add a number to a square. This tests all 4 constraints before it allows a number to be added. This is recursive.

C# program that uses constraint solver using System; using System.Collections.Generic; using System.Text; class Program { // Place all solutions in a dictionary. // ... This avoids duplicates. static HashSet<string> _hashedSolutions = new HashSet<string>(); static int _hashedSolutionsFinals = 0; static int GlobalMax(List<Tuple<int, int, int>> data) { // Get the highest number from the data. int max = -1; for (int i = 0; i < data.Count; i++) { if (data[i].Item1 > max) { max = data[i].Item1; } } return max; } static int GetAtPosition(List<Tuple<int, int, int>> data, int x, int y) { // Get value as this position. for (int i = 0; i < data.Count; i++) { if (data[i].Item2 == x && data[i].Item3 == y) { return data[i].Item1; } } return -1; } static string GetString(List<Tuple<int, int, int>> data, int width, int height) { // Convert our tuples to a string. // ... This is displayed like a 2D array. StringBuilder builder = new StringBuilder(); for (int i = 0; i < width; i++) { for (int y = 0; y < height; y++) { int value = GetAtPosition(data, y, i); builder.Append(value.ToString().PadLeft(3)); builder.Append(' '); } builder.AppendLine(); } return builder.ToString(); } static void AddItem(List<Tuple<int, int, int>> data, int width, int height, int globalMax) { // Convert our data to a string. string text = GetString(data, width, height); // If this data has already been encountered, do nothing further. if (_hashedSolutions.Contains(text)) { return; } // Record this data as having been encountered. _hashedSolutions.Add(text); // See if we have all required values. if (data.Count == width * height) { // We are done. Console.WriteLine($"::RESULT {++_hashedSolutionsFinals}::"); Console.Write(text); return; } // Loop over all squares. for (int i = 0; i < width; i++) { for (int y = 0; y < height; y++) { // Get current value. int currentValueHere = GetAtPosition(data, i, y); // See if this square is empty. if (currentValueHere == -1) { // Try all possible numbers. // ... Never go beyond the global max. for (int test = 0; test < globalMax; test++) { // Constraint 1. // ... Must be larger than all squares above it. bool invalid = false; foreach (var listItem in data) { if (listItem.Item2 == i && // Same column. listItem.Item3 < y && // Higher. listItem.Item1 >= test) { invalid = true; break; } } // Constraint 2. // ... Must be smaller than all squares below it. foreach (var listItem in data) { if (listItem.Item2 == i && // Same column. listItem.Item3 > y && // Lower. listItem.Item1 <= test) { invalid = true; break; } } // Constraint 3. // ... Must be larger than all squares to the right. foreach (var listItem in data) { if (listItem.Item2 > i && // To the right. listItem.Item3 == y && // Same row. listItem.Item1 >= test) { invalid = true; break; } } // Constraint 4. // ... Must be smaller than all squares to the left. foreach (var listItem in data) { if (listItem.Item2 < i && // To the left. listItem.Item3 == y && // Same row. listItem.Item1 <= test) { invalid = true; break; } } // We are invalid if a constraint was not met. if (invalid) { continue; } // Copy our data. var copy = new List<Tuple<int, int, int>>(data); // Add this new value to our data. copy.Add(new Tuple<int, int, int>(test, i, y)); // Recurse. AddItem(copy, width, height, globalMax); } } } } } static void Main() { // Add existing data to our list of tuples. // ... First int is the value. // Second is the X coordinate. // Third is the Y coordinate. var list = new List<Tuple<int, int, int>>(); list.Add(new Tuple<int, int, int>(100, 0, 0)); list.Add(new Tuple<int, int, int>(120, 0, 2)); list.Add(new Tuple<int, int, int>(5, 1, 2)); // Get maximum int from the data. int globalMax = GlobalMax(list); // Pass existing data and dimensions of puzzle as arguments. AddItem(list, 3, 3, globalMax); } } Output: first part ::RESULT 1:: 100 1 0 101 2 1 120 5 2 ::RESULT 2:: 100 1 0 101 2 1 120 5 3 ::RESULT 3:: 100 1 0 101 2 1 120 5 4 ::RESULT 4:: 100 1 0 101 3 1 120 5 2 ::RESULT 5:: 100 1 0 101 3 1 120 5 3 Output: second part ::RESULT 754:: 100 3 0 119 4 2 120 5 3 ::RESULT 755:: 100 3 0 119 4 2 120 5 4 ::RESULT 756:: 100 3 0 119 4 3 120 5 4 ::RESULT 757:: 100 3 1 119 4 2 120 5 3 ::RESULT 758:: 100 3 1 119 4 2 120 5 4 ::RESULT 759:: 100 3 1 119 4 3 120 5 4 ::RESULT 760:: 100 3 2 119 4 3 120 5 4

Notes, AddItem. The important part of the above program is the AddItem method. This is a recursive method. It adds a number to a square, then tries to add another one.Recursion

Constraints: It tests all 4 constraints for each number we add to the puzzle. For each constraint, we loop through all our existing data.

Copy: We always copy the data before calling AddItem from itself. This is so we can "branch out" without modifying data we may need again.

Results. The program produces 760 unique results. The first part of the output, and the last part, are shown. Each result is different, and each is valid according to our puzzle's rules.

Notes, duplicate effort. With these kinds of recursive puzzles, it is important to avoid duplicate work. Two recursive paths may end up converging on the same exact values.

And: We can just return early from one call stack at this point. We just want unique results.

An important point. For this puzzle, we could have infinite solutions if the bottom left number was not filled in. This number (120) is the greatest of all numbers.

A summary. Constraints can be used to solve puzzles complex and simple. Often we use constraints in recursive algorithms. But what about the rich man on the island?

After some exciting events, you escape from the island. Sadly you do not get to keep any great treasures (sorry). And no one will ever believe you were there to begin with.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Constraint Puzzle Solver

Related Links:

.Net

Java

Related Links