ortools-clone/examples/contrib/discrete_tomography.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 DiscreteTomography
{
    // default problem
    static int[] default_rowsums = { 0, 0, 8, 2, 6, 4, 5, 3, 7, 0, 0 };
    static int[] default_colsums = { 0, 0, 7, 1, 6, 3, 4, 5, 2, 7, 0, 0 };

    static int[] rowsums2;
    static int[] colsums2;

    /**
     *
     * Discrete tomography
     *
     * Problem from http://eclipse.crosscoreop.com/examples/tomo.ecl.txt
     * """
     * This is a little 'tomography' problem, taken from an old issue
     * of Scientific American.
     *
     * A matrix which contains zeroes and ones gets "x-rayed" vertically and
     * horizontally, giving the total number of ones in each row and column.
     * The problem is to reconstruct the contents of the matrix from this
     * information. Sample run:
     *
     * ?- go.
     *    0 0 7 1 6 3 4 5 2 7 0 0
     * 0
     * 0
     * 8      * * * * * * * *
     * 2      *             *
     * 6      *   * * * *   *
     * 4      *   *     *   *
     * 5      *   *   * *   *
     * 3      *   *         *
     * 7      *   * * * * * *
     * 0
     * 0
     *
     * Eclipse solution by Joachim Schimpf, IC-Parc
     * """
     *
     * See  http://www.hakank.org/or-tools/discrete_tomography.py
     *
     */
    private static void Solve(int[] rowsums, int[] colsums)
    {
        Solver solver = new Solver("DiscreteTomography");

        //
        // Data
        //
        int r = rowsums.Length;
        int c = colsums.Length;

        Console.Write("rowsums: ");
        for (int i = 0; i < r; i++)
        {
            Console.Write(rowsums[i] + " ");
        }
        Console.Write("\ncolsums: ");
        for (int j = 0; j < c; j++)
        {
            Console.Write(colsums[j] + " ");
        }
        Console.WriteLine("\n");

        //
        // Decision variables
        //
        IntVar[,] x = solver.MakeIntVarMatrix(r, c, 0, 1, "x");
        IntVar[] x_flat = x.Flatten();

        //
        // Constraints
        //

        // row sums
        for (int i = 0; i < r; i++)
        {
            var tmp = from j in Enumerable.Range(0, c) select x[i, j];
            solver.Add(tmp.ToArray().Sum() == rowsums[i]);
        }

        // cols sums
        for (int j = 0; j < c; j++)
        {
            var tmp = from i in Enumerable.Range(0, r) select x[i, j];
            solver.Add(tmp.ToArray().Sum() == colsums[j]);
        }

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

        solver.NewSearch(db);

        while (solver.NextSolution())
        {
            for (int i = 0; i < r; i++)
            {
                for (int j = 0; j < c; j++)
                {
                    Console.Write("{0} ", x[i, j].Value() == 1 ? "#" : ".");
                }
                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();
    }

    /**
     *
     * Reads a discrete tomography file.
     * File format:
     *  # a comment which is ignored
     *  % a comment which also is ignored
     *  rowsums separated by [,\s]
     *  colsums separated by [,\s]
     *
     * e.g.
     * """
     * 0,0,8,2,6,4,5,3,7,0,0
     * 0,0,7,1,6,3,4,5,2,7,0,0
     * # comment
     * % another comment
     * """
     *
     */
    private static void readFile(String file)
    {
        Console.WriteLine("readFile(" + file + ")");

        TextReader inr = new StreamReader(file);
        String str;
        int lineCount = 0;
        while ((str = inr.ReadLine()) != null && str.Length > 0)
        {
            str = str.Trim();

            // ignore comments
            if (str.StartsWith("#") || str.StartsWith("%"))
            {
                continue;
            }

            if (lineCount == 0)
            {
                rowsums2 = ConvLine(str);
            }
            else if (lineCount == 1)
            {
                colsums2 = ConvLine(str);
                break;
            }

            lineCount++;

        } // end while

        inr.Close();

    } // end readFile

    private static int[] ConvLine(String str)
    {
        String[] tmp = Regex.Split(str, "[,\\s]+");
        int len = tmp.Length;
        int[] sums = new int[len];
        for (int i = 0; i < len; i++)
        {
            sums[i] = Convert.ToInt32(tmp[i]);
        }

        return sums;
    }

    public static void Main(String[] args)
    {
        if (args.Length > 1)
        {
            readFile(args[1]);
            Solve(rowsums2, colsums2);
        }
        else
        {
            Solve(default_rowsums, default_colsums);
        }
    }
}