型レベルプログラミングでN×Nの数独を解く

型レベルプログラミングの上級者向けの記事です。以前書いた入門者向けの記事はこちら。

TypeScriptの型レベルプログラミングでN×Nの数独を解く型を解説します。

一般に数独は9×9マスですが、１辺のマス目が平方数であればよいので、4×4、16×16などの数独もあります。今回は一般化されたN×Nの数独を解く型について解説します。

理論上の解法としてN×Nが解けるはずですが、16×16については「Loading」が終わらずに答えが確認出来なかったことを先にお伝えしておきます。4×4,9×9の数独はVSCode上で解答が表示出来ることが確認出来ました。

今回作った数独を解く型はこちら。(Solve型は314行目)

プレイグラウンドではすべての型情報は表示されませんが、VSCodeならtsconfig.jsonに"noErrorTruncation": trueを設定するとすべて表示してくれます。

準備

用語について

数独のルールについてWikiから引用します。

基本的なルールは簡単で、下記の3つだけである。

• 空いているマスに、1〜9のいずれかの数字を入れる。
• 縦・横の各列に、同じ数字が重複して入ってはいけない。
• 太線で囲まれた3×3のグループ（以降「ブロック」と呼ぶ）内に、同じ数字が重複して入ってはいけない。

数独を解くためのヘルパーとなる型名は、これらのルールに登場する概念から拝借しています。

概念	型名
横の列	Row
縦の列	Col
太線で囲まれたところ	Block
縦・横の各列、または太線で囲まれたところ	Group

問題設定

また数独の問題はタプル型で受け取ることとします。例えば4×4の問題は次のように定義されます。0は、まだ数字が埋まっていないところです。

type SudokuTest1 = [
  1, 0, 0, 0,
  3, 0, 1, 2,
  4, 3, 0, 1,
  0, 0, 0, 3
]

汎用型

以下の型は数独を解くために限定されない汎用型です。type-challengesなどを参考にしています。

/** ## ネストしたタプルを展開する */
type Flat<Nested extends unknown[], C extends unknown[] = []> =
  Nested extends [
    infer First extends unknown[],
    ...infer Tail extends unknown[]
  ] ? Flat<Tail, [...C, ...First]>
    : C;
type FlatTest = Flat<[[0, 0], [1, 2]]>; // [0, 0, 1, 2]

/** ## 同じ型を要素とするタプル型を生成する */
type Tuple<E, N extends number, C extends E[] = []> =
  C['length'] extends N
  ? C
  : Tuple<E, N, [...C, E]>;
type TupleTest = Tuple<1, 4>; // [1, 1, 1, 1]

/** ## 掛け算 */
type Multiply<N extends number, M extends number> =
  Flat<Tuple<Tuple<1, N>, M>> extends infer F extends 1[]
  ? F['length']
  : never;
type MultiplyTest = Multiply<2, 3>; // 6

/** ## 平方根 */
type SquareRoot<N extends number, C extends 1[] = Tuple<1, N>> =
  Multiply<C['length'], C['length']> extends N
  ? C['length']
  : C extends [1, ...infer Tail extends 1[]]
    ? SquareRoot<N, Tail>
    : never;
type SquareRootTest = SquareRoot<25>; // 5

/** ## 足し算 */
type Add<N extends number, M extends number> =
  [...Tuple<1, N>, ...Tuple<1, M>]['length'];
type AddTest = Add<2, 5>; // 7

/** 要素数Nのタプルを生成する: `[0, 1, ...(N - 1)]` */
type Sequence<N extends number, C extends number[] = []> =
  C['length'] extends N
  ? C
  : Sequence<N, [...C, C['length']]>;
type SequenceTest = Sequence<4>; // [0, 1, 2, 3]

/** 対象タプルから特定の要素を削除 */
type Without<
  T extends unknown[],
  U extends unknown[],
  C extends unknown[] = []
> =
  T extends [infer First, ...infer Tail extends unknown[]]
  ? First extends U[number]
    ? Without<Tail, U, C>
    : Without<Tail, U, [...C, First]>
  : C;
type WithoutTest = Without<[1, 2, 3, 4], [2, 4, 2]>; // [1, 3]

