D-Waveに、とても便利な例題が沢山収録されているライブラリがありました。この中で数独を見てみましょう。
https://github.com/dwave-examples
数独
https://github.com/dwave-examples/sudoku
こちらになります。
ツール
ツールはD-Waveから提供されているD-Wave Oceanというものを利用できます。ダウンロードの上ご利用ください。
https://docs.ocean.dwavesys.com/en/stable/
pip経由でのインストールは、
pip install dwave-ocean-sdk
となります。
コード
先にコードをみましょう。メインのコードはこちらから手に入ります。
https://github.com/dwave-examples/sudoku/blob/master/sudoku.py
コード自体はとてもシンプルでわかりやすいものです。数独の満たすべき問題を式の形で実装し、ファイルを指定することで、式を自動的に作って解いてくれます。解く際に利用するのはD-Waveのマシンですが、ここではKerberosというハイブリッドシステムを利用していますので、そこだけ注意が必要です。
ハイブリッドアルゴリズム
解くまえに、Kerberosについてです。KerberosはハイブリッドソルバーでD-Waveを使った場合と使わない場合を複数計算をします。また、今回の数独問題は量子ビット数が700近く必要ですので、2020現在のD-Waveの最新マシンであるAdvantage System1.1であっても、一度で解くことはできません。ですので問題分割が利用されており、それによって多少前後処理の時間がかかります。
手順
問題を解く手順
１、問題の読み込み。問題が指定されない場合にはサンプルファイル
２、問題から定式化
３、Kerberosサンプラーに投入
４、答えをもらって、チェック
となります。数独は出てきた答えがあっているのかチェックが容易ですので、楽ですね。
実際にやってみると、今回はKerberosではなく、一部を改造してLeapHybridで実行してみました。
[[3, 8, 9, 7, 5, 2, 6, 1, 4], [2, 5, 1, 6, 4, 9, 8, 7, 3], [7, 4, 6, 3, 8, 1, 9, 2, 5], [8, 1, 2, 5, 7, 4, 3, 6, 9], [6, 9, 4, 8, 1, 3, 2, 5, 7], [5, 3, 7, 9, 2, 6, 4, 8, 1], [9, 7, 3, 2, 6, 5, 1, 4, 8], [4, 2, 8, 1, 3, 7, 5, 9, 6], [1, 6, 5, 4, 9, 8, 7, 3, 2]]
The solution is correct
このように、9*9の配列と、正解チェックがされて戻ってきました。かなり簡単に利用できますので、是非やってみてください。tokenの設定の仕方だけちょっとコツが必要ですので、最新の利用方法をチェックしてみてください。
数独は面白い
D-Waveの実機を利用した数独はインターネットを介して、実際にカナダのマシンで解かれて戻ってきます。D-Waveの登録で無料時間もありますので、ぜひ利用してみて体感してみてください。
License
Released under the Apache License 2.0. See LICENSE file.