Puzzles libres en Scala — Atelier LINUQ

J’ai eu la chance de présenter un atelier sur les puzzles libres en Scala au LINUQ. L’idée : utiliser la programmation par contraintes pour résoudre des casse-têtes classiques, le tout en code source libre. Voici le contenu de l’atelier.

🌘 Contexte

Le LINUQ (Linux UQ) est le groupe d’utilisateurs Linux et de logiciels libres de l’Université du Québec. Dans le cadre de leurs ateliers, j’ai proposé une séance de programmation par contraintes en Scala.

La programmation par contraintes est un paradigme où tu déclares les relations (contraintes) qui doivent être satisfaites, et le moteur de résolution cherche une solution qui les respecte toutes. C’est particulièrement adapté aux puzzles logiques.

graph TD
    A[Déclarer les variables CPIntVar] --> B[Définir leur domaine de valeurs]
    B --> C[Ajouter les contraintes<br>ex: allDifferent]
    C --> D[Lancer la recherche<br>search(binaryFirstFail)]
    D --> E{Solution trouvée?}
    E -->|Oui| F[Afficher avec onSolution]
    E -->|Non| G[Backtrack automatique]
    F --> D
    G --> D
    D --> H[Aucune solution? → stats]

La bibliothèque utilisée est OscaR, une librairie Scala open source pour la recherche opérationnelle.

🌘 Le projet SBT

Le projet est structuré avec SBT (Scala Build Tool) 1.1.1. Une seule dépendance externe : OscaR 3.1.0.

// build.sbt
name := "puzzles_libre"
version := "0.1"
scalaVersion := "2.11.12"

resolvers += "Artifactory" at "http://artifactory.info.ucl.ac.be/artifactory/libs-release/"

libraryDependencies += "oscar" % "oscar-cp_2.11" % "3.1.0"

// project/build.properties
sbt.version = 1.1.1

Pour lancer un puzzle :

sbt "runMain Sudoku2"
sbt "runMain Queens"
sbt "runMain CrossWord"

🌘 Les puzzles

🌘 Sudoku

Le solveur de Sudoku utilise OscaR avec des contraintes allDifferent sur les lignes, colonnes et régions. Trois contraintes suffisent pour résoudre la grille :

graph TD
    subgraph "Contraintes du Sudoku"
        L[add(allDifferent⁡(x(i)))] --> V[Valeurs uniques par ligne]
        C[add(allDifferent⁡(x_t(i)))] --> V
        R[add(allDifferent⁡(région 3×3))] --> V
    end
    V --> S[Solution complète]

import oscar.cp._
import scala.io.Source._
import scala.math._

object Sudoku2 extends CPModel with App {

  var n = 9
  var reg = 3
  val X = 0

  var problem = Array(
    Array(X, X, X, 2, X, 5, X, X, X),
    Array(X, 9, X, X, X, X, 7, 3, X),
    Array(X, X, 2, X, X, 9, X, 6, X),
    Array(2, X, X, X, X, X, 4, X, 9),
    Array(X, X, X, X, 7, X, X, X, X),
    Array(6, X, 9, X, X, X, X, X, 1),
    Array(X, 8, X, 4, X, X, 1, X, X),
    Array(X, 6, 3, 1, X, X, X, 8, X),
    Array(X, X, X, 6, X, 8, X, X, X))

  val alpha = ('0' to '9') ++ ('A' to 'Z')

  if (args.length > 0) {
    val fileName = args(0)
    println("\nReading from file: " + fileName)
    val lines = fromFile(fileName).getLines.filter(!_.startsWith("#")).toArray
    n = lines(0).toInt
    reg = sqrt(n).toInt
    println("Size:" + n)
    val this_problem = lines.tail.map(_.split("\\s+").
      filter(_.length>0).map(i=>if (i == ".") X else i.toInt))
    problem = this_problem
  }

  val x = Array.fill(n,n)(CPIntVar(1 to n))
  val x_t = x.transpose

  for(i <- NRANGE; j <- NRANGE if problem(i)(j) > 0) {
    add(x(i)(j) == problem(i)(j))
  }

  for(i <- NRANGE) {
    add(allDifferent(x(i)), Strong)
    add(allDifferent(x_t(i)), Strong)
  }

  for(i <- RRANGE; j <- RRANGE) {
    add(allDifferent((for{ r <- i*reg until i*reg+reg;
                           c <- j*reg until j*reg+reg
    } yield x(r)(c))), Strong)
  }

  search { binaryFirstFail(x.flatten.toSeq) }

  onSolution {
    println("\nSolution:")
    for(i <- 0 until n) {
      println(x(i).map(j=>alpha(j.value)).mkString(" "))
    }
    numSols += 1
  }

  val stats = start()
  println(stats)
}

🌘 N-Reines

Le problème classique des N-Reines : placer 12 reines sur un échiquier sans qu’aucune ne se menace. La solution tient en quelques lignes grâce aux contraintes allDifferent. Chaque reine est représentée par sa colonne, et trois contraintes assurent qu’aucune ne partage la même ligne, diagonale montante ou descendante :