/** タブルのI番目の要素をVに置き換える */
type Replace<
  S extends unknown[],
  I extends number,
  V,
  C extends unknown[] = []
 > =
  S extends [infer First extends unknown, ...infer Tail extends unknown[]]
  ? I extends C['length']
    ? [...C, V, ...Tail]
    : Replace<Tail, I, V, [...C, First]>
  : never;
type ReplaceTest = Replace<[0, 1, 2, 3, 4], 2, 'a'>; // [0, 1, "a", 3, 4]

/**
 * ## ２つのタプル(N, M)の長さを比較する
 * NがMより短ければtrue, そうでなければfalse
 */
type IsLessThanLength<N extends unknown[], M extends unknown[], C extends 1[] = []> =
  C['length'] extends M['length']
  ? false
  : C['length'] extends N['length']
    ? true
    : IsLessThanLength<N, M, [...C, 1]>;
type IsLessThanTest1 = IsLessThanLength<[1, 2], [1, 2, 3]>; // true
type IsLessThanTest2 = IsLessThanLength<[1, 2, 3], [1, 2, 3]>; // false
type IsLessThanTest3 = IsLessThanLength<[1, 2, 3, 4], [1, 2, 3]>; // false

/** ## readonlyを外す */
type Mutable<R extends readonly number[]> = [...R];
const mutableTest = [0, 1, 2] as const;
type MutableTest = Mutable<typeof mutableTest>; // [0, 1, 2]

解説

数独を解く方針として、次の処理を再帰的に実施します。

• 問題の空いているマスのうち候補の数が最も少ないところを探す
  • なければそれが解答
  • 候補の数が最も少ないマスを埋める（複数あればそれぞれ）

これらを処理する型の命名は次の通りとします。

役割	型名
候補の数が最も少ないところを探す	NextTarget
そのマスの候補を計算する	AvailableValues
埋める（複数あればそれぞれ）	ReplaceValues

これらの型がある前提で、数独を解く型は次のように定義されます。

type Solve<Sudoku extends number[]> =
  Sudoku extends Sudoku
  ? NextTarget<Sudoku> extends infer Index extends number
    ? AvailableValues<Sudoku, Index> extends infer Values extends number[]
      ? ReplaceValues<Sudoku, Index, Values> extends infer Next extends number[]
        ? Solve<Next>
        : never
      : never
    : Sudoku
  : never;

これだけなら簡単ですね。
しかしSudoku extends Sudokuは何でしょうか？

このテクニックについても解説します。TypeScriptの公式ドキュメントに仕様が記述されています。私も最近までその仕様の名前(Distributive Conditional Types)について知りませんでした。後ほどReplaceValuesと一緒にそれを紹介したいと思います。

それではそれぞれの型を掘り下げてその実装を考えていきます。

AvailableValues<Sudoku, Index>

数独の問題とマスの場所（インデックス）を与えられれば、そのマスで使用可能な数字をタプルに格納して返します。Solve型に登場する型としては２番目ですが、NextTarget型はAvailableValues型に依存しているので、AvailableValuesから解説します。

AvailableValuesは、次のように処理します。

• 指定のマスが属するグループ(Row, Col, Block)を計算
• それらのグループで使用されていない数をタプルで返す

役割	型名
Rowのグループマップ	RowMap
Colのグループマップ	ColMap
Blockのグループマップ	BlockMap
インデックスの属するグループで使用されている数字をタプルで返す	Group
使用されている数字のタプルから未使用の数字をタプルで返す	UnusedNumbers

これらの型が定義済みの前提で、AvailableValuesは次のように定義されます。

/** ## 指定のインデックスで使用可能な数字 */
type AvailableValues<Sudoku extends number[], I extends number> =
  SquareRoot<Sudoku['length']> extends infer N extends number
  ? RowGroupMap<N> extends infer RM extends number[]
  ? ColGroupMap<N> extends infer CM extends number[]
  ? BlockGroupMap<N> extends infer BM extends number[]
  ? Group<Sudoku, I, RM> extends infer RG extends number[]
  ? Group<Sudoku, I, CM> extends infer CG extends number[]
  ? Group<Sudoku, I, BM> extends infer BG extends number[]
  ? UnusedNumbers<N, [...RG, ...CG, ...BG]>
  : never : never : never : never : never : never : never;

