// solve-sudoku9x9
// author: Leonardone @ NEETSDKASU

//! 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にできなかったら失敗  
//!
//! 適当な数独の問題でこのプログラムを試してみた感想としては  
//!
//!  - 人間にとって簡単と思える問題すら解けない場合もある…  
//!  - 人間にとって難しいと思える問題を解ける可能性は低いが解けることもある…
//!

use mersenne_twister_rs::*;

#[cfg(test)]
mod tests;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Error {
    /// パラメータfieldの列・行・ブロックの中に数値(1～9)の重複がある。
    DuplicateValue { row: usize, col: usize, value: u32 },

    /// パラメータfieldに0～9以外の数値がある。
    WrongValue { row: usize, col: usize, value: u32 },

    /// パラメータfieldが9x9のサイズではない。
    WrongSize,

    /// 解くのに失敗。
    Unsolved,
}

/// 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),
/// }
/// ```
pub struct Solver {
    // try count (= kick count + 1)
    try_count: u32,
    // iter count
    iter_count: u32,
    // cooling schedule
    cooling_speed: f64,
    // random seed
    random_seed: u32,
}

impl Default for Solver {
    /// デフォルトのパラメータでSolverを生成。  
    /// - パラメータtry_countは200  
    /// - パラメータiter_countは10000  
    /// - パラメータcooling_speedは0.8  
    /// - パラメータrandom_seedは5489  
    fn default() -> Self {
        const TRY_COUNT: u32 = 200;
        const ITER_COUNT: u32 = 10_000;
        const COOLING_SPEED: f64 = 0.8;
        const RANDOM_SEED: u32 = DEFAULT_SEED;
        Self {
            try_count: TRY_COUNT,
            iter_count: ITER_COUNT,
            cooling_speed: COOLING_SPEED,
            random_seed: RANDOM_SEED,
        }
    }
}

impl Solver {
    /// 任意のパラメータでSolverを生成。  
    /// 各パラメータの意味の説明は省略。  
    /// - パラメータtry_countは1以上 (100以上を推奨) (default: 200)  
    /// - パラメータiter_countは1000以上 (5000以上を推奨) (default: 10000)  
    /// - パラメータcooling_speedは1未満の正の値 (0.5以上を推奨) (default: 0.8)  
    /// - パラメータrandom_seedは任意の値 (9桁以上を推奨) (default: 5489)  
    pub fn new(
        try_count: u32,
        iter_count: u32,
        cooling_speed: f64,
        random_seed: u32,
    ) -> Result<Self, &'static str> {
        if try_count == 0 {
            return Err("パラメータtry_countは1以上 (100以上を推奨) (default: 200)");
        }
        if iter_count < 1000 {
            return Err("パラメータiter_countは1000以上 (5000以上を推奨) (default: 10000)");
        }
        if !(0.0 < cooling_speed && cooling_speed < 1.0) {
            return Err("パラメータcooling_speedは1未満の正の値 (0.5以上を推奨) (default: 0.8)");
        }
        Ok(Self {
            try_count,
            iter_count,
            cooling_speed,
            random_seed,
        })
    }

    /// 9x9の数独を解く。  
    /// パラメータfieldは9x9のu32型の2次元配列、空きマスは0、それ以外は1～9を埋めておく、solve処理で空きマスには1～9の数値が埋められる。  
    /// 戻り値は、  
    ///   - Ok(ステップ数) ... 解くのに成功した場合に返る。ステップ数は解くまでにかかった処理量。  
    ///   - Err(Unsolved)  ... 解くのに失敗した場合に返る。fieldにはでたらめな数値が埋まっている状態。    
    ///   - Err(その他)    ... 入力のfieldに不備があった場合に返る。  
    pub fn solve(&self, field: &mut Vec<Vec<u32>>) -> Result<u32, Error> {
        check(field)?;
        let pairs = make_pairs(field);
        fill_blocks(field);
        let mut status = Status::new(field);
        let mut mt = Box::new(MersenneTwister::new(self.random_seed));
        for u in 0..self.try_count {
            for i in 0..self.iter_count {
                if status.score == 0 {
                    assert!(
                        field
                            .iter()
                            .all(|row| row.iter().all(|v| (1..=9).contains(v))),
                        "BUG: 1～9以外が混じってる！ {:?}",
                        field
                    );
                    assert_eq!(check(field), Ok(()), "BUG: 矛盾が混じってる！ {:?}", field);
                    return Ok(i + u * self.iter_count);
                }
                let index = (mt.genrand_real2() * pairs.len() as f64).floor() as usize;
                let (p1, p2) = &pairs[index];
                let diff = status.calc(field, p1, p2);
                if diff > 0 {
                    // 焼きなまし法(SA)ぽい処理
                    // 参考資料
                    //  https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95
                    let r = i as f64 / self.iter_count as f64;
                    let t = self.cooling_speed.powf(r);
                    let p = (-diff as f64 / t).exp();
                    if p < mt.genrand_real2() {
                        continue;
                    }
                }
                status.swap(field, p1, p2);
            }
            // Kickぽい処理(fieldの中身をランダムにかき乱す)
            for _ in 0..pairs.len() / 2 {
                let index = (mt.genrand_real2() * pairs.len() as f64).floor() as usize;
                let (p1, p2) = &pairs[index];
                status.swap(field, p1, p2);
            }
        }
        Err(Error::Unsolved)
    }
}

