// (c) 2026-2026 Fair Isaac Corporation

using System;
using Optimizer;
using Optimizer.Maps;
using Optimizer.Objects;
using static Optimizer.Objects.Utils;


namespace XpressExamples {
  /// <summary>9x9 Sudoku puzzle to illustrate solution enumeration.</summary>
  /// <remarks>
  /// This is a pure feasibility problem, i.e., the objective function is
  /// all-zero.
  /// We first solve with prefixed values that allow exactly one solution.
  /// Then we add clear one of the fixings and enumerate all solutions the
  /// new board allows.
  /// </remarks>
  class Sudoku {
    /// <summary>The available row indices (first row has index zero).</summary>
    static readonly int[] ROWS = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    /// <summary>The available column indices (first column has index zero). </summary>
    static readonly int[] COLS = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    /// <summary>The available values (1 through 9).</summary>
    static readonly int[] VALS = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    /// <summary>Values that are fixed in the beginning.</summary>
    /// <remarks>
    /// These fixings allow exactly one feasible solution.
    /// Data set from "The Guardian", 15 July, 2005. http://www.guardian.co.uk/sudoku
    /// </remarks>
    static int[,] PRESET = {
      { 0, 0, 0, 7, 0, 5, 6, 9, 0 },
      { 0, 0, 8, 0, 4, 0, 0, 0, 7 },
      { 0, 2, 0, 0, 0, 3, 0, 0, 0 },
      { 0, 0, 2, 0, 0, 0, 9, 0, 0 },
      { 0, 0, 0, 9, 0, 0, 0, 8, 0 },
      { 0, 0, 0, 0, 1, 0, 0, 0, 5 },
      { 0, 0, 0, 0, 0, 4, 0, 0, 0 },
      { 0, 0, 6, 0, 0, 0, 3, 0, 4 },
      { 0, 0, 0, 8, 2, 1, 0, 5, 0 },
    };

    /// <summary>Print a board to the console.</summary>
    /// <param name='board'>A 9x9 array that specifies the numbers that are
    /// set in board. A zero means "not set".</param>
    static void PrintBoard(int[,] board) {
      foreach (int r in ROWS) {
        string fill = (r == 3 || r == 6) ? "===+" : "---+";
        Console.Write("+");
        foreach (int c in COLS) {
          Console.Write(fill);
          if (c == 2 || c == 5)
            Console.Write('+');
        }
        Console.WriteLine();
        Console.Write("|");
        foreach (int c in COLS) {
          Console.WriteLine($" {((board[r,c] == 0) ? ' ' : (char)(board[r,c] + '0'))} |");
          if (c == 2 || c == 5)
            Console.Write("|");
        }
        Console.WriteLine();
      }
      Console.Write("+");
      foreach (int c in COLS) {
        Console.Write("---+");
        if (c == 2 || c == 5)
          Console.Write('+');
      }
      Console.WriteLine();
    }

    /// <summary>Print a soolution.</summary>
    /// <remarks>
    /// Constructs a board from a solution and then prints it.
    /// </remarks>
    /// <param name='b'>The binary variables.</param>
    /// <param name='sol'>The solution values for b.</param>
    static void PrintSolution(HashMap3<int, int, int, Variable> b, double[] sol) {
      int[,] result = new int[9,9];
      foreach (int r in ROWS) {
        foreach (int c in COLS) {
          foreach (int v in VALS) {
            if (b[r, c, v].GetValue(sol) > 0.5) {
              result[r,c] = v;
            }
          }
        }
      }
      PrintBoard(result);
    }

    /// <summary>Solve the 9x9 Sudoku puzzle with the given fixed values.</summary>
    /// <param name='preset'>The values that are fixed on the board.</param>
    /// <param name='enumerate'>If true then we enumerate all solutions,
    ///                   otherwise we stop on the first solution. Note that
    ///                   enumeration can become expensive the more solutions
    ///                   there are.</param>
    static void Solve(int[,] preset, bool enumerate) {
      using (XpressProblem prob = new XpressProblem()) {
        // Create the variables. One binary variable for each combination of
        // row, column, value.
        // We store the variables in a map rather than a 3D array since rows and
        // columns index from 0, but values index from 1.
        HashMap3<int, int, int, Variable> b = prob.AddVariables(ROWS, COLS, VALS)
          .WithName("b({0},{1},{2})")
          .WithType(ColumnType.Binary)
          .ToMap();

        // Fix the variables that should be fixed on the initial board.
        foreach (int r in ROWS) {
          foreach (int c in COLS) {
            if (preset[r,c] > 0) {
              b[r, c, preset[r, c]].Fix(1.0);
            }
          }
        }

        // Each cell must have a number.
        prob.AddConstraints(ROWS, COLS, (r, c) => Sum(VALS, v => b[r, c, v]) == 1.0);

        // Each number must appear exactly once in a row.
        prob.AddConstraints(ROWS, VALS, (r, v) => Sum(COLS, c => b[r, c, v]) == 1.0);
        // Each number must appear exactly once in a column.
        prob.AddConstraints(COLS, VALS, (c, v) => Sum(ROWS, r => b[r, c, v]) == 1.0);
        // In 3x3 squares all values must be different.
        for (int k = 0; k < 3; ++k) {
          int[] colidx = {3 * k, 1 + 3 * k, 2 + 3 * k};
          foreach (int v in VALS) {
            prob.AddConstraint(Sum(new int[]{0, 1, 2}, colidx,
                                   (x, y) => b[x, y, v]) == 1.0);
            prob.AddConstraint(Sum(new int[]{3, 4, 5}, colidx,
                                   (x, y) => b[x, y, v]) == 1.0);
            prob.AddConstraint(Sum(new int[]{6, 7, 8}, colidx,
                                   (x, y) => b[x, y, v]) == 1.0);
          }
        }
        // Enable log output and prepare for numeration (if requested).
        prob.callbacks.AddMessageCallback(DefaultMessageListener.Console);
        if (enumerate) {
          prob.PoolEnumStrategy = PoolEnumStrategy.Full;
          prob.PoolLimit = Int32.MaxValue; // Find all solutions.
        }
        // Find all solutions.
        prob.Optimize();
        // Print solutions.
        // Note that we only print the first 10 solutions to not flood the screen.
        for (int s = 0; s < Math.Min(10, prob.PoolSize); ++s) {
          Console.WriteLine($"Solution {s}:");
          PrintSolution(b, prob.GetPoolSolution(s));
        }
      }
    }


    public static void Main(string[] args) {
      // First solve with the preset board. This should allow exactly one solution.
      Solve(PRESET, false);
      // Now remove some fixed values and enumerate all solutions.
      PRESET[0, 3] = 0;
      Solve(PRESET, true);
    }
  }
}