今回は9×9の数独だけではなく一般化したN×Nの数独を解ける型を考えているので、まずはSudokuの問題のタプルの長さからNを求めています。そして縦の列、横の列、ブロックごとのグループを判断するための地図を作成し、それらの地図を使用して指定のインデックスで使用されている数字を抽出し、最後にUnusedNumbers型で使用していない数字をタプルで返します。

それぞれの型をさらに掘り下げていきます。

RowGroupMap<N>

/**
 * ## RowGroupMap
 * 数独のマスを次のようにグループ化する。
 * ```
 * [
 *   0, 0, 0, 0,
 *   1, 1, 1, 1,
 *   2, 2, 2, 2,
 *   3, 3, 3, 3
 * ]
 * ```
 */
type RowGroupMap<N extends number, C extends number[][] = []> =
  C['length'] extends infer RowIndex extends number
  ? RowIndex extends N
    ? Flat<C>
    : RowGroupMap<N, [...C, Tuple<RowIndex, N>]>
  : never;

type RowGroupMap2 = RowGroupMap<2>;
/**
 * [
 *   0, 0,
 *   1, 1
 * ]
 */

type RowGroupMap3 = RowGroupMap<3>;
/**
 * [
 *   0, 0, 0,
 *   1, 1, 1,
 *   2, 2, 2
 * ]
 */

C(Current)には2次元タプルを格納して再起的に処理を進め、最後にFlat型で展開しています。

ColGroupMap<N>

/**
 * ## ColGroupMap
 * 数独のマスを次のようにグループ化する。
 * ```
 * [
 *   0, 1, 2, 3,
 *   0, 1, 2, 3,
 *   0, 1, 2, 3,
 *   0, 1, 2, 3
 * ]
 * ```
 */
type ColGroupMap<N extends number, C extends number[][] = []> =
  C['length'] extends N
  ? Flat<C>
  : ColGroupMap<N, [...C, Sequence<N>]>;

type ColGroupMap2 = ColGroupMap<2>;
/**
 * [
 *   0, 1,
 *   0, 1
 * ]
 */

type ColGroupMap3 = ColGroupMap<3>;
/**
 * [
 *   0, 1, 2,
 *   0, 1, 2,
 *   0, 1, 2
 * ]
 */

RowGroupMapと同じように2次元タプル(C)を最後に展開しています。

BlockGroupMap<N>

/**
 * ## BlockGroupMap
 * 数独のマスを次のようにグループ化する。
 * ```
 * [
 *   0, 0, 1, 1,
 *   0, 0, 1, 1,
 *   2, 2, 3, 3,
 *   2, 2, 3, 3
 * ]
 * ```
 * ※BlockGroupMapは_BlockGroupMapで必要な型を生成する役割のみ。
 */
type BlockGroupMap<N extends number> =
  SquareRoot<N> extends infer Root extends number
  ? SquareInSquare<Root> extends infer SS extends number[][][][]
    ? _BlockGroupMap<Root, SS>
    : never
  : never;

type BlockMap4 = BlockGroupMap<4>; // 平方数しか受け付けられない
/**
 * [
 *   0, 0, 1, 1,
 *   0, 0, 1, 1,
 *   2, 2, 3, 3,
 *   2, 2, 3, 3
 * ]
 */

type BlockMap9 = BlockGroupMap<9>;
/**
 * [
 *   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
 * ]

RowGroupMap、ColGroupMapはとても簡単に定義できましたが、BlockGroupMapは面倒です。
詳しくは定義全体を見ていただいて、ここでは方針だけざっくり解説します。

N×Nの数独の、Nの平方根をR(Root)とすると、ブロック１つはR×Rのマスです。BlockGroupMapはR×RのブロックをR×Rだけ敷き詰めたものです。平方根はSquareRoot、R×R×R×Rの４次元タプルの生成はSquareInSquareで処理しています。その4次元タプルをいい感じに1次元のタプルに展開する処理が_BlockGroupMapです。

BlockGroupMapを成立させるために6つの型を定義していて、もう少しシンプルに出来ないかな？と思うところです。もしアイディアあればコメント下さい。

BlockGroupMapに必要な型

/** ## 要素TのN×Nの２次元タプル */
type ToSquare<T, N extends number, S extends T[][] = []> =
  S['length'] extends N
  ? S
  : ToSquare<T, N, [...S, Tuple<T, N>]>;

