Scala 3 match type sudoku solver

build.sbt

scalaVersion := "3.5.1-RC2"

SudokuSolver.scala

import scala.compiletime.ops.boolean.&&
import scala.compiletime.ops.boolean
import scala.compiletime.ops.string
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.Take[
    Tuple.Drop[
      All,
      int.*[
        int./[A, 9],
        9
      ]
    ],
    9
  ]

type Val2[A <: Int, All <: Tuple] <: Tuple = A match {
  case _ =>

    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]]] *:
    EmptyTuple
}

type Val3[A <: Int, All <: Tuple] <: Tuple = A match {
  case _ =>
    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 = Tuple.Size[A] match {
  case 81 =>
    any.==[AsString[F2[A]], AsString[A]] match {
      case true =>
        A // 変化なし。解き終わったか、解けない
      case false =>
        Sudoku[F2[A]] // 変化あり。一部が埋まったはずで、さらに進行可能かもしれないので、再帰
    }
}

type AsString[A <: Tuple] = AsString0[A, ""]

type AsString0[A <: Tuple, Acc <: String] <: String = A match {
  case x *: xs =>
    AsString0[xs, string.+[Acc, any.ToString[x]]]
  case EmptyTuple =>
    Acc
}

type Range81 = Range[81]

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

type Range[N <: Int] <: Tuple = 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 _ =>
          Placeholder
      }
  }

type F[All <: Tuple, X <: Int] <: Tuple = X match {
  case _ =>
    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 {
  summon[Sudoku[Problem1] =:= Answer1]
}

type Answer1 = (
  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 = (
  -, 2, 4,  1, 8, 7,  5, 6, 9,
  8, 9, 1,  4, 5, 6,  3, -, 2,
  5, 6, 7,  2, 9, 3,  8, 4, 1,

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

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