<a id="数独"></a>
# 数独




:::{container} prog-cpp
**数独**は $9\times 9$ のマス目に 1 から 9 の数字を入れるパズルで,以下の条件をすべて満たす必要があります:

- 各行に 1 から 9 がちょうど 1 回ずつ現れる.
- 各列に 1 から 9 がちょうど 1 回ずつ現れる.
- 9 個の $3\times 3$ のブロックそれぞれに 1 から 9 がちょうど 1 回ずつ現れる.

問題には初期ヒント (clues) としていくつかのマスにあらかじめ数字が入っており,残りの空きマスを上記の制約を満たすように埋めます.

<a id="1-hot 符号化による QUBO 定式化"></a>
## 1-hot 符号化による QUBO 定式化

3 次元のバイナリ変数 $X=(x_{i,j,k})$ ($0\leq i, j, k \leq 8$) を用い,$x_{i,j,k}=1$ をマス $(i, j)$ に数字 $k+1$ が入ることを表す **1-hot 符号化**を採用します.
各マスは 1 つの数字を持つので,軸 $k$ 方向に常にちょうど 1 つだけ $1$ が立ちます.

以下の制約を課します:

- 各マスは 1 つの数字を持つ:

$$
\begin{aligned}
\sum_{k=0}^{8} x_{i,j,k}=1 && (0\leq i,j \leq 8)
\end{aligned}
$$

- 各行に各数字がちょうど 1 回ずつ:

$$
\begin{aligned}
\sum_{j=0}^{8} x_{i,j,k}=1 && (0\leq i,k \leq 8)
\end{aligned}
$$

- 各列に各数字がちょうど 1 回ずつ:

$$
\begin{aligned}
\sum_{i=0}^{8} x_{i,j,k}=1 && (0\leq j,k \leq 8)
\end{aligned}
$$

- 各 $3\times 3$ ブロックに各数字がちょうど 1 回ずつ:

$$
\begin{aligned}
\sum_{i=3b_r}^{3b_r+2}\sum_{j=3b_c}^{3b_c+2} x_{i,j,k}=1 && (0\leq b_r, b_c\leq 2,\ 0\leq k \leq 8)
\end{aligned}
$$

これらの等式制約を二乗ペナルティの和としてQUBO式 $f$ を構築します.$f=0$ を達成する変数割り当てが数独の解です.

<a id="ヒントによる変数固定"></a>
## ヒントによる変数固定

初期ヒントは追加のペナルティとして与えるのではなく,変数を直接固定 (1 または 0 に置換) します.
ヒントによってマス $(i, j)$ が数字 $v$ と分かっている場合:

$$
\begin{aligned}
x_{i,j,v-1} &= 1 && \text{(マス $(i, j)$ は数字 $v$ である)}\\
x_{i,j,k} &= 0 && \text{($k \ne v-1$,マス $(i, j)$ は数字 $v$ 以外ではない)}\\
x_{i,j',v-1} &= 0 && \text{($j' \ne j$,同じ行のほかのマスは $v$ ではない)}\\
x_{i',j,v-1} &= 0 && \text{($i' \ne i$,同じ列のほかのマスは $v$ ではない)}\\
x_{i',j',v-1} &= 0 && \text{($(i', j')$ が同じ $3\times 3$ ブロック,ほかのマスは $v$ ではない)}
\end{aligned}
$$

これらの強制値を `qbpp::MapList` に集めて `qbpp::replace` に渡すと,QUBO式から該当する変数が消え,ソルバが扱う変数の数が大幅に削減されます.

<a id="Hi-QUBO プログラム"></a>
## Hi-QUBO プログラム

以下の Hi-QUBO プログラムは,上記の制約をもとにQUBO式を構築し,ヒントによる変数固定後に EasySolver で解きます:

```{literalinclude} /../programFiles/cppPrograms/example/puzzle/sudoku-program1.cpp
:language: cpp
:caption: sudoku-program1.cpp
```


`qbpp::var("x", 9, 9, 9)` は形状 $(9, 9, 9)$ のバイナリ変数の 3 次元配列 `x` を生成します.

`sudoku_expr` 関数は以下のスライス記法と `qbpp::sum`,`== 1` 構文を用いて 4 種類の等式制約に対応する二乗ペナルティを構築します:
- `x(i, j, qbpp::all)` はマス $(i, j)$ の 9 個の変数からなる軸 $k$ 方向のベクトル.
- `x(i, qbpp::all, k)` は行 $i$ で数字 $k+1$ に対応する 9 個の変数のベクトル.
- `x(qbpp::all, j, k)` は列 $j$ で数字 $k+1$ に対応する 9 個の変数のベクトル.
- `x(qbpp::slice(3*br, 3*br+3), qbpp::slice(3*bc, 3*bc+3), k)` は $3\times 3$ ブロックで数字 $k+1$ に対応する 9 個の変数の 2 次元配列.

