build.sbt

scalaVersion := "3.5.1-RC2"

SudokuSolver.scala

import scala.compiletime.ops.boolean.&&
import scala.compiletime.ops.boolean
import scala.compiletime.ops.int
import scala.compiletime.ops.any

type ToSquare = (
  0, 0, 0, 1, 1, 1, 2, 2, 2,
  0, 0, 0, 1, 1, 1, 2, 2, 2,
  0, 0, 0, 1, 1, 1, 2, 2, 2,
  3, 3, 3, 4, 4, 4, 5, 5, 5,
  3, 3, 3, 4, 4, 4, 5, 5, 5,
  3, 3, 3, 4, 4, 4, 5, 5, 5,
  6, 6, 6, 7, 7, 7, 8, 8, 8,
  6, 6, 6, 7, 7, 7, 8, 8, 8,
  6, 6, 6, 7, 7, 7, 8, 8, 8
)

type Val1[A <: Int, All <: Tuple] <: Tuple =
  Tuple.Take[
    Tuple.Drop[
      All,
      int.*[
        int.%[A, 9],
        9
      ]
    ],
    9
  ]

type Val2[A <: Int, All <: Tuple] <: Tuple =
  (
    Tuple.Elem[All, int.+[0 , int.%[A, 9]]],
    Tuple.Elem[All, int.+[9 , int.%[A, 9]]],
    Tuple.Elem[All, int.+[18, int.%[A, 9]]],
    Tuple.Elem[All, int.+[27, int.%[A, 9]]],
    Tuple.Elem[All, int.+[36, int.%[A, 9]]],
    Tuple.Elem[All, int.+[45, int.%[A, 9]]],
    Tuple.Elem[All, int.+[54, int.%[A, 9]]],
    Tuple.Elem[All, int.+[63, int.%[A, 9]]],
    Tuple.Elem[All, int.+[72, int.%[A, 9]]]
  )

type Val3[A <: Int, All <: Tuple] <: Tuple =
  Tuple.Map[
    Tuple.Filter[
      Tuple.Zip[
        All,
        Tuple.Map[ToSquare, [n] =>> any.==[n, Tuple.Elem[ToSquare, A]]]
      ],
      FilterByEleme2
    ],
    TupleHead
  ]

type TupleHead[A] =
  A match {
    case a1 *: a2 =>
      a1
  }

type FilterByEleme2[A] <: Boolean =
  A match {
    case (a1, a2) =>
      any.==[true, a2]
  }

type Sudoku[A <: Tuple] <: Tuple = A match {
  case (
    _1_1 *: _1_2 *: _1_3 *: _1_4 *: _1_5 *: _1_6 *: _1_7 *: _1_8 *: _1_9 *:
    _2_1 *: _2_2 *: _2_3 *: _2_4 *: _2_5 *: _2_6 *: _2_7 *: _2_8 *: _2_9 *:
    _3_1 *: _3_2 *: _3_3 *: _3_4 *: _3_5 *: _3_6 *: _3_7 *: _3_8 *: _3_9 *:
    _4_1 *: _4_2 *: _4_3 *: _4_4 *: _4_5 *: _4_6 *: _4_7 *: _4_8 *: _4_9 *:
    _5_1 *: _5_2 *: _5_3 *: _5_4 *: _5_5 *: _5_6 *: _5_7 *: _5_8 *: _5_9 *:
    _6_1 *: _6_2 *: _6_3 *: _6_4 *: _6_5 *: _6_6 *: _6_7 *: _6_8 *: _6_9 *:
    _7_1 *: _7_2 *: _7_3 *: _7_4 *: _7_5 *: _7_6 *: _7_7 *: _7_8 *: _7_9 *:
    _8_1 *: _8_2 *: _8_3 *: _8_4 *: _8_5 *: _8_6 *: _8_7 *: _8_8 *: _8_9 *:
    _9_1 *: _9_2 *: _9_3 *: _9_4 *: _9_5 *: _9_6 *: _9_7 *: _9_8 *: _9_9 *: EmptyTuple
  ) =>

  any.==[F2[A], A] match {
    case true =>
      A // 変化なし。解き終わったか、解けない
    case false =>
      Sudoku[F2[A]] // 変化あり。一部が埋まったはずで、さらに進行可能かもしれないので、再帰
  }
}

type Range81 = Range[81]

type F2[A <: Tuple] = A match {
  case _ =>
    Tuple.Map[
      Range81,
      [x] =>> F1[A, x]
    ]
}

