Snake - A through Y on a 5 x 5 grid

Question

You are given a 5 x 5 grid, and this grid should hold the letters A through Y.  Some of the cells in the grid are already filled out.  The others can go anywhere, but the constraint is that adjacent letters (for example F and G) must be adjacent to each other, either horizontally or vertically.  

-    -    -    -    Y
R    A    -    -    -
-    -    -    -    -
-    E    -    -    -
-    -    -    -    K

Design a solution for this constraint satisfaction problem.  (Solution should explain the variables, the domain values, the constraints, and how the constraint propagation would work.)

Answer 1

For this problem, there are two tricks I used.

First, you can check the Manhattan distance between all placed (including pre-placed) letters and a cell. If any domain values of the cell, the distance in alphabetical order from that value to the value of any assigned cell is larger than the Manhattan distance to that assigned cell. The value should be removed.

Second, the AC3 should be evaluated for all constraints for a given cell before you decide whether to remove that value from domain or not. For instance, (0,0) you need to check (1,0) and (0,1), as long as any value is possible to have an adjacent value given the domain of those two cells. The value should not be removed.

You can also apply additional things like minimum remaining value (to select variable), least constraining value (to order values), and variable with most constraints (as a tie breaker for variable selection).

Answer 2

Variables:

Use an array to present the grid, assuming it’s A[5][5]

Domain Values:

Each variable can take any of the letters A to Y, but some variables already have assigned values. Here take A[0][4]=’Y’ as an example.

 

Constraints:

1. Adjacent Letters: If two cells are adjacent (horizontally or vertically), their values must be adjacent in the alphabet.

2. Pre-assigned Values: Some cells already have assigned letters, and these cannot be changed.

3. Unique Letters Constraint: Each letter from A to Y must appear exactly once.

 

Constraint Propagation:

1. Initialization: Start by reducing the domain of each variable based on the pre-assigned values.

2. Consistency: Ensure that for every pair of adjacent cells, there exists a combination of letters that satisfies the adjacent letters constraint. This might further reduce the domains.

3. Forward: Choosing a random value from the current domain. When a value is assigned to a variable, immediately reduce the domain of all adjacent variables similar to step1 and step2.

4. Back tracing: If no value can be assigned to a variable that satisfies the constraints, backtrack to the previous variable and try a different value.

 

Solution:

The solution will be a complete assignment of letters to the grid, satisfying all constraints. This can be achieved through a recursive back tracing algorithm, where we choose a variable, assign a value from its domain, propagate constraints, and move to the next variable. If we encounter a dead end, we backtrack and try a different value.

Answer 3

Let's establish the important aspects for designing a solution to this constraint satisfaction problem (CSP):

Variables: A variable is each cell in the 5x5 grid. There are a total of 25 cells.
Variable names can be written as (row, column), such as (1, 1) for the top-left cell.

Domain: Each variable's domain is the set of letters A through Y.
The filled cells already have fixed values and are removed from the domain of the variables that relate to them.

Constraints: Adjacent cells must have letters that are either horizontally or vertically adjacent.
If two cells (i, j) and (k, l) are contiguous, the letters in those cells must also be adjacent in the English alphabet.

Constraint Propagation:

Constraint propagation entails iteratively lowering variable domains depending on constraints.
When a variable is assigned a value, the domains of its neighbors are modified in accordance with the adjacency requirement.
For example, if cell (1, 1) is allocated 'R', cells (1, 2) and (2, 1) must have domains confined to letters next to 'R'.
The process is repeated until a solution is discovered or a variable has an empty domain, indicating an inconsistency.