type ToSquareTest = ToSquare<1, 2>; // [[1, 1], [1, 1]]

/** 
 * ## RowOfSS<R, RowIndex>
 * SquareInSquareの行部分 （SquareInSquareのコメントをご覧ください）
 */
type RowOfSS<R extends number, RowIndex extends number, C extends number[][][] = []> =
  C['length'] extends R
  ? C
    : ToSquare<Add<Multiply<RowIndex, R>, C['length']>, R> extends infer S extends number[][]
    ? RowOfSS<R, RowIndex, [...C, S]>
  : never;

type RowInSquareTest = RowOfSS<2, 1>; // [[[2, 2], [2, 2]], [[3, 3], [3, 3]]]

/** 
 * ## SquareInSquare
 * R(Root)=2の場合、次のようになる。
 * ```
 * [
 *   [[[0, 0], [0, 0]], [[1, 1], [1, 1]]],　← RowOfSS<2, 0>
 *   [[[2, 2], [2, 2]], [[3, 3], [3, 3]]],　← RowOfSS<2, 1>
 * ]
 * ```
 */
type SquareInSquare<R extends number, C extends number[][][][] = []> =
  C['length'] extends R ? C : SquareInSquare<R, [...C, RowOfSS<R, C['length']>]>;

type SquareInSquareTest = SquareInSquare<2>;
/**
 * [
 *   [
 *     [
 *       [0, 0],
 *       [0, 0]
 *     ],
 *     [
 *       [1, 1],
 *       [1, 1]
 *     ]
 *   ],
 *   [
 *     [
 *       [2, 2],
 *       [2, 2]
 *     ],
 *     [
 *       [3, 3],
 *       [3, 3]
 *     ]
 *   ]
 * ]
 */

/** 
 * ## PickRow
 * SquareInSquareからSquareMapの1行を抽出する。
 */
type PickRow<
  R extends number,
  SSRow extends unknown[][][],
  RowIndex extends number,
  C extends unknown[][] = [],
> =
  C['length'] extends infer ColIndex extends number
  ? ColIndex extends R
    ? Flat<C>
    : PickRow<R, SSRow, RowIndex, [...C, SSRow[ColIndex][RowIndex]]>
  : never;
type PickRow0 = PickRow<2, SquareInSquareTest[0], 0>; // [0, 0, 1, 1]
type PickRow1 = PickRow<2, SquareInSquareTest[0], 1>; // [0, 0, 1, 1]
type PickRow2 = PickRow<2, SquareInSquareTest[1], 0>; // [2, 2, 3, 3]
type PickRow3 = PickRow<2, SquareInSquareTest[1], 1>; // [2, 2, 3, 3]

/**
 * ## SSRowToRow
 * 次のように型を変換する。
 * ```
 * [[['A1', 'A1'], ['A2', 'A2']], [['B1', 'B1'], ['B2', 'B2']]]
 * ↓↓↓↓
 * [["A1", "A1", "B1", "B1"], ["A2", "A2", "B2", "B2"]]
 * ```
 */
type SSRowToRow<R extends number, SSRow extends unknown[][][], C extends unknown[][] = []> =
  C['length'] extends R
  ? C
  : SSRowToRow<R, SSRow, [...C, PickRow<R, SSRow, C['length']>]>;
type SSRowTest1 = [[['A1', 'A1'], ['A2', 'A2']], [['B1', 'B1'], ['B2', 'B2']]];
type RowOfSquareTest = SSRowToRow<2, SSRowTest1>; // [["A1", "A1", "B1", "B1"], ["A2", "A2", "B2", "B2"]]

/**
 * ## _BlockMap
 * SquareMap型を生成する。
 */
