I found a nice puzzle in the newspaper (Logelei, Zeit Magazin Nr.4 22.1.2015). It has (like many puzzles) the structure of a constraint satisfaction problem:

There are strange traffic rules in the country Leepf. At every crossing there is a sign with an arrow and a number. The number indicates the number of distinct numbers that are found at crossings in this direction.

Given is a grid of 5x5 crossings with 4 numbers already filled in:

Given my recent interest in constraint satisfaction, I immediately tried to solve it with constraining order, which turns out to be straightforward.

A new type of Constraint needs to be implemented that relates the value of a variable with the number of distinct values in a list of variables. I initially forgot to flag a labeling as inconsistent when not all variables in the list are labeled and there are not enough of these to reach the target number of distinct values. It turned out to help performance quite a bit by being able to reduce the problem space a bit at the beginning and stop examining some partial labelings earlier during backtracking.

The most tedious part is the formulation of the constraints, as there are 25 of them and they must be hardcoded. I used a numpy array to hold the variables in the same layout as the crossings, this allows to make use of the better slicing to conveniently express the constraints.

The full script looks like this:

from constrainingorder.sets import DiscreteSet from constrainingorder.variables import DiscreteVariable from constrainingorder.constraints import Constraint, FixedValue from constrainingorder.solver import solve,ac3 from constrainingorder import Space import numpy as np """ This script solves the following puzzle (Logelei, Zeit Magazin Nr.4 22.1.2015): There are strange traffic rules in Leepf. At every crossing there is a sign with an arrow and a number. The number indicates the number of distinct numbers that are found at crossings in this direction. Fill in the missing numbers For the layout of crossings see crossings.svg """ class NDistinctEqual(Constraint): """ This constraint makes sure that the value of a variable is equal to the number of distinct values in a list of variables. """ def __init__(self,var,varlist): domains = {} domains[var] = var.domain for v in varlist: domains[v] = v.domain Constraint.__init__(self,domains) self.var = var self.varlist = varlist def satisfied(self,lab): if not self.var.name in lab: return False values = set([]) for var in self.varlist: if not var.name in lab: return False values.add(lab[var.name]) return len(values) == lab[self.var.name] def consistent(self,lab): if not self.var.name in lab: return True values = set([]) unknown = 0 for var in self.varlist: if not var.name in lab: unknown += 1 continue values.add(lab[var.name]) #cannot reach number if len(values) + unknown < lab[self.var.name]: return False #exceed number if len(values) > lab[self.var.name]: return False return True #set up variables domain = DiscreteSet(range(1,5)) crossings = [] for i in range(5): row = [] for j in range(5): name = "c%d%d" % (j,i) row.append(DiscreteVariable(name,domain=domain)) crossings.append(row) crossings = np.array(crossings) #set up constraints cons = [] cons.append(NDistinctEqual(crossings[0,0],crossings[0,1:])) cons.append(NDistinctEqual(crossings[0,1],crossings[0,:1])) cons.append(NDistinctEqual(crossings[0,2],crossings[0,(0,1,3,4)])) cons.append(NDistinctEqual(crossings[0,3],crossings[1:,3])) cons.append(NDistinctEqual(crossings[0,4],crossings[(1,2,3,4),(3,2,1,0)])) cons.append(NDistinctEqual(crossings[1,0],crossings[(0,2,3,4),0])) cons.append(NDistinctEqual(crossings[1,1],crossings[(0,2,3,4),1])) cons.append(NDistinctEqual(crossings[1,2],crossings[1,(0,1,3,4)])) cons.append(NDistinctEqual(crossings[1,3],crossings[1,(0,1,2,4)])) cons.append(NDistinctEqual(crossings[1,4],crossings[(0,2,3,4),4])) cons.append(NDistinctEqual(crossings[2,0],crossings[3:,0])) cons.append(NDistinctEqual(crossings[2,1],crossings[3:,1])) cons.append(NDistinctEqual(crossings[2,2],crossings[(3,4),(3,4)])) cons.append(NDistinctEqual(crossings[2,3],crossings[(0,1,3),(1,2,4)])) cons.append(NDistinctEqual(crossings[2,4],crossings[(3,4),(3,2)])) cons.append(NDistinctEqual(crossings[3,0],crossings[(2,1,0),(1,2,3)])) cons.append(NDistinctEqual(crossings[3,1],crossings[(4,),(0,)])) cons.append(NDistinctEqual(crossings[3,2],crossings[(4,2,1),(1,3,4)])) cons.append(NDistinctEqual(crossings[3,3],crossings[3,(0,1,2,4)])) cons.append(NDistinctEqual(crossings[3,4],crossings[(0,1,2,4),4])) cons.append(NDistinctEqual(crossings[4,0],crossings[:4,0])) cons.append(NDistinctEqual(crossings[4,1],crossings[4,(0,2,3,4)])) cons.append(NDistinctEqual(crossings[4,2],crossings[4,(3,4)])) cons.append(NDistinctEqual(crossings[4,3],crossings[4,(0,1,2,4)])) cons.append(NDistinctEqual(crossings[4,4],crossings[(0,1,2,3),(0,1,2,3)])) cons.append(FixedValue(crossings[0,0],4)) cons.append(FixedValue(crossings[0,4],3)) cons.append(FixedValue(crossings[4,0],4)) cons.append(FixedValue(crossings[4,4],3)) space = Space(crossings.ravel().tolist(),cons) ac3(space) for vname, domain in sorted(space.domains.items()): print vname, domain for solution in solve(space,method='backtrack'): print solution

This gives a single, correct solution very quickly. I had the impression that the solution is quite heavily constrained even without the given number, so I removed the FixedValue constraints and solved again. This resulted in only 14 solutions. The simplest one has value 1 for every variable, which one could have found by careful thinking. Most of the other solutions only contain the values 1 and 2, and then there are one which contains the values 1 to 3 and one that contains the values 1 to 4. So the 4 given numbers are more than enough information to make the solution unique, either one of them would have been enough, but also a tad more difficult. Mentioning that there is a four somewhere would also be ok, but even more difficult.