fn check(field: &[Vec<u32>]) -> Result<(), Error> {
    check_wrong_size(field)?;
    check_wrong_value(field)?;
    check_duplicate_value_in_rows(field)?;
    check_duplicate_value_in_cols(field)?;
    check_duplicate_value_in_blocks(field)?;
    Ok(())
}

fn check_wrong_size(field: &[Vec<u32>]) -> Result<(), Error> {
    if field.len() != 9 {
        return Err(Error::WrongSize);
    }
    if field.iter().any(|row| row.len() != 9) {
        return Err(Error::WrongSize);
    }
    Ok(())
}

fn check_wrong_value(field: &[Vec<u32>]) -> Result<(), Error> {
    assert!(field.len() == 9);
    assert!(field.iter().all(|r| r.len() == 9));
    field
        .iter()
        .enumerate()
        .find_map(|(row, line)| {
            line.iter().enumerate().find_map(|(col, value)| {
                if (0..=9).contains(value) {
                    None
                } else {
                    Some(Error::WrongValue {
                        row,
                        col,
                        value: *value,
                    })
                }
            })
        })
        .map_or(Ok(()), Err)
}

fn check_duplicate_value_in_rows(field: &[Vec<u32>]) -> Result<(), Error> {
    assert!(field.len() == 9);
    assert!(field.iter().all(|r| r.len() == 9));
    assert!(field.iter().all(|r| r.iter().all(|v| (0..=9).contains(v))));
    for (i, row) in field.iter().enumerate() {
        let mut nums = [0_i32; 10];
        for (k, v) in row.iter().enumerate() {
            let x = *v as usize;
            nums[x] += 1;
            if x > 0 && nums[x] > 1 {
                return Err(Error::DuplicateValue {
                    row: i,
                    col: k,
                    value: *v,
                });
            }
        }
    }
    Ok(())
}

fn check_duplicate_value_in_cols(field: &[Vec<u32>]) -> Result<(), Error> {
    assert!(field.len() == 9);
    assert!(field.iter().all(|r| r.len() == 9));
    assert!(field.iter().all(|r| r.iter().all(|v| (0..=9).contains(v))));
    for k in 0..9_usize {
        let mut nums = [0_i32; 10];
        for (i, row) in field.iter().enumerate() {
            let x = row[k] as usize;
            nums[x] += 1;
            if x > 0 && nums[x] > 1 {
                return Err(Error::DuplicateValue {
                    row: i,
                    col: k,
                    value: row[k],
                });
            }
        }
    }
    Ok(())
}