graph LR
    subgraph "12 reines sur 12×12"
        Q[queens = Array(12 CPIntVar)]
    end
    Q --> C1[allDifferent⁡(queens)]
    Q --> C2[allDifferent⁡(queens + i)]
    Q --> C3[allDifferent⁡(queens - i)]
    C1 --> R1[Aucune reine sur la même ligne]
    C2 --> R2[Aucune sur la diagonale ↗]
    C3 --> R3[Aucune sur la diagonale ↘]

import oscar.cp._
object Queens extends CPModel with App {
  val nQueens = 12
  val Queens = 0 until nQueens
  val queens = Array.fill(nQueens)(CPIntVar.sparse(0, nQueens - 1))

  add(allDifferent(queens))
  add(allDifferent(Queens.map(i => queens(i) + i)))
  add(allDifferent(Queens.map(i => queens(i) - i)))

  search(binaryFirstFail(queens))

  onSolution {
    print("Solution potentielle\n")
    println(queens.mkString(" "))
  }

  val stats = start()
  println(stats)
}

🌘 Mots croisés

Le plus complexe des trois : un puzzle de mots croisés où les mots doivent s’entrecroiser correctement. Les contraintes d’intersection sont modélisées via une matrice de chevauchements. La variable E sélectionne quels mots parmi les 15 candidats sont placés horizontalement, et les contraintes d’intersection lient leurs lettres aux mots verticaux :

graph LR
    subgraph "Mots horizontaux (candidats)"
        H0[0: HOSES]
        H3[3: SAILS]
        H6[6: HEEL]
        H7[7: HIKE]
    end
    subgraph "Mots verticaux (candidats)"
        V1[1: LASER]
        V2[2: SAILS]
        V4[4: SHEET]
        V5[5: STEER]
    end
    H0 -- "E(0)∩E(1)" --> V1
    H3 -- "E(3)∩E(2) et E(3)∩E(4)" --> V2
    H6 -- "E(6)∩E(1) et E(6)∩E(4)" --> V4
    H7 -- "E(7)∩E(4) et E(7)∩E(5)" --> V5

import oscar.cp._
import oscar.cp.core.CPPropagStrength

object CrossWord extends CPModel with App {

  val alpha = Array(" ", "a", "b", "c", "d", "e", "f",
    "g", "h", "i", "j", "k", "l", "m",
    "n", "o", "p", "q", "r", "s", "t",
    "u", "v", "w", "x", "y", "z")

  val a = 1; val b = 2; val c = 3; val d = 4; val e = 5
  val f = 6; val g = 7; val h = 8; val i = 9; val j = 10
  val k = 11; val l = 12; val m = 13; val n = 14; val o = 15
  val p = 16; val q = 17; val r = 18; val s = 19; val t = 20
  val u = 21; val v = 22; val w = 23; val x = 24; val y = 25; val z = 26

  val AA = Array(
    Array(h, o, s, e, s),  // HOSES
    Array(l, a, s, e, r),  // LASER
    Array(s, a, i, l, s),  // SAILS
    Array(s, h, e, e, t),  // SHEET
    Array(s, t, e, e, r),  // STEER
    Array(h, e, e, l, 0),  // HEEL
    Array(h, i, k, e, 0),  // HIKE
    Array(k, e, e, l, 0),  // KEEL
    Array(k, n, o, t, 0),  // KNOT
    Array(l, i, n, e, 0),  // LINE
    Array(a, f, t, 0, 0),  // AFT
    Array(a, l, e, 0, 0),  // ALE
    Array(e, e, l, 0, 0),  // EEL
    Array(l, e, e, 0, 0),  // LEE
    Array(t, i, e, 0, 0))  // TIE

  val num_overlapping = 12
  val overlapping = Array(
    Array(0, 2, 1, 0), Array(0, 4, 2, 0),
    Array(3, 1, 1, 2), Array(3, 2, 4, 0), Array(3, 3, 2, 2),
    Array(6, 0, 1, 3), Array(6, 1, 4, 1), Array(6, 2, 2, 3),
    Array(7, 0, 5, 1), Array(7, 2, 1, 4), Array(7, 3, 4, 2), Array(7, 4, 2, 4))

  val N = 8
  val A = Array.fill(15, 5)(CPIntVar(0 to 26))
  val A_flatten = A.flatten
  val E = Array.fill(N)(CPIntVar(0 to 15))

  add(allDifferent(E))

  for (i <- 0 until 15; j <- 0 until 5)
    add(A(i)(j) == AA(i)(j))

  for (i <- 0 until num_overlapping) {
    add(
      A_flatten(E(overlapping(i)(0)) * 5 + overlapping(i)(1))
        ==
        A_flatten(E(overlapping(i)(2)) * 5 + overlapping(i)(3)),
      CPPropagStrength.Strong
    )
  }

  search(binaryStatic(E))

  onSolution {
    println("E: " + E.mkString(" "))
    for (ee <- 0 until N) {
      print(ee + ": (" + "%2d".format(E(ee).value) + ") ")
      for (ii <- 0 until 5)
        print(alpha(A(ee)(ii).value))
      println()
    }
  }

  val stats = start()
  println(stats)
}

🌘 Références

• OscaR — bibliothèque Scala de recherche opérationnelle
• LINUQ — Groupe d’utilisateurs Linux de l’UQ
• SBT — Scala Build Tool
• Programmation par contraintes sur Wikipédia