type _BlockGroupMap<R extends number, SS extends number[][][][], C extends number[][][] = []> =
  C['length'] extends R
  ? Flat<Flat<C>>
  : _BlockGroupMap<R, SS, [...C, SSRowToRow<R, SS[C['length']]>]>;

type _BlockMapTest = _BlockGroupMap<2, SquareInSquareTest>;
/**
 * [
 *   0, 0, 1, 1,
 *   0, 0, 1, 1,
 *   2, 2, 3, 3,
 *   2, 2, 3, 3
 * ]
 */

Group<Sudoku, Index, GroupMap>

Group型はGroupMapから指定のインデックスのグループのマスの数字をタプルで返します。

/** ## 問題、インデックス、グループマップからグループで使用されている値を抽出 */
type Group<
  Sudoku extends number[],
  Index extends number,
  GroupMap extends number[],
  C extends 1[] = [],
  Result extends number[] = []
> =
  GroupMap['length'] extends C['length']
  ? Result
  : GroupMap[C['length']] extends GroupMap[Index]
    ? Group<Sudoku, Index, GroupMap, [...C, 1], [...Result, Sudoku[C['length']]]>
    : Group<Sudoku, Index, GroupMap, [...C, 1], Result>;

C['length']がループカウンターの役割となっており、受け取ったGroupMapの各要素をインデックスのグループと同じかどうか一つ一つ調べていきます。同じなら[...Result, Sudoku[C['length']]]で使用されている数字をResultに追加します。

UnusedNumbers

/** ## 使用済みの数字から未使用の数字のタプルを生成 */
type UnusedNumbers<N extends number, UsedList extends number[]> =
  Without<[...Sequence<N>, N], UsedList>;

AvailableValuesの締めの処理がUnusedNumbersです。Row, Col, Blockの各グループで使用されている数字から、まだ使用していない数字を判定します。[...Sequence<N>, N]で0からNまでの数字が格納されたタプルを用意し、そこから使用済みのものをWithout型で除きます。

NextTarget<Sudoku>

問題のすべてのマスから次に埋めるべきマスを判定し、そのインデックスを返します。

/** ## 使用可能な数字の数が最も小さいインデックスを返す */
type NextTarget<
  Sudoku extends number[],
  C extends 1[] = [],
  MinIndex extends number | undefined = undefined
> =
  C['length'] extends infer Index extends number
  ? Index extends Sudoku['length'] 
    ? MinIndex // 最後までチェックしたらMinを返す
    : Sudoku[Index] extends 0
      ? MinIndex extends number
        ? IsLessThanLength<
          AvailableValues<Sudoku, Index>,
          AvailableValues<Sudoku, MinIndex>
        > extends true
          // 使用可能な数字の数が、より少ない場合
          ? NextTarget<Sudoku, [...C, 1], Index>
          // 使用可能な数字の数が、同じか多い場合
          : NextTarget<Sudoku, [...C, 1], MinIndex>
        // Sudoku[Index]が埋まっていない && MinIndexもない(undefined)
        : NextTarget<Sudoku, [...C, 1], Index>
      // // Sudoku[Index]が埋まっているs
      : NextTarget<Sudoku, [...C, 1], MinIndex>
  : never;

MinIndexはundefinedで処理をスタートします。MinIndexがundefinedの場合に埋まっていないマスがあればそのインデックスを保持し、さらに保持しているインデックスよりも使用可能な数字の数が小さなマスがあれば、そのインデックスを保持します。そして最後にMinIndexを返します。

ReplaceValues<Sudoku, Index, Values>

ここでもう一度Solve型を振り返っておきましょう。

type Solve<Sudoku extends number[]> =
  Sudoku extends Sudoku
  ? NextTarget<Sudoku> extends infer Index extends number
    ? AvailableValues<Sudoku, Index> extends infer Values extends number[]
      ? ReplaceValues<Sudoku, Index, Values> extends infer Next extends number[]
        ? Solve<Next>
        : never
      : never
    : Sudoku
  : never;

