fixpoint

#
# Quasigroup Completion in Elixir.
#
# See
# Carla P. Gomes and David Shmoys:
# "Completing Quasigroups or Latin Squares: Structured Graph Coloring Problem"
#
# See also
# Ivars Peterson "Completing Latin Squares"
# http://www.maa.org/mathland/mathtrek_5_8_00.html
# """
# Using only the numbers 1, 2, 3, and 4, arrange four sets of these
# numbers into a four-by-four array so that no column or row contains
# the same two numbers. The result is known as a Latin square.
# ...
# The so-called quasigroup completion problem concerns a table that is
# correctly but only partially filled in. The question is whether the
# remaining blanks in the table can be filled in to obtain a complete
# Latin square (or a proper quasigroup multiplication table).
# """
#
#
# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
## Boris Okner: modified to sync with the latest API,
## change then naming and the result handling.
##

defmodule CPSolver.Examples.Hakank.QuasigroupCompletion do
  import Hakank.CPUtils

  alias CPSolver.IntVariable
  # alias CPSolver.Constraint.Sum
  # alias CPSolver.Constraint.Equal
  # alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
  alias CPSolver.Model

  #
  # Example from Ruben Martins and Inès Lynce
  # Breaking Local Symmetries in Quasigroup Completion Problems, page 3
  # The solution is unique:
  # 1 3 2 5 4
  # 2 5 4 1 3
  # 4 1 3 2 5
  # 5 4 1 3 2
  # 3 2 5 4 1
  #
  def puzzle(1) do
    [[1, 0, 0, 0, 4],   # 0 are the unknowns
     [0, 5, 0, 0, 0],
     [4, 0, 0, 2, 0],
     [0, 4, 0, 0, 0],
     [0, 0, 5, 0, 1]]
  end

  #
  # Example from Gomes & Shmoys, page 3.
  # Solution:
  # 4 1 2 3
  # 2 3 4 1
  # 1 4 3 2
  # 3 2 1 4
  #
  def puzzle(2) do
    [[0, 1, 2, 3],
     [2, 0, 4, 1],
     [1, 4, 0, 2],
     [3, 0, 1, 0]]
  end

  # Example from Gomes & Shmoys, page 7
  # Two solutions.
  #
  def puzzle(3) do
    [[0, 1, 0, 0],
     [0, 0, 2, 0],
     [0, 3, 0, 0],
     [0, 0, 0, 4]]
  end


  #
  # Example from Global Constraint Catalogue
  # http://www.emn.fr/x-info/sdemasse/gccat/sec2.7.108.html
  #
  # 12 solutions.
  #
  def puzzle(4) do
    [[1, 0, 0, 0],
     [0, 0, 0, 3],
     [3, 0, 0, 0],
     [0, 0, 0, 1]]
  end


  #
  # Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
  # (n = 10]
  # Pattern #1.
  # There are _many_ solutions to this problem.
  #
  def puzzle(5) do
    [
      [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
      [0, 1, 0, 0, 0, 2, 0, 0, 0, 0],
      [1, 0, 0, 0, 2, 0, 0, 0, 0, 0],
      [0, 0, 0, 2, 1, 0, 0, 0, 0, 0],
      [0, 0, 2, 0, 0, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 1, 0, 2],
      [0, 0, 0, 0, 0, 0, 0, 0, 2, 0],
      [0, 0, 0, 0, 0, 0, 0, 2, 0, 0]
    ]
  end

  #
  # Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
  # (n = 10]
  # Pattern #2.
  # There are many solutions to this problem.
  #
  def puzzle(6) do
    [
      [0, 0, 1, 2, 3, 4, 0, 0, 0, 0],
      [0, 1, 2, 3, 0, 0, 4, 0, 0, 0],
      [1, 2, 3, 0, 0, 0, 0, 4, 0, 0],
      [2, 3, 0, 0, 0, 0, 0, 0, 4, 0],
      [3, 0, 0, 0, 0, 0, 0, 0, 0, 4],
      [5, 6, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 5, 6, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 5, 6, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 5, 6, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 5, 6, 0, 0, 0, 0]
    ]
  end

  #
  # Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
  # (n = 10]
  # Pattern #3.
  # Coding:
  #    dark red   = 1
  #    light blue = 2
  #    dark blue  = 3
  #    light red  = 4
  #    brown      = 5
  #    green      = 6
  #    pink       = 7
  #    grey       = 8
  #    black      = 9
  #    yellow     = 10
  # There are 40944 solutions for this pattern.
  #
  # This takes 9.5s, about to solve and print all solutions.
  #
  def puzzle(7) do
    [
      [0, 0, 1, 5, 2, 6, 7, 8, 0, 0],
      [0, 1, 5, 2, 0, 0, 6, 7, 8, 0],
      [1, 5, 2, 0, 0, 0, 0, 6, 7, 8],
      [5, 2, 0, 0, 0, 0, 0, 0, 6, 7],
      [2, 0, 0, 0, 0, 0, 0, 0, 0, 6],
      [4, 10, 0, 0, 0, 0, 0, 0, 3, 9],
      [0, 4, 10, 0, 0, 0, 0, 3, 9, 0],
      [0, 0, 4, 10, 0, 0, 3, 9, 0, 0],
      [0, 0, 0, 4, 10, 3, 9, 0, 0, 0],
      [0, 0, 0, 0, 4, 9, 0, 0, 0, 0]
    ]
  end

  #
  # Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
  # (n = 10]
  # Pattern #4.
  #  dark red   = 1
  #  light blue = 2
  #  dark blue  = 3
  #  light red  = 4
  # Note: There are no solutions to this problem.
  #
  def puzzle(8) do
    [
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      [2, 1, 0, 0, 0, 0, 0, 0, 0, 4],
      [3, 2, 1, 0, 0, 0, 0, 0, 4, 0],
      [0, 3, 2, 1, 0, 0, 0, 4, 0, 0],
      [0, 0, 3, 2, 1, 0, 4, 0, 0, 0],
      [0, 0, 0, 3, 2, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 3, 2, 1, 0, 0, 0],
      [0, 0, 0, 4, 0, 3, 2, 1, 0, 0],
      [0, 0, 4, 0, 0, 0, 3, 2, 1, 0],
      [0, 4, 0, 0, 0, 0, 0, 3, 2, 1]
    ]
  end

  #
  # Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
  # (n = 10]
  # Pattern #5
  # Note: There are no solutions to this problem.
  #
  def puzzle(9) do
    [
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
      [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
      [0, 0, 0, 0, 0, 0, 2, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
      [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]
  end

  #
  #
  #
  def run(opts \\ []) do
    # Problem 5..7 yields a huge number of solutions.
    # Let's just pick the first.
    1..7
    |> Enum.map(fn p ->
      IO.puts("Running problem #{p}")

      cond do
        p in [5..7] -> solve_puzzle(p, Keyword.put(opts, :num_solutions, 1))
        true -> solve_puzzle(p, opts)
      end
    end)
  end

  def solve_puzzle(id, opts \\ []) do
    quasigroup_completion(puzzle(id), opts)
  end

  #
  # Running problems 8 and 9 (no solution)
  # Takes long time in current Fixpoint version
  ##
  ## Boris Okner: if using AllDifferent.DC.Fast for `latin_square`,
  ## these puzzles will instantly fail due to early propagation.
  def run_unsatisfiable(opts \\ []) do
    Enum.each([8, 9], fn puzzle_id ->
      try do
        solve_puzzle(puzzle_id, opts)
      catch
        {:fail, _} ->
          IO.puts("Puzzle #{puzzle_id} doesn't have solutions")
      end
    end)
  end

  @doc """
  quasigroup_completion(mat,num_sols \\ :infinity)

  Solves the Quasigroup completion problem for the matrix `mat`.
  `num_sols` are the required number of solutions, defaults to :infinity.

  """
  def quasigroup_completion(mat, opts \\ []) do
    n = length(mat)
    dom = 1..n

    #
    # Decision variables
    #

    x =
      for i <- 0..(n - 1) do
        for j <- 0..(n - 1) do
          v = mat_at(mat, i, j)

          if v > 0 do
            # > 0: this is a hint
            IntVariable.new(v, name: "x[#{i},#{j}]")
          else
            # 0: unknown
            IntVariable.new(dom, name: "x[#{i},#{j}]")
          end
        end
      end

    x_flatten = List.flatten(x)

    #
    # Constraints
    #
    constraints = latin_square(x)

    model =
      Model.new(
        x_flatten,
        constraints
      )

    Logger.configure(level: :info)

    opts =
      Keyword.merge(default_opts(), opts)
      |> then(fn opts ->
        Keyword.put(opts, :stop_on, {:max_solutions, opts[:num_solutions]})
      end)

    {:ok, result} =
      CPSolver.solve(
        model,
        opts
      )

    ## Print last solution
    print_matrix(result.solutions |> List.last(), n, n, "~3w")
    ##
    IO.inspect(result.statistics)

    {:ok, result}
  end

  defp default_opts() do
    [
      search: {:first_fail, :indomain_max},
      # search: {:first_fail, :indomain_min},
      # search: {:first_fail, :indomain_random},
      # search: {:input_order, :indomain_max},
      num_solutions: :infinity,
      timeout: :timer.minutes(5)
    ]
  end
end