これらに `qbpp::sum(...) == 1` を適用すると,対応する和が 1 のとき 0 となる二乗ペナルティ式が得られます.

`fix_variables` 関数は,ヒントに対して上記の固定値 (1 または 0) を `qbpp::MapList` に集めます.
同じ変数に複数回書き込みが発生し得るため,`std::unordered_set<qbpp::vindex_t>` で既出をチェックし,最初の書き込みのみ `emplace_back` します.マス自身に対する書き込みを先に処理することで,ヒントの「= 1」の値が他のヒントの近傍規則による「= 0」より優先されます.

`qbpp::replace(f, sub)` は,`sub` に含まれる各変数を対応する定数 (0 または 1) で置換した新しい式 `g` を返します.これにより `g` から固定された変数が消え,`g.simplify_as_binary()` で簡約することで `g` の変数の数と項数が大幅に減少します.

`qbpp::EasySolver(g)` で `g` をソルバに渡し,{% raw %}`search({{"target_energy", 0}})`{% endraw %} で目標エネルギー 0 を達成する解 `sol` を求めます.
`g` には空きマスに対応する変数しか含まれていないため,`sol` も空きマスの値のみを保持しています.
ヒントを含む完全な解は `qbpp::Sol(f).set(sol, sub)` で構築します.
これは,もとの式 `f` のすべての変数を含む新しい `Sol` を作り,まず `sol` の値をコピーし,続けて `sub` の固定値を反映するイディオムです.

最後に,`full_sol(x)` で 3 次元の 0/1 配列を得て,`qbpp::onehot_to_int` で軸 $k$ 方向の 1-hot を整数 $(0,\ldots,8)$ に復号し,`print_sudoku` で `+1` した値を出力します.

実行すると,ヒント (`.` が空きマス) と求めた解が以下のように表示されます:

```{include} /../programFiles/markDown/example/puzzle/sudoku.md
:start-after: <!-- begin: Hi-QUBO プログラム -->
:end-before: <!-- end: Hi-QUBO プログラム -->
```
:::




:::{container} prog-python
**数独**は $9\times 9$ のマス目に 1 から 9 の数字を入れるパズルで,以下の条件をすべて満たす必要があります:

- 各行に 1 から 9 がちょうど 1 回ずつ現れる.
- 各列に 1 から 9 がちょうど 1 回ずつ現れる.
- 9 個の $3\times 3$ のブロックそれぞれに 1 から 9 がちょうど 1 回ずつ現れる.

問題には初期ヒント (clues) としていくつかのマスにあらかじめ数字が入っており,残りの空きマスを上記の制約を満たすように埋めます.

<a id="1-hot 符号化による QUBO 定式化"></a>
## 1-hot 符号化による QUBO 定式化

3 次元のバイナリ変数 $X=(x_{i,j,k})$ ($0\leq i, j, k \leq 8$) を用い,$x_{i,j,k}=1$ をマス $(i, j)$ に数字 $k+1$ が入ることを表す **1-hot 符号化**を採用します.
各マスは 1 つの数字を持つので,軸 $k$ 方向に常にちょうど 1 つだけ $1$ が立ちます.

以下の制約を課します:

- 各マスは 1 つの数字を持つ:

$$
\begin{aligned}
\sum_{k=0}^{8} x_{i,j,k}=1 && (0\leq i,j \leq 8)
\end{aligned}
$$

- 各行に各数字がちょうど 1 回ずつ:

$$
\begin{aligned}
\sum_{j=0}^{8} x_{i,j,k}=1 && (0\leq i,k \leq 8)
\end{aligned}
$$

- 各列に各数字がちょうど 1 回ずつ:

$$
\begin{aligned}
\sum_{i=0}^{8} x_{i,j,k}=1 && (0\leq j,k \leq 8)
\end{aligned}
$$

- 各 $3\times 3$ ブロックに各数字がちょうど 1 回ずつ:

$$
\begin{aligned}
\sum_{i=3b_r}^{3b_r+2}\sum_{j=3b_c}^{3b_c+2} x_{i,j,k}=1 && (0\leq b_r, b_c\leq 2,\ 0\leq k \leq 8)
\end{aligned}
$$

