F#でOR-Toolsを用いた数独のソルバを実装してみた
実装してみました.
目次
背景
- 関数型プログラミングって響きがカッコイイ
- C#はほんの少しだけ書ける
- 数理最適化もほんの少しだけ出来る
じゃ, F#でOR-Toolsを使って数独のソルバを作ってみるか.
問題はコチラからお借りしました.
設計
まずはディレクトリ構成
sudoku-solver/
├── Core/
│ ├── Optimizer/
│ │ └── SudokuSolver.fs # ソルバ
│ ├── Utils/
│ │ ├── CsvHandler.fs # 問題のCSV読み込み処理
│ │ ├── Models.fs # 問題の型や解のタイプ等
│ │ ├── PathHandler.fs # パスのハンドリングを行う
│ │ └── Visualizer.fs # ソルバの結果を可視化する
│ ├── Core.fsproj
│ └── Program.fs # エントリポイント
├── Data/
│ └── base/ # 問題集
│ ├── L7_1_01.csv
│ ...
│ └── L7_1_10.csv
└── sudoku-solver.sln
続いてプロジェクト(Core/Core.fsproj)の構成. F#は前方参照があるので, 丁寧に設定しましょう.
<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
<OutputType>Exe</OutputType>
<TargetFramework>net9.0</TargetFramework>
</PropertyGroup>
<ItemGroup>
<Compile Include="Utils/Models.fs" />
<Compile Include="Utils/CsvHandler.fs" />
<Compile Include="Utils/PathHandler.fs" />
<Compile Include="Utils/Visualizer.fs" />
<Compile Include="Optimizer/SudokuSolver.fs" />
<Compile Include="Program.fs" />
</ItemGroup>
<ItemGroup>
<PackageReference Include="Google.OrTools" Version="9.15.6755" />
</ItemGroup>
</Project>
もう少しかみ砕きます. ファイル間の関係を図示すると, 次のようになります.
Models.fsはソルバやcsvのハンドラ等, 色々なところから参照されます.
だから, Core.fsprojでは一番上に記載されています.
反対に, Program.fsはどこからも参照されず, 色々なモジュールを参照します. だからこそ, Core.fsprojでは一番下に記載されるわけですね.
定式化
数独のルールをコンピュータに理解してもらうために, 以下のように数式でモデル化(定式化)します.
1. 変数の定義
各セル(行 $r$, 列 $c$)に値 $v$ が配置されるかどうかを表す, 3次元の 0-1バイナリ変数 $x_{r, c, v}$ を定義します.
$$x_{r, c, v} = \begin{cases} 1 & (\text{行 } r, \text{列 } c \text{ に値 } v \text{ が入る場合}) \ 0 & (\text{それ以外}) \end{cases}$$
ここで, インデックスの範囲はすべて $1 \le r, c, v \le 9$ です.
2. 制約条件
初期配置の固定(ヒント数字)
問題(CSV)ですでに数字が埋まっているマス(値を $V_{r,c}$ とする)については, その値を固定します.
$$x_{r, c, V_{r,c}} = 1$$
(addConstraintsInitial関数に対応)
各セルには必ず1つの値が入る
1つのマスに数字が2つ入ったり, 空欄になったりしてはいけません.
$$\sum_{v=1}^{9} x_{r, c, v} = 1 \quad (\forall r, \forall c)$$
(addConstraintsOne関数に対応)
各列において, 同じ数字は1度しか使えない
任意の列 $c$ において, 数字 $v$ は1回だけ登場します.
$$\sum_{r=1}^{9} x_{r, c, v} = 1 \quad (\forall c, \forall v)$$
(addConstraintsColumn関数に対応)
各行において, 同じ数字は1度しか使えない
任意の行 $r$ において, 数字 $v$ は1回だけ登場します.
$$\sum_{c=1}^{9} x_{r, c, v} = 1 \quad (\forall r, \forall v)$$
(addConstraintsRow関数に対応)
$3 \times 3$ のブロック内において, 同じ数字は1度しか使えない
9つある各ブロック($B_1, B_2, \dots, B_9$)の中でも, 数字 $v$ は1回だけ登場します.
$$\sum_{(r, c) \in B_k} x_{r, c, v} = 1 \quad (\forall k, \forall v)$$
(addConstraintsBlock関数に対応)
主要な実装
主要なところだけ書きます. コードの全文はAppendixに書きます. 興味があればどうぞ.
Modelsモジュール
Core/Utils/Models.fsファイルです. 問題の型とソルバの結果型を設定しています.
F#の判別共用体では, Enumに更に値を持たせるようなイメージで実装することが出来ます. 実際, 今回は問題やソルバの結果型に, SudokuPuzzle型(要は2次元配列)を持たせるように実装しています.
※他の言語で出来るかどうかは知りません. 勉強不足で申し訳ないです...
// Core/Utils/Models.fs
namespace Core.Utils
/// 型定義
module Models =
/// 問題の型
type SudokuPuzzle =
{ Cells: int[,] }
/// ソルバの結果型
type SolveResult =
/// 解が見つかった
| Solved of SudokuPuzzle
/// 解無し
| Infeasible
/// タイムアウト等
| Unknown
Programモジュール
エントリポイントです. やることはシンプルで, ルートパス取得->問題ファイルのパスを絶対パス化->求解->可視化のステップを問題ファイルの数だけ回しています.
個人的に「F#らしい」と感じている, パイプ演算子(|>)を用いています. バケツリレーのようなイメージでしょうか.
// Core/Program.fs
namespace Core
module Program =
open Core.Utils.CsvHandler
open Core.Utils.PathHandler
open Core.Utils.Visualizer
open Core.Optimizer.SudokuSolver
// エントリポイント
[<EntryPoint>]
let main args =
// ルートパスを取得する
let root = resolveProjectRoot args
printfn "ProjectRoot : %s" root
// ターゲットのファイルをリストでベタ書きする
let targetFiles = [
"Data/base/L7_1_01.csv";
// ~中略~
"Data/base/L7_1_10.csv";
]
// ターゲットのファイルリストに対し,
// 絶対パス取得->問題取得->求解->可視化
targetFiles
|> List.map (combinePaths root)
|> List.iter (
fun csvPath ->
printfn "Loading: %s" csvPath
csvPath
|> loadPuzzle
|> solvePuzzle
|> visualizeResult
)
0
私は他の関数型言語を知りませんが, 全くの関数型/F#素人ながら, こういった書き方が気に入っています.
SudokuSolverモジュール
概略
Core/Optimizer/SudokuSolver.fsの実装です. まずは概略から.
/// ソルバ
module SudokuSolver =
open Google.OrTools.Sat
/// モデル, 変数の生成を行うプライベートモジュール
module private ModelBuilder =
/// モデル, 変数を生成する
let buildModel (): CpModel*BoolVar[,,] =
// ~中略~
/// 制約を追加するプライベートモジュール
module private ConstraintAdder =
// ~中略~
/// 制約を追加する
let addConstraints (model: CpModel) (vars: BoolVar[,,]) (puzzle: SudokuPuzzle): unit =
// ~中略~
/// ソルバのプライベートモジュール
module private Solver =
// ~中略~
/// 求解する
let solve (model: CpModel) (vars: BoolVar[,,]): SolveResult =
// ~中略~
/// 問題を受け取り, 結果を返す
let solvePuzzle (puzzle: SudokuPuzzle): SolveResult =
// モデル, 変数を生成する
let model, vars = ModelBuilder.buildModel()
// 制約を作成して追加する
ConstraintAdder.addConstraints model vars puzzle
// 求解する
Solver.solve model vars
外側から呼ばれる関数はsolvePuzzleのみです.
それ以外のモジュールは全てプライベートモジュール化し, カプセル化しています.
ModelBuilderモジュール
ModelBuilderはシンプルです. ただし, F#独特の書き方で, Array3D.initを用いています.
今回の書き方だと,
- 3次元配列(9x9x9)を作る
- そのインデックスをそのまま変数名とした, ブーリアン変数の3次元配列を作る
という指令になります.
module SudokuSolver =
open Google.OrTools.Sat
/// モデル, 変数の生成を行うプライベートモジュール
module private ModelBuilder =
/// モデル, 変数を生成する
let buildModel (): CpModel*BoolVar[,,] =
// モデルを生成する
let model = CpModel()
// 0-1の整数変数を9*9*9個作成する
let vars = Array3D.init 9 9 9 (fun r c v -> model.NewBoolVar($"x_{r}_{c}_{v}"))
model, vars
ConstraintAdderモジュール
ConstraintAdderは必要最低限の制約追加を行っています.
- 初期の制約(ヒント数字)
- 各セルにはちょうど1つの数字が入る制約
- 1~9の数値が出てくるのは1列に1回という制約
- 1~9の数値が出てくるのは1行に1回という制約
- 1~9の数値が出てくるのは3×3の領域それぞれで1回という制約
module SudokuSolver =
open Google.OrTools.Sat
/// 制約を追加するプライベートモジュール
module private ConstraintAdder =
/// 初期の制約を追加する
let private addConstraintsInitial (model: CpModel) (vars: BoolVar[,,]) (puzzle: SudokuPuzzle): unit =
let idxs = [0..8]
// 初期の制約を追加する
for r in idxs do
for c in idxs do
let value = puzzle.Cells[r, c]
if value <> 0 then
[vars.[r,c,value-1] :> ILiteral]
|> List.toSeq
|> model.AddBoolAnd
|> ignore
/// 各セルにはちょうど1つの数字が入る
let private addConstraintsOne (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 各セルにはちょうど1つの数字が入る
for r in idxs do
for c in idxs do
[ for v in idxs -> vars.[r, c, v] :> ILiteral ]
|> model.AddExactlyOne
|> ignore
/// 1~9の数値が出てくるのは1列に1回
let private addConstraintsColumn (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 1~9の数値が出てくるのは1列に1回
for v in idxs do
for c in idxs do
[for r in idxs -> vars.[r, c, v] :> ILiteral]
|> List.toSeq
|> model.AddExactlyOne
|> ignore
/// 1~9の数値が出てくるのは1行に1回
let private addConstraintsRow (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 1~9の数値が出てくるのは1行に1回
for v in idxs do
for r in idxs do
[for c in idxs -> vars.[r, c, v] :> ILiteral]
|> List.toSeq
|> model.AddExactlyOne
|> ignore
/// 1~9の数値が出てくるのは3×3の領域それぞれで1回
let private addConstraintsBlock (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 1~9の数値が出てくるのは3×3の領域それぞれで1回
let blockIdx = [0..2]
for v in idxs do
for rBlock in blockIdx do
for cBlock in blockIdx do
[
for r in blockIdx do
for c in blockIdx
-> vars.[r+3*rBlock, c+3*cBlock, v]
:> ILiteral
]
|> List.toSeq
|> model.AddExactlyOne
|> ignore
/// 制約を追加する
let addConstraints (model: CpModel) (vars: BoolVar[,,]) (puzzle: SudokuPuzzle): unit =
// 初期の制約を追加する
addConstraintsInitial model vars puzzle
// 各セルにはちょうど1つの数字が入る
addConstraintsOne model vars
// 1~9の数値が出てくるのは1列に1回
addConstraintsColumn model vars
// 1~9の数値が出てくるのは1行に1回
addConstraintsRow model vars
// 1~9の数値が出てくるのは3×3の領域それぞれで1回
addConstraintsBlock model vars
書き方に少しクセがありますので, いくつか解説していきます.
初期の制約(ヒント数字)について, CpModel.AddBoolAnd()という関数を使用しています.
F#におけるSeqしか受け付けなかったので, List.toSeqを用いてSeqに変換しています.
以降全ての関数でこの変換を使用しています.
:>という演算子について. CpModelに制約を追加する際, 変数Variableやその線形和Exprは, その親クラスのILiteralに変換する必要があります. 親クラスに変換するための演算子が:>です.
C#ユーザなら, 以下のような書き方に見覚えがあるかもしれません.
var parent = child as Parent
もちろん, C#では暗黙的に変換することもありますが, F#では先述したように, 明示的に変換する必要があります.
Solverモジュール
ソルバの本丸ですね. とは言え, ソルバ生成と求解はたった2行で終わってしまいます.
むしろ, 解が求まった後の処理にほとんどの行数を割いています.
module SudokuSolver =
open Google.OrTools.Sat
/// ソルバのプライベートモジュール
module private Solver =
/// 変数の配列を受け取り, Trueになっている変数のインデックスに1を足して返す
let private getIdx (solver: CpSolver) (vars: BoolVar[]): int =
vars
|> Array.findIndex (fun v -> solver.BooleanValue v)
|> (+) 1
/// 求解する
let solve (model: CpModel) (vars: BoolVar[,,]): SolveResult =
// ソルバを生成して求解する
let solver = new CpSolver()
let status = solver.Solve(model)
if status = CpSolverStatus.Optimal || status = CpSolverStatus.Feasible then
// 求解出来たので処理開始
let idxs = [0..8]
// 9x9の二次元配列の各要素に対し, そのマスに入る値を取得する
// ジャグ配列(list in list)とする
let values = [
for r in idxs do
[
for c in idxs do
[for v in idxs -> vars.[r, c, v]]
|> List.toArray
|> getIdx solver
]
]
// 2次元配列に整形する
let cells = Array2D.init 9 9 (fun r c -> values.[r].[c])
// 解けたので判別共用体にして返す
Solved {Cells = cells}
else
// 何らかの理由で解が見つからなかった
match status with
| CpSolverStatus.Infeasible -> Infeasible
| _ -> Unknown
特に関数型っぽく？するために, getIdx関数を作りました.
コメントを見てもらえれば分かりますが, 各マス目の変数の値を取得し, 効率的に解を出力しています.
vars
|> Array.findIndex (fun v -> solver.BooleanValue v)
|> (+) 1 // ← ココ！
上記の部分で |> (+) 1 は, パイプラインから渡ってきたインデックス(0～8)に1を足して, 数独の実際の値(1～9)に変換します.
カリー化を利用した, F#特有の書き方みたいです.
Visualizerモジュール
ソルバを通した結果を, イイ感じに出力してくれます.
// Core/Utils/Visualizer.fs
namespace Core.Utils
open Core.Utils.Models
/// 可視化用モジュール
module Visualizer =
let private getRow (arr: int[,]) (r: int) : int[] =
[| for c in 0..8 -> arr.[r, c] |]
let private getVisRow (row: int[]): string =
// 分かりにくいが, 要するに以下のようにする
// [1; 2; 3; 4; 5; 6; 7; 8; 9]
// -> "|1 2 3|4 5 6|7 8 9|"
$"|{row.[0]} {row.[1]} {row.[2]}|{row.[3]} {row.[4]} {row.[5]}|{row.[6]} {row.[7]} {row.[8]}|"
let private getVisList (sep: string) (arr: int[,]) =
let row r = getRow arr r |> getVisRow
[0..8]
|> List.collect (
fun r ->
if r % 3 = 0 then
[ sep; row r ]
else
[ row r ]
)
|> fun lines -> lines @ [ sep ]
let private visualizeCells (arr: int[,]) : unit =
let sep = "+-----+-----+-----+"
getVisList sep arr |> List.iter (printfn "%s")
/// ソルバの結果を受け取り, 可視化を行う
let visualizeResult (result: SolveResult): unit =
match result with
| Solved p -> visualizeCells p.Cells
| Infeasible -> eprintfn "Infeasible"
| Unknown -> eprintfn "Interrupted"
複雑に見えますが, 本筋としてはmatch文でソルバの結果型を判別し, 解が求まっている時だけは特別なお化粧をするモジュールです. 出力例は以下のような形です.
# 出力例
+-----+-----+-----+
|7 4 2|3 5 9|1 8 6|
|6 1 9|7 8 4|3 5 2|
|8 5 3|2 1 6|9 7 4|
+-----+-----+-----+
|4 8 5|9 3 7|2 6 1|
|3 6 7|8 2 1|4 9 5|
|2 9 1|6 4 5|8 3 7|
+-----+-----+-----+
|9 2 6|1 7 3|5 4 8|
|5 7 8|4 9 2|6 1 3|
|1 3 4|5 6 8|7 2 9|
+-----+-----+-----+
最後に
F#でOR-Toolsを扱うことが出来ました. F#の関数型の良いところを活かせているのでは？と感じています.
もちろん主観です.
F#でOR-Tools, ひいては数理最適化のラッパーを育ててみるのもアリかもしれないと思いました.
Appendix
実装の全文を置きます.
Models
// Core/Utils/Models.fs
namespace Core.Utils
/// 型定義
module Models =
/// 問題の型
type SudokuPuzzle =
{ Cells: int[,] }
/// ソルバの結果型
type SolveResult =
/// 解が見つかった
| Solved of SudokuPuzzle
/// 解無し
| Infeasible
/// タイムアウト等
| Unknown
CsvHandler
// Core/Utils/CsvHandler.fs
namespace Core.Utils
open System
open System.IO
open Core.Utils.Models
// CSVパーサー
module CsvHandler =
/// 文字をパースする. 空白はゼロ, それ以外はintに変換
let private parseCell (s: string): int =
match s.Trim() with
| "" -> 0
| s -> int s
/// 1行をカンマで区切り, 各文字をパースして配列で返す
let private parseLine (line: string) : int[] =
line.Split(',') |> Array.map parseCell
/// CSVパスを受け取り, 2次元配列に整形, 問題の型にして返す
let loadPuzzle (path: string) : SudokuPuzzle =
let cells =
File.ReadLines(path)
|> Seq.filter (fun line -> not (String.IsNullOrWhiteSpace(line)))
|> Seq.map parseLine
|> Seq.toArray
|> fun rows -> Array2D.init 9 9 (fun r c -> rows.[r].[c])
{ Cells = cells }
PathHandler
namespace Core.Utils
open System
open System.IO
/// パスのハンドリング
module PathHandler =
/// ルートパスを何とかして返す関数
let resolveProjectRoot (args: string[]) =
// ステップその1. --root引数を探し出す. 見つからなければNone
let fromArgs =
args
|> Array.pairwise
|> Array.tryFind (fun (k, _) -> k = "--root")
|> Option.map snd
// ステップその1でルートパスが見つかっていればそのまま
match fromArgs with
| Some root -> root
| None ->
// cwdでカレントディレクトリを取得
let cwd = Directory.GetCurrentDirectory()
if Directory.Exists(Path.Combine(cwd, "Data", "base")) then
// カレントディレクトリにデータのディレクトリが存在が見つかったので,
// ルートパスとして適切. そのまま返す
cwd
else
// カレントディレクトリにデータのディレクトリが存在しない
// カレントディレクトリがnetX.0のディレクトリになっている
// 親(Debug or Release)の親(bin)の親(Core)のフルパスを取得して返す
AppDomain.CurrentDomain.BaseDirectory
|> Directory.GetParent
|> fun d -> d.Parent
|> fun d -> d.Parent
|> fun d -> d.FullName
/// 2つの文字列をパスとして結合する
let combinePaths (root: string) (relativePath: string) =
Path.Combine(root, relativePath)
Visualizer
// Core/Utils/Visualizer.fs
namespace Core.Utils
open Core.Utils.Models
/// 可視化用モジュール
module Visualizer =
let private getRow (arr: int[,]) (r: int) : int[] =
[| for c in 0..8 -> arr.[r, c] |]
let private getVisRow (row: int[]): string =
// 分かりにくいが, 要するに以下のようにする
// [1; 2; 3; 4; 5; 6; 7; 8; 9]
// -> "|1 2 3|4 5 6|7 8 9|"
$"|{row.[0]} {row.[1]} {row.[2]}|{row.[3]} {row.[4]} {row.[5]}|{row.[6]} {row.[7]} {row.[8]}|"
let private getVisList (sep: string) (arr: int[,]) =
let row r = getRow arr r |> getVisRow
[0..8]
|> List.collect (
fun r ->
if r % 3 = 0 then
[ sep; row r ]
else
[ row r ]
)
|> fun lines -> lines @ [ sep ]
let private visualizeCells (arr: int[,]) : unit =
let sep = "+-----+-----+-----+"
getVisList sep arr |> List.iter (printfn "%s")
/// ソルバの結果を受け取り, 可視化を行う
let visualizeResult (result: SolveResult): unit =
match result with
| Solved p -> visualizeCells p.Cells
| Infeasible -> eprintfn "Infeasible"
| Unknown -> eprintfn "Interrupted"
SudokuSolver
// Core/Optimizer/SudokuSolver.fs
namespace Core.Optimizer
open Core.Utils.Models
/// ソルバ
module SudokuSolver =
open Google.OrTools.Sat
/// モデル, 変数の生成を行うプライベートモジュール
module private ModelBuilder =
/// モデル, 変数を生成する
let buildModel (): CpModel*BoolVar[,,] =
// モデルを生成する
let model = CpModel()
// 0-1の整数変数を9*9*9個作成する
let vars = Array3D.init 9 9 9 (fun r c v -> model.NewBoolVar($"x_{r}_{c}_{v}"))
model, vars
/// 制約を追加するプライベートモジュール
module private ConstraintAdder =
/// 初期の制約を追加する
let private addConstraintsInitial (model: CpModel) (vars: BoolVar[,,]) (puzzle: SudokuPuzzle): unit =
let idxs = [0..8]
// 初期の制約を追加する
for r in idxs do
for c in idxs do
let value = puzzle.Cells[r, c]
if value <> 0 then
[vars.[r,c,value-1] :> ILiteral]
|> List.toSeq
|> model.AddBoolAnd
|> ignore
/// 各セルにはちょうど1つの数字が入る
let private addConstraintsOne (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 各セルにはちょうど1つの数字が入る
for r in idxs do
for c in idxs do
[ for v in idxs -> vars.[r, c, v] :> ILiteral ]
|> model.AddExactlyOne
|> ignore
/// 1~9の数値が出てくるのは1列に1回
let private addConstraintsColumn (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 1~9の数値が出てくるのは1列に1回
for v in idxs do
for c in idxs do
[for r in idxs -> vars.[r, c, v] :> ILiteral]
|> List.toSeq
|> model.AddExactlyOne
|> ignore
/// 1~9の数値が出てくるのは1行に1回
let private addConstraintsRow (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 1~9の数値が出てくるのは1行に1回
for v in idxs do
for r in idxs do
[for c in idxs -> vars.[r, c, v] :> ILiteral]
|> List.toSeq
|> model.AddExactlyOne
|> ignore
/// 1~9の数値が出てくるのは3×3の領域それぞれで1回
let private addConstraintsBlock (model: CpModel) (vars: BoolVar[,,]): unit =
let idxs = [0..8]
// 1~9の数値が出てくるのは3×3の領域それぞれで1回
let blockIdx = [0..2]
for v in idxs do
for rBlock in blockIdx do
for cBlock in blockIdx do
[
for r in blockIdx do
for c in blockIdx
-> vars.[r+3*rBlock, c+3*cBlock, v]
:> ILiteral
]
|> List.toSeq
|> model.AddExactlyOne
|> ignore
/// 制約を追加する
let addConstraints (model: CpModel) (vars: BoolVar[,,]) (puzzle: SudokuPuzzle): unit =
// 初期の制約を追加する
addConstraintsInitial model vars puzzle
// 各セルにはちょうど1つの数字が入る
addConstraintsOne model vars
// 1~9の数値が出てくるのは1列に1回
addConstraintsColumn model vars
// 1~9の数値が出てくるのは1行に1回
addConstraintsRow model vars
// 1~9の数値が出てくるのは3×3の領域それぞれで1回
addConstraintsBlock model vars
/// ソルバのプライベートモジュール
module private Solver =
/// 変数の配列を受け取り, Trueになっている変数のインデックスに1を足して返す
let private getIdx (solver: CpSolver) (vars: BoolVar[]): int =
vars
|> Array.findIndex (fun v -> solver.BooleanValue v)
|> (+) 1
/// 求解する
let solve (model: CpModel) (vars: BoolVar[,,]): SolveResult =
// ソルバを生成して求解する
let solver = new CpSolver()
let status = solver.Solve(model)
if status = CpSolverStatus.Optimal || status = CpSolverStatus.Feasible then
// 求解出来たので処理開始
let idxs = [0..8]
// 9x9の二次元配列の各要素に対し, そのマスに入る値を取得する
// ジャグ配列(list in list)とする
let values = [
for r in idxs do
[
for c in idxs do
[for v in idxs -> vars.[r, c, v]]
|> List.toArray
|> getIdx solver
]
]
// 2次元配列に整形する
let cells = Array2D.init 9 9 (fun r c -> values.[r].[c])
// 解けたので判別共用体にして返す
Solved {Cells = cells}
else
// 何らかの理由で解が見つからなかった
match status with
| CpSolverStatus.Infeasible -> Infeasible
| _ -> Unknown
/// 問題を受け取り, 結果を返す
let solvePuzzle (puzzle: SudokuPuzzle): SolveResult =
// モデル, 変数を生成する
let model, vars = ModelBuilder.buildModel()
// 制約を作成して追加する
ConstraintAdder.addConstraints model vars puzzle
// 求解する
Solver.solve model vars
Program
// Core/Program.fs
namespace Core
module Program =
open Core.Utils.CsvHandler
open Core.Utils.PathHandler
open Core.Utils.Visualizer
open Core.Optimizer.SudokuSolver
// エントリポイント
[<EntryPoint>]
let main args =
// ルートパスを取得する
let root = resolveProjectRoot args
printfn "ProjectRoot : %s" root
// ターゲットのファイルをリストでベタ書きする
let targetFiles = [
"Data/base/L7_1_01.csv";
"Data/base/L7_1_02.csv";
"Data/base/L7_1_03.csv";
"Data/base/L7_1_04.csv";
"Data/base/L7_1_05.csv";
"Data/base/L7_1_06.csv";
"Data/base/L7_1_07.csv";
"Data/base/L7_1_08.csv";
"Data/base/L7_1_09.csv";
"Data/base/L7_1_10.csv";
]
// ターゲットのファイルリストに対し,
// 絶対パス取得->問題取得->求解->可視化
targetFiles
|> List.map (combinePaths root)
|> List.iter (
fun csvPath ->
printfn "Loading: %s" csvPath
csvPath
|> loadPuzzle
|> solvePuzzle
|> visualizeResult
)
0