fn check_duplicate_value_in_blocks(field: &[Vec<u32>]) -> Result<(), Error> {
    assert!(field.len() == 9);
    assert!(field.iter().all(|r| r.len() == 9));
    assert!(field.iter().all(|r| r.iter().all(|v| (0..=9).contains(v))));
    for (a, rows) in field.chunks(3).enumerate() {
        let iter = rows[0]
            .chunks(3)
            .enumerate()
            .zip(rows[1].chunks(3).zip(rows[2].chunks(3)));

        for ((b, x), (y, z)) in iter {
            let mut nums = [0_u32; 10];

            let iter = x.iter().chain(y.iter()).chain(z.iter()).enumerate();

            for (i, v) in iter {
                let p = *v as usize;
                nums[p] += 1;
                if p > 0 && nums[p] > 1 {
                    return Err(Error::DuplicateValue {
                        row: a * 3 + i / 3,
                        col: b * 3 + i % 3,
                        value: *v,
                    });
                }
            }
        }
    }
    Ok(())
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pos {
    row: usize,
    col: usize,
}

impl Pos {
    fn get(&self, field: &[Vec<u32>]) -> usize {
        field[self.row][self.col] as usize
    }
}

fn make_pairs(field: &[Vec<u32>]) -> Vec<(Pos, Pos)> {
    let mut pairs: Vec<(Pos, Pos)> = vec![];
    let mut pos: Vec<Pos> = vec![];
    for a in 0..3 {
        let row = a * 3;
        for b in 0..3 {
            let col = b * 3;
            pos.clear();
            for dr in 0..3 {
                for dc in 0..3 {
                    pos.push(Pos {
                        row: row + dr,
                        col: col + dc,
                    });
                }
            }
            pos.retain(|p| field[p.row][p.col] == 0);
            for i in 0..pos.len() {
                for k in i + 1..pos.len() {
                    pairs.push((pos[i], pos[k]));
                }
            }
        }
    }
    pairs
}

fn fill_blocks(field: &mut Vec<Vec<u32>>) {
    for a in 0..3 {
        let row = a * 3;
        for b in 0..3 {
            let col = b * 3;
            let mut nums: Vec<u32> = (1..=9).collect();
            for dr in 0..3 {
                for dc in 0..3 {
                    let v = field[row + dr][col + dc];
                    if v > 0 {
                        nums.retain(|w| *w != v);
                    }
                }
            }
            for dr in 0..3 {
                for dc in 0..3 {
                    let v = &mut field[row + dr][col + dc];
                    if *v == 0 {
                        *v = nums.pop().unwrap();
                    }
                }
            }
        }
    }
}

struct Status {
    score: i32,
    rows_state: Vec<Vec<i32>>,
    cols_state: Vec<Vec<i32>>,
}

impl Status {
    fn new(field: &[Vec<u32>]) -> Self {
        let mut rows_state: Vec<Vec<i32>> = (0..9).map(|_| vec![-1; 10]).collect();
        let mut cols_state: Vec<Vec<i32>> = rows_state.clone();
        for (i, row) in field.iter().enumerate() {
            for (k, v) in row.iter().enumerate() {
                let p = *v as usize;
                rows_state[i][p] += 1;
                cols_state[k][p] += 1;
            }
        }
        let score: i32 = rows_state
            .iter()
            .map(|row| row.iter().skip(1).map(|v| v.abs()).sum::<i32>())
            .sum::<i32>()
            + cols_state
                .iter()
                .map(|col| col.iter().skip(1).map(|v| v.abs()).sum::<i32>())
                .sum::<i32>();
        Self {
            score,
            rows_state,
            cols_state,
        }
    }

    fn calc(&self, field: &[Vec<u32>], p1: &Pos, p2: &Pos) -> i32 {
        let v1 = p1.get(field);
        let v2 = p2.get(field);
        let rows_diff = if p1.row == p2.row {
            0
        } else {
            let old_score = self.rows_state[p1.row][v1].abs()
                + self.rows_state[p1.row][v2].abs()
                + self.rows_state[p2.row][v1].abs()
                + self.rows_state[p2.row][v2].abs();
            let new_score = (self.rows_state[p1.row][v1] - 1).abs()
                + (self.rows_state[p1.row][v2] + 1).abs()
                + (self.rows_state[p2.row][v1] + 1).abs()
                + (self.rows_state[p2.row][v2] - 1).abs();
            new_score - old_score
        };
        let cols_diff = if p1.col == p2.col {
            0
        } else {
            let old_score = self.cols_state[p1.col][v1].abs()
                + self.cols_state[p1.col][v2].abs()
                + self.cols_state[p2.col][v1].abs()
                + self.cols_state[p2.col][v2].abs();
            let new_score = (self.cols_state[p1.col][v1] - 1).abs()
                + (self.cols_state[p1.col][v2] + 1).abs()
                + (self.cols_state[p2.col][v1] + 1).abs()
                + (self.cols_state[p2.col][v2] - 1).abs();
            new_score - old_score
        };
        rows_diff + cols_diff
    }

    fn swap(&mut self, field: &mut [Vec<u32>], p1: &Pos, p2: &Pos) {
        let v1 = p1.get(field);
        let v2 = p2.get(field);
        field[p1.row][p1.col] = v2 as u32;
        field[p2.row][p2.col] = v1 as u32;
        let rows_diff = if p1.row == p2.row {
            0
        } else {
            let old_score = self.rows_state[p1.row][v1].abs()
                + self.rows_state[p1.row][v2].abs()
                + self.rows_state[p2.row][v1].abs()
                + self.rows_state[p2.row][v2].abs();
            self.rows_state[p1.row][v1] -= 1;
            self.rows_state[p1.row][v2] += 1;
            self.rows_state[p2.row][v1] += 1;
            self.rows_state[p2.row][v2] -= 1;
            let new_score = self.rows_state[p1.row][v1].abs()
                + self.rows_state[p1.row][v2].abs()
                + self.rows_state[p2.row][v1].abs()
                + self.rows_state[p2.row][v2].abs();
            new_score - old_score
        };
        let cols_diff = if p1.col == p2.col {
            0
        } else {
            let old_score = self.cols_state[p1.col][v1].abs()
                + self.cols_state[p1.col][v2].abs()
                + self.cols_state[p2.col][v1].abs()
                + self.cols_state[p2.col][v2].abs();
            self.cols_state[p1.col][v1] -= 1;
            self.cols_state[p1.col][v2] += 1;
            self.cols_state[p2.col][v1] += 1;
            self.cols_state[p2.col][v2] -= 1;
            let new_score = self.cols_state[p1.col][v1].abs()
                + self.cols_state[p1.col][v2].abs()
                + self.cols_state[p2.col][v1].abs()
                + self.cols_state[p2.col][v2].abs();
            new_score - old_score
        };
        self.score += rows_diff + cols_diff;
    }
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::DuplicateValue { row, col, value } => {
                write!(f, "値が重複 (場所: 行{} 列{}, 値: {})", row, col, value)
            }
            Error::WrongValue { row, col, value } => {
                write!(f, "値が不正 (場所: 行{} 列{}, 値: {})", row, col, value)
            }
            Error::WrongSize => {
                write!(f, "9x9のサイズになってない")
            }
            Error::Unsolved => {
                write!(f, "残念ながら解けませんでした･･･ごめんなさい")
            }
        }
    }
}

impl std::error::Error for Error {}