これらの等式制約を二乗ペナルティの和としてQUBO式 $f$ を構築します.$f=0$ を達成する変数割り当てが数独の解です.

<a id="ヒントによる変数固定"></a>
## ヒントによる変数固定

初期ヒントは追加のペナルティとして与えるのではなく,変数を直接固定 (1 または 0 に置換) します.
ヒントによってマス $(i, j)$ が数字 $v$ と分かっている場合:

$$
\begin{aligned}
x_{i,j,v-1} &= 1 && \text{(マス $(i, j)$ は数字 $v$ である)}\\
x_{i,j,k} &= 0 &&\text{($k \ne v-1$,マス $(i, j)$ は数字 $v$ 以外ではない)}\\
x_{i,j',v-1} &= 0 &&\text{($j' \ne j$,同じ行のほかのマスは $v$ ではない)}\\
x_{i',j,v-1} &= 0 &&\text{($i' \ne i$,同じ列のほかのマスは $v$ ではない)}\\
x_{i',j',v-1} &= 0 &&\text{($(i', j')$ が同じ $3\times 3$ ブロック,ほかのマスは $v$ ではない)}
\end{aligned}
$$

これらの強制値を辞書 `{Var: 0 or 1}` に集めて `qbpp.replace` に渡すと,QUBO式から該当する変数が消え,ソルバが扱う変数の数が大幅に削減されます.

<a id="PyQBPP プログラム"></a>
## PyQBPP プログラム

以下の PyQBPP プログラムは,上記の制約をもとにQUBO式を構築し,ヒントによる変数固定後に EasySolver で解きます:

```{literalinclude} /../programFiles/pythonPrograms/example/puzzle/sudoku-program1.py
:language: python
:caption: sudoku-program1.py
```


`qbpp.var("x", 9, 9, 9)` は形状 $(9, 9, 9)$ のバイナリ変数の 3 次元配列 `x` を生成します.

`sudoku_expr` 関数は以下のスライス記法と `qbpp.sum`,`== 1` 構文を用いて 4 種類の等式制約に対応する二乗ペナルティを構築します:
- `x[i, j, :]` はマス $(i, j)$ の 9 個の変数からなる軸 $k$ 方向のベクトル.
- `x[i, :, k]` は行 $i$ で数字 $k+1$ に対応する 9 個の変数のベクトル.
- `x[:, j, k]` は列 $j$ で数字 $k+1$ に対応する 9 個の変数のベクトル.
- `x[3*br:3*br+3, 3*bc:3*bc+3, k]` は $3\times 3$ ブロックで数字 $k+1$ に対応する 9 個の変数の 2 次元配列.

これらに `qbpp.sum(...) == 1` を適用すると,対応する和が 1 のとき 0 となる二乗ペナルティ式が得られます.

`fix_variables` 関数は,ヒントに対して上記の固定値 (1 または 0) を辞書 `sub` に集めます.Python の辞書は同一キーへの再代入を自然に扱えるため,マス自身に対する値は `sub[...] = ...` で常に上書きし,行・列・ブロックの近傍に対する 0 は `sub.setdefault(...)` で既存値を上書きしないようにします.これにより,ヒントの「= 1」の値が他のヒントの近傍規則による「= 0」より優先されます.

`qbpp.replace(f, sub)` は,`sub` に含まれる各変数を対応する定数 (0 または 1) で置換した新しい式 `g` を返します.これにより `g` から固定された変数が消え,`g.simplify_as_binary()` で簡約することで `g` の変数の数と項数が大幅に減少します.

`qbpp.EasySolver(g)` で `g` をソルバに渡し,`solver.search(target_energy=0)` で目標エネルギー 0 を達成する解 `sol` を求めます.
`g` には空きマスに対応する変数しか含まれていないため,`sol` も空きマスの値のみを保持しています.
ヒントを含む完全な解は `qbpp.Sol(f).set(sol).set(sub)` で構築します.
これは,もとの式 `f` のすべての変数を含む新しい `Sol` を作り,まず `sol` の値をコピーし,続けて `sub` の固定値を反映するイディオムです.

最後に,`full_sol(x)` で 3 次元の 0/1 配列を得て,`qbpp.onehot_to_int` で軸 $k$ 方向の 1-hot を整数 $(0,\ldots,8)$ に復号し,`print_sudoku` で `+1` した値を出力します.

実行すると,ヒント (`.` が空きマス) と求めた解が以下のように表示されます:

```{include} /../programFiles/markDown/example/puzzle/sudoku.md
:start-after: <!-- begin: PyQBPP プログラム -->
:end-before: <!-- end: PyQBPP プログラム -->
```
:::