Crate solve_sudoku9x9

9x9の数独の問題を解くソルバー。
※必ず解けるわけではない…

Example

use solve_sudoku9x9::*;
let mut field: Vec<Vec<u32>> = vec![/* 9x9の数独の問題 */];
let solver = Solver::default();
match solver.solve(&mut field) {
    Ok(_) => println!("解けました！ {:?}", field),
    Err(Error::Unsolved) => println!("解けませんでした"),
    Err(error) => println!("入力にミスがあります！ {}", error),
}

※9x9の数独の問題は数字1～9と空きマスを0として9x9の2次元配列(Vec<Vec<u32>>)で表現する

Summary

9x9(81マス)の数独の問題を解きたい

9x9の81マスが次の条件全てを満たすように空きマスを埋めていく必要がある

• 1列(9x1の9マス)に1～9の各数字が揃う
• 1行(1x9の9マス)に1～9の各数字が揃う
• 1ブロック(3x3の9マス)に1～9の各数字が揃う

このプログラムのアプローチは

• 初期状態として各1ブロック(3x3の9マス)に1～9の各数字が揃うように空きマスに適当な数字を配置する
• 1列(9x1の9マス)内や1行(1x9の9マス)内の不揃いを得点(コスト)として計上する
• 各1ブロック(3x3の9マス)内の中でランダムに選んだ2マスの数字を入れ替えること(2点swap)を繰り返す
• 2点swapを遷移(近傍?)として焼きなまし法(SA)を行いコストを限りなく0に近づけること(最小化)を目指す
• コストが0に至れば数独の問題を解くことに成功、コストを0にできなかったら失敗

適当な数独の問題でこのプログラムを試してみた感想としては

• 人間にとって簡単と思える問題すら解けない場合もある…
• 人間にとって難しいと思える問題を解ける可能性は低いが解けることもある…

Structs

Solver

9x9の数独の問題を解くソルバー。
※必ず解けるわけではない…

Enums

Error