type Range[N <: Int] = N match {
  case _ =>
    Range0[int.-[N, 1], EmptyTuple]
}

type Range0[N <: Int, Acc <: Tuple] <: Tuple =
  N match {
    case -1 =>
      Acc
    case _ =>
      Range0[int.-[N, 1], N *: Acc]
  }

type F1[All <: Tuple, X <: Int] =
  any.!=[Tuple.Elem[All, X], Placeholder] match {
    case true =>
      Tuple.Elem[All, X]
    case false =>
      F[All, X] match {
        case n *: EmptyTuple =>
          n
        case _ =>
          F[All, X]
      }
  }

type F[All <: Tuple, X <: Int] =
  Tuple.Filter[
    Numbers,
    [n] =>>
      Tuple.Contains[Unused[Val1[X, All]], n] &&
      Tuple.Contains[Unused[Val2[X, All]], n] &&
      Tuple.Contains[Unused[Val3[X, All]], n]
]

type Placeholder = " "
type - = Placeholder

type Numbers = (1, 2, 3, 4, 5, 6, 7, 8, 9)

type Unused[XS <: Tuple] =
  Tuple.Filter[Numbers, [x] =>> boolean.![Tuple.Contains[XS, x]]]
object Main {
  def main(args: Array[String]): Unit = {
    summon[
      Val1[0, Problem1] =:= (
        (- , 3 , - ,   - , - , - ,   - , - , -)
      )
    ]
    summon[
      Val2[0, Problem1] =:= (
        (- , - , - ,   8 , 4 , - ,   - , - , -)
      )
    ]
    summon[
      Val3[0, Problem1] =:= (
        (- , 3 , - ,   - , - , - ,   - , - , 8)
      )
    ]

    summon[F[Problem1, 0] =:= (1, 2, 5, 6, 7, 9)]
    summon[F[Problem1, 1] =:= (2, 4, 7)]
    summon[F[Problem1, 7] =:= (2 *: EmptyTuple)]
    summon[F[Problem1, 9] =:= (1, 2, 5, 6, 7, 9)]
    summon[F[Problem1, 80] =:= 4 *: EmptyTuple]

    summon[F1[Problem1, 0] =:= (1, 2, 5, 6, 7, 9)]
    summon[F1[Problem1, 1] =:= 3]
    summon[F1[Problem1, 7] =:= 2]
    summon[F1[Problem1, 9] =:= (1, 2, 5, 6, 7, 9)]
    summon[F1[Problem1, 80] =:= 4]

    summon[Range[9] =:= (0, 1, 2, 3, 4, 5, 6, 7, 8)]

    summon[
      Sudoku[Problem2] =:= (
        3, 2, 4,  1, 8, 7,  5, 6, 9,
        8, 9, 1,  4, 5, 6,  3, 7, 2,
        5, 6, 7,  2, 9, 3,  8, 4, 1,

        7, 8, 6,  5, 2, 9,  1, 3, 4,
        2, 5, 9,  3, 1, 4,  7, 8, 6,
        1, 4, 3,  6, 7, 8,  2, 9, 5,

        4, 7, 2,  9, 3, 1,  6, 5, 8,
        6, 3, 5,  8, 4, 2,  9, 1, 7,
        9, 1, 8,  7, 6, 5,  4, 2, 3
      )]
  }
}


type Problem1 = (
  -, 3, -,  -, -, -,  -, -, -,
  -, -, -,  1, 9, 5,  -, -, -,
  -, -, 8,  -, -, -,  -, 6, -,

  8, -, -,  -, 6, -,  -, -, -,
  4, -, -,  8, -, -,  -, -, 1,
  -, -, -,  -, 2, -,  -, -, -,

  -, 6, -,  -, -, -,  2, 8, 9,
  -, -, -,  4, 1, 9,  6, 3, 5,
  -, -, -,  -, -, -,  -, 7, -,
)

type Problem2 = (
  3, 2, 4,  1, 8, 7,  5, 6, 9,
  8, 9, 1,  4, 5, 6,  3, 7, 2,
  5, 6, 7,  2, 9, 3,  8, 4, 1,

  7, 8, 6,  5, 2, 9,  1, 3, 4,
  2, 5, 9,  3, 1, 4,  7, 8, 6,
  1, 4, 3,  6, 7, 8,  2, 9, 5,

  4, 7, 2,  9, 3, 1,  6, 5, 8,
  6, -, 5,  8, 4, 2,  9, 1, 7,
  9, 1, 8,  7, 6, 5,  4, 2, 3
)