ABC Puzzle- Constraint Satisfaction Problem

Question

ABC is a logic puzzle on a board 5x5. In each row and column, there has to be exactly 3 letters(A,B,C) and 2 empty cells. Additionally for each row and column there is information about which is the first letter in that row/column. That does not mean that is the letter in the first cell, but the first letter in the row(There can be empty spaces before the first letter). This is the board with its information.

I need help figuring out the constraint for the first letter in each row and column.

I already have the constraint for each row and column but just cannot figure out how to find the exact place for the first letter in a row or column. This is what i have so far.

*Note i used 1,2,3 for A,B,C and i used "_"(Single space) and "__"(Double space) for the empty cells, in order to still stay within the 'AllDifferentConstraint'.

from constraint import *

if __name__ == "__main__":

problem = Problem(BacktrackingSolver())

variables = []
for i in range(0, 25):
    variables.append(i)
domain= []
for i in range(1,4):
    domain.append(i)

domain.append("_")
domain.append("__")

problem.addVariables(variables, domain)

for row in range(5):
    problem.addConstraint(AllDifferentConstraint(), [row * 5 + i for i in range(5)])

for col in range(5):
    problem.addConstraint(AllDifferentConstraint(), [col * 5 + i for i in range(5)])


solution = problem.getSolution()
print(solution)

Answer 1

Disclaimer:

• my code might look slightly over-engineered
• for someone doing lots of CP stuff recently, the available set of constraints of this library look strange and/or incomplete (compared to industrial-strength Gecode)
  • i consider this solution a hack (but it's enough for this toy-problem)
• i kept most of your code, but changed the spaces to numbers (8, 9) for better visualization

Basic idea Assuming the dimensions are fixed a-priori, there are exactly 5 valid cases for the constraint you seek, when looking from the front of the slice:

0: _  __ TARGET ...dontcare
1: __ _  TARGET ...dontcare
2: _  TARGET    ...dontcare
3: __ TARGET    ...dontcare
4: TARGET       ...dontcare

As someone coming from SAT-solving (before CP), i feel reasoning with clauses pretty natural. The above is easily expressed in boolean-logic (not same order as above):

   (  pos0 = F                  )
OR ( (pos0 = _ )  and (pos1 = F) )
OR ( (pos0 = __)  and (pos1 = F) )
OR ( (pos0 = __) and (pos1 = _  ) and (pos2 = F)
OR ( (pos0 = _ )  and (pos1 = __ ) and (pos2 = F)

Normally one would use a well-implemented constraint / propagator (using SAT technology), but this library is missing the usual stuff.

But to our rescue: there is FunctionConstraint which allows us to build a simple propagator. This is actually quite a nice design (for small and relatively easy problems)!

Some remarks:

• clause builds our boolean-logic based propagator (in non-efficient manner)
• row and clause returns the 1d-indices based on what we want
• reverse let's us reuse the logic when the constraint needs to act from the end (and not on the front)
• we use partial function application to make the calls compact
• numpy is just used as quick visualization-tool (there is nothing worse than reasoning about matrix-solutions from a dict)

Code

""" ORIGINAL CODE """

from constraint import *

problem = Problem(BacktrackingSolver())

variables = []
for i in range(0, 25):
    variables.append(i)
domain= []
for i in range(1,4):
    domain.append(i)

domain.append(8)
domain.append(9)

problem.addVariables(variables, domain)

for row in range(5):
    problem.addConstraint(AllDifferentConstraint(), [row * 5 + i for i in range(5)])

for col in range(5):
    problem.addConstraint(AllDifferentConstraint(), [col * 5 + i for i in range(5)])

""" ADDITIONS """

from functools import partial  

def clause(target, p0, p1, p2, p3, p4):
  wildcards = [8, 9]
  return (p0 == target) or                                              \
        ( (p0 in wildcards) and (p1 == target) ) or                    \
        ( (p0 in wildcards) and (p1 in wildcards) and p2 == target ) 


row = lambda x: [x * 5 + i for i in range(5)]
col = lambda x: [x + i * 5 for i in range(5)]
reverse = lambda x: list(reversed(x))

problem.addConstraint(partial(clause, 3), reverse(row(0))) # C
problem.addConstraint(partial(clause, 2), reverse(row(1))) # B
problem.addConstraint(partial(clause, 3), reverse(row(2))) # C
problem.addConstraint(partial(clause, 1), row(2))          # A
problem.addConstraint(partial(clause, 2), row(3))          # B
problem.addConstraint(partial(clause, 1), col(0))          # A
problem.addConstraint(partial(clause, 2), col(1))          # B
problem.addConstraint(partial(clause, 1), col(3))          # A
problem.addConstraint(partial(clause, 3), reverse(col(0))) # C
problem.addConstraint(partial(clause, 3), reverse(col(2))) # C
problem.addConstraint(partial(clause, 3), reverse(col(3))) # C

""" SOLVE """

solution = problem.getSolution()
print(solution)

""" VISUALIZE """

import numpy as np
matrix = np.zeros((5, 5), dtype=int)
matrix[np.unravel_index(range(5*5), (5,5))] = [solution[i] for i in range(5*5)]
print(matrix)

Output

λ python C:\Tmp\constr.py
{10: 9, 13: 3, 11: 1, 12: 2, 0: 9, 3: 1, 5: 1, 8: 2, 15: 9, 18: 8, 14: 8, 20: 3, 23: 9, 1: 2, 2: 8, 6: 9, 7: 3, 16: 2, 17: 3, 4: 3, 9: 8, 19: 1, 22: 8, 21: 2, 24: 1}

[[9 2 8 1 3]
 [1 9 3 2 8]
 [9 1 2 3 8]
 [9 2 3 8 1]
 [3 2 8 9 1]]

The result surprisingly looks correct ;-), comparing with your original task: