costas_array.cs

//
// Copyright 2012 Hakan Kjellerstrand
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using Google.OrTools.ConstraintSolver;

public class CostasArray
{
    /**
     *
     * Costas array
     *
     * From http://mathworld.wolfram.com/CostasArray.html:
     * """
     * An order-n Costas array is a permutation on {1,...,n} such
     * that the distances in each row of the triangular difference
     * table are distinct. For example, the permutation {1,3,4,2,5}
     * has triangular difference table {2,1,-2,3}, {3,-1,1}, {1,2},
     * and {4}. Since each row contains no duplications, the permutation
     * is therefore a Costas array.
     * """
     *
     * Also see
     * http://en.wikipedia.org/wiki/Costas_array
     * http://hakank.org/or-tools/costas_array.py
     *
     */
    private static void Solve(int n = 6)
    {
        Solver solver = new Solver("CostasArray");

        //
        // Data
        //
        Console.WriteLine("n: {0}", n);

        //
        // Decision variables
        //
        IntVar[] costas = solver.MakeIntVarArray(n, 1, n, "costas");
        IntVar[,] differences = solver.MakeIntVarMatrix(n, n, -n + 1, n - 1, "differences");

        //
        // Constraints
        //

        // Fix the values in the lower triangle in the
        // difference matrix to -n+1. This removes variants
        // of the difference matrix for the the same Costas array.
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                solver.Add(differences[i, j] == -n + 1);
            }
        }

        // hakank: All the following constraints are from
        // Barry O'Sullivans's original model.
        //
        solver.Add(costas.AllDifferent());

        // "How do the positions in the Costas array relate
        //  to the elements of the distance triangle."
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i < j)
                {
                    solver.Add(differences[i, j] - (costas[j] - costas[j - i - 1]) == 0);
                }
            }
        }

        // "All entries in a particular row of the difference
        //  triangle must be distint."
        for (int i = 0; i < n - 2; i++)
        {
      IntVar[] tmp = (from j in Enumerable.Range(0, n)
                          where j > i select differences[i, j])
                         .ToArray();
      solver.Add(tmp.AllDifferent());
        }

        //
        // "All the following are redundant - only here to speed up search."
        //

        // "We can never place a 'token' in the same row as any other."
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i < j)
                {
                    solver.Add(differences[i, j] != 0);
                    solver.Add(differences[i, j] != 0);
                }
            }
        }

        for (int k = 2; k < n; k++)
        {
            for (int l = 2; l < n; l++)
            {
                if (k < l)
                {
                    solver.Add((differences[k - 2, l - 1] + differences[k, l]) -
                                   (differences[k - 1, l - 1] + differences[k - 1, l]) ==
                               0);
                }
            }
        }

        //
        // Search
        //
        DecisionBuilder db = solver.MakePhase(costas, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        solver.NewSearch(db);

        while (solver.NextSolution())
        {
            Console.Write("costas: ");
            for (int i = 0; i < n; i++)
            {
                Console.Write("{0} ", costas[i].Value());
            }
            Console.WriteLine("\ndifferences:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    long v = differences[i, j].Value();
                    if (v == -n + 1)
                    {
                        Console.Write("   ");
                    }
                    else
                    {
                        Console.Write("{0,2} ", v);
                    }
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }

        Console.WriteLine("\nSolutions: {0}", solver.Solutions());
        Console.WriteLine("WallTime: {0}ms", solver.WallTime());
        Console.WriteLine("Failures: {0}", solver.Failures());
        Console.WriteLine("Branches: {0} ", solver.Branches());

        solver.EndSearch();
    }

    public static void Main(String[] args)
    {
        int n = 6;

        if (args.Length > 1)
        {
            n = Convert.ToInt32(args[1]);
        }

        Solve(n);
    }
}