Solve型は、まずNextTarget型で次に埋めるマスを計算し、次にAvailableValues型でそのマスに使用できる数字を計算しています。そしてReplaceValues型でSudokuのマスを１つ埋めたNext(Sudoku)をSolve型に渡して再帰的に処理を進めます。

ReplaceValuesに必要な処理を理解したところで、ReplaceValuesは次のように定義しました。

/** タブルのI番目の要素をVの要素で置き換えたUnion型にする */
type ReplaceValues<Sudoku extends unknown[], Index extends number, Values extends unknown[]> =
  Values extends [infer First extends unknown, ...infer Tail extends unknown[]]
  ? (Replace<Sudoku, Index, First> | ReplaceValues<Sudoku, Index, Tail>)
  : never;

AvailableValuesで複数の候補がある場合には並行して処理するために、SudokuをValuesの数だけ交差型で返しています。

はい、ここで後回しにしていたSudoku extends Sudokuのテクニックについて紹介します。私はこちらでこのテクニックを見つけました。

296 - Permutation (with explanations) #614

これはDistributive Conditional TypesというTypeScriptの仕様を使ったテクニックです。

公式ドキュメントで紹介されている次のコードが分かりやすいです。

type ToArray<Type> = Type extends any ? Type[] : never;
 
type StrArrOrNumArr = ToArray<string | number>; //string[] | number[]

つまりKが交差型のジェネリクスである場合、K extends Kを記述することで、ユニオンされたそれぞれの型が分配されて型が計算され、その計算された型がユニオンとして扱われます。Sudoku extends Sudokuを書かない場合には交差型のうち１つだけを処理してしまい、2つの答えを持つ問題の場合でも1つの答えしか出せません。

K extends Kのテクニックによって2つの答えが出せることをプレイグラウンドでも確認出来ます。

以上でSolve型の解説はお終いです。

おまけ: satisfiesを使ってみた

TypeScript4.9からsatisfiesというオペレーターが使用できます。より安全にコードが書けるようになる代物です。詳しい説明は他の記事に任せたいと思いますが、今回、数独の問題となる型を安全に定義するために使用してみました。

/** ## 数独の空欄(プレイスホルダー)を0で表現 */
type Placeholder = 0;

/** ## 数独で使用する数字の交差型 `1 | 2 | ... | N` */
type Num<N extends number, C extends number[] = []> =
  C['length'] extends N
  ? C[number]
  : [...C, 0]['length'] extends infer LengthPlus1 extends number
    ? Num<N, [...C, LengthPlus1]>
    : never;
type Num4 = Num<4>;

/** ## プレイスホルダーと数独で使用する数字の交差型 */
type Mix<N extends number> = Placeholder | Num<N>;
type Mix4 = Mix<4>;

/** ## 数独の問題を`satisfies`で安全に定義するための型 */
type SudokuType<N extends number, C extends Tuple<Mix<N>, N>[] = []> =
  C['length'] extends N
  ? Readonly<Flat<C>>
  : Sudoku<N, [...C, Tuple<Mix<N>, N>]>;
type Sudoku4 = SudokuType<4>;

Sudoku型は一辺のマスの数を与えると、タプルの長さ、使用する要素の種類についてチェックしてくれます。

このSudoku型を次のように使います。

const sudoku4Test1 = [
  1, 0, 0, 0,
  3, 0, 1, 2,
  4, 3, 0, 1,
  0, 0, 0, 3,
] as const satisfies Sudoku4;
type Sudoku4Test1 = Mutable<typeof sudoku4Test1>;
type Solve4Test1 = Solve<Sudoku4Test1>;

例えば、sudoku4Test1型の最後の要素が欠けていると次のように教えてくれます。

satisfiesの登場によってこれまで以上に安全なコードが書きやすくなったと言えるでしょう。

今回のケースでは、例えばSudoku型をRow, Col, Blockの各グループの重複チェックまで実施するような厳しい型にするといったことも可能です。私にとっては数独の問題をコードに打ち込む際に間違えなければOKだと考えて重複チェックの機能は省きましたが、コードの寿命や使用頻度によってはガチガチに型安全にするという判断もありそうですね。

以上、型レベルプログラミングでN×Nの数独を解く解説でした。