ABC Path is a game that you have to put into the N × N grid such that the total payoff of the game is maximized. If a letter is placed on the desired position, it gets 1 as payoff. Here is an example for the desired position of each letter for a 4×4 grid.

A   B   C   D
E   F   G   H
I   J   K   L
M   N   O   P

And the rule is the same for other N values. It follows the alphabetic order from the upper left to the bottom right.

We can model the problem with a set of 16 variables \(X =\) { \(x_i, j| i, j ∈ [1..4]\) }, each representing a cell of the grid. The domain of each variable \(x_i,j\) is \(D_i,j =\) { \(1, 2, .., 16\) } with each value representing the letter in { \(A,B,..,P\) } respectively. Let \(S_i,j\) be the set of all adjacent cells of \(x_i,j\). The set of constraints and the associated objective function of the problem are given as follows:

• \((x_{i,j} =1) \vee ( \bigvee _{s \in S_{i, j}} x_{i,j} =s+1 ) ,\) for \(i,j∈[1..4]\)
• \(x_{i,j} \ne x_{u,v},\) for \(i,j,u,v∈[1..4]\) where \(¬(i=u∧j=v)\)
• Objective: max \(\sum_{i,j \in [1...4]} (x_{i,j} −(4i+j −4) == 0)\)

An alternative way to model the problem is to represent each letter with a variable \(x_i\) , where \(i ∈ [1..n2 ]\) and the domain of each variable \(x_i\) is \(D_i =\) { \(1, 2, ..., n2\) } representing the position of the corresponding letter in the grid.

The Gecode implementation has been uploaded to my github repository. You can see the source code at website wangdaiwei/gecode.

The program should be run as following command in Mac OSX:

./abc_path -model mod 5

Here mod stands for the model you choose. The value is from 1 to 2, which represents the memtioned models. The last parameter defines the size of ABC Path problem.