Sudoku

use sudoku.qweruse sudoku_parse, sudoku_validate from sudoku      // Quillo 0.6: only these

serde_json = { version = "1", features = ["preserve_order"] }

// Sudoku: a well-known puzzle solved, a hard one graded, one with a mistake refused, a new puzzle// made from a seed, and a hint.////   quillo run sudoku.qwe//   then open http://localhost:8080/solve, /grade, /generate?seed=7, /hint and /refuseduse "sudoku.qwer"// Wikipedia's example puzzle, Arto Inkala's "hardest" one, and a board with two 5s in a row.let easy = "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"let inkala = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.."let wrong = "55..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"route GET /solve = {    wikipedia: sudoku_solve(easy)?,    hardest: sudoku_solve(inkala)?.solution,    drawn: sudoku_parse("5 3 . | . 7 . | . . .\n6 . . | 1 9 5 | . . .\n. 9 8 | . . . | . 6 .\n------+-------+------\n8 . . | . 6 . | . . 3\n4 . . | 8 . 3 | . . 1\n7 . . | . 2 . | . . 6\n------+-------+------\n. 6 . | . . . | 2 8 .\n. . . | 4 1 9 | . . 5\n. . . | . 8 . | . 7 9\n")?.puzzle,    empty_corner: sudoku_solve(replace(easy, "53", ".."))?.count,}route GET /grade = {    wikipedia: sudoku_grade(easy)?,    hardest: sudoku_grade(inkala)?,}route GET /hint = {    first: sudoku_hint(easy)?,    stuck: sudoku_hint(inkala)?,}route GET /generate ? { seed: int = 7 } {    let p = sudoku_generate(seed, { clues: 30 })?    {        puzzle: p.puzzle,        clues: p.clues,        grade: p.grade.level,        unique: sudoku_solve(p.puzzle)?.unique,        solves_to_its_solution: sudoku_solve(p.puzzle)?.solution == p.solution,        same_again: sudoku_generate(seed, { clues: 30 })?.puzzle == p.puzzle,        other_seed: sudoku_generate(seed + 1, { clues: 30 })?.puzzle == p.puzzle,        drawn: sudoku_format(p.puzzle)?,    }}route GET /refused = {    conflict: sudoku_validate(wrong)?,    solve: sudoku_solve(wrong).error,    no_solution: sudoku_solve(replace(easy, "53..7....", "53..7...4"))?.solved,    short: sudoku_solve("123").error,    letter: sudoku_solve("x" + slice(easy, 1, 81)).error,    too_few: sudoku_generate(1, { clues: 10 }).error,}

//! Sudoku: puzzles read and validated, solved with a count of their solutions, generated from a seed with one solution only, graded by the techniques a person needs, and a next step explained as a hint.//! version: 1.0.0//!//! [dependencies]//! serde_json = { version = "1", features = ["preserve_order"] }use serde_json::{json, Map, Value};// A grid is 81 cells, row by row, 0 for empty.type Grid = [u8; 81];struct Rng(u64);impl Rng {    fn next(&mut self) -> u64 {        self.0 = self.0.wrapping_add(0x9E3779B97F4A7C15);        let mut z = self.0;        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);        z ^ (z >> 31)    }    fn below(&mut self, n: usize) -> usize {        (self.next() % n as u64) as usize    }    fn shuffle<T>(&mut self, v: &mut [T]) {        for i in (1..v.len()).rev() {            v.swap(i, self.below(i + 1));        }    }}fn parse(text: &str) -> Result<Grid, String> {    let mut g = [0u8; 81];    let mut n = 0;    let line_art = text.contains('|') || text.contains('+') || text.contains('-');    for c in text.chars() {        let v = match c {            '1'..='9' => c as u8 - 48,            '0' | '.' | '_' | '*' => 0,            ' ' if !line_art && !text.contains('.') && !text.contains('0') => continue,            c if c.is_whitespace() || c == '|' || c == '+' || c == '-' => continue,            c => return Err(format!("`{}` cannot be in a sudoku: digits, and `.` or `0` for an empty cell", c)),        };        if n >= 81 {            return Err("that is more than 81 cells".into());        }        g[n] = v;        n += 1;    }    if n != 81 {        return Err(format!("a sudoku has 81 cells, this has {}", n));    }    Ok(g)}fn write(g: &Grid) -> String {    g.iter().map(|v| if *v == 0 { '.' } else { (v + 48) as char }).collect()}fn rows(g: &Grid) -> Value {    json!(g.chunks(9).map(|r| r.to_vec()).collect::<Vec<_>>())}fn unit_cells(u: usize) -> [usize; 9] {    let mut o = [0; 9];    for i in 0..9 {        o[i] = match u {            0..=8 => u * 9 + i,            9..=17 => i * 9 + (u - 9),            _ => {                let b = u - 18;                (b / 3) * 27 + (b % 3) * 3 + (i / 3) * 9 + i % 3            }        };    }    o}fn unit_name(u: usize) -> String {    match u {        0..=8 => format!("row {}", u + 1),        9..=17 => format!("column {}", u - 8),        _ => format!("box {}", u - 17),    }}fn conflicts(g: &Grid) -> Vec<Value> {    let mut out = vec![];    for u in 0..27 {        let cells = unit_cells(u);        for d in 1..=9u8 {            let at: Vec<usize> = cells.iter().copied().filter(|c| g[*c] == d).collect();            if at.len() > 1 {                out.push(json!({ "value": d, "unit": unit_name(u), "cells": at.iter().map(|c| json!([c / 9 + 1, c % 9 + 1])).collect::<Vec<_>>() }));            }        }    }    out}struct Search {    row: [u16; 9],    col: [u16; 9],    bx: [u16; 9],    g: Grid,    found: usize,    first: Option<Grid>,    limit: usize,    nodes: u64,}fn box_of(c: usize) -> usize {    (c / 27) * 3 + (c % 9) / 3}impl Search {    fn new(g: &Grid, limit: usize) -> Option<Search> {        let mut s = Search { row: [0; 9], col: [0; 9], bx: [0; 9], g: *g, found: 0, first: None, limit, nodes: 0 };        for c in 0..81 {            if g[c] != 0 {                let b = 1u16 << g[c];                if (s.row[c / 9] | s.col[c % 9] | s.bx[box_of(c)]) & b != 0 {                    return None;                }                s.row[c / 9] |= b;                s.col[c % 9] |= b;                s.bx[box_of(c)] |= b;            }        }        Some(s)    }    fn go(&mut self, rng: &mut Option<Rng>) {        self.nodes += 1;        // The empty cell with the fewest candidates, which keeps the tree small.        let (mut best, mut best_n, mut best_m) = (81, 10, 0u16);        for c in 0..81 {            if self.g[c] == 0 {                let m = !(self.row[c / 9] | self.col[c % 9] | self.bx[box_of(c)]) & 0x3fe;                let n = m.count_ones();                if n < best_n {                    best = c;                    best_n = n;                    best_m = m;                    if n <= 1 {                        break;                    }                }            }        }        if best == 81 {            self.found += 1;            if self.first.is_none() {                self.first = Some(self.g);            }            return;        }        let mut ds: Vec<u8> = (1..=9).filter(|d| best_m >> d & 1 == 1).collect();        if let Some(r) = rng {            r.shuffle(&mut ds);        }        for d in ds {            let b = 1u16 << d;            self.g[best] = d;            self.row[best / 9] |= b;            self.col[best % 9] |= b;            self.bx[box_of(best)] |= b;            self.go(rng);            self.g[best] = 0;            self.row[best / 9] &= !b;            self.col[best % 9] &= !b;            self.bx[box_of(best)] &= !b;            if self.found >= self.limit {                return;            }        }    }}fn count(g: &Grid, limit: usize) -> (usize, Option<Grid>) {    match Search::new(g, limit) {        None => (0, None),        Some(mut s) => {            s.go(&mut None);            (s.found, s.first)        }    }}/// A puzzle read from 81 characters or a drawn grid, `.` or `0` for empty: { puzzle, rows, clues }. Spaces, `|`, `-` and `+` are passed over.pub fn sudoku_parse(text: &str) -> Result<Value, String> {    let g = parse(text)?;    Ok(json!({ "puzzle": write(&g), "rows": rows(&g), "clues": g.iter().filter(|v| **v != 0).count() }))}/// A grid checked by the rules: { valid, complete, conflicts }, each conflict naming the value, the unit and its cells by row and column from 1.pub fn sudoku_validate(text: &str) -> Result<Value, String> {    let g = parse(text)?;    let c = conflicts(&g);    Ok(json!({ "valid": c.is_empty(), "complete": g.iter().all(|v| *v != 0), "conflicts": c }))}/// A puzzle solved: { solved, solution, rows, unique, count }. `count` stops at 2, which is all "not unique" needs; a puzzle with no solution has `solved` false. Conflicting givens are an error value.pub fn sudoku_solve(text: &str) -> Result<Value, String> {    let g = parse(text)?;    if let Some(c) = conflicts(&g).first() {        return Err(format!("{} has {} twice", c["unit"].as_str().unwrap_or(""), c["value"]));    }    let (n, first) = count(&g, 2);    Ok(match first {        Some(s) => json!({ "solved": true, "solution": write(&s), "rows": rows(&s), "unique": n == 1, "count": n }),        None => json!({ "solved": false, "solution": null, "rows": null, "unique": false, "count": 0 }),    })}#[derive(Clone)]struct Board {    g: Grid,    cand: [u16; 81],}fn board(g: &Grid) -> Board {    let mut b = Board { g: *g, cand: [0; 81] };    for c in 0..81 {        if g[c] == 0 {            b.cand[c] = 0x3fe;        }    }    for c in 0..81 {        if g[c] != 0 {            eliminate_peers(&mut b, c, g[c]);        }    }    b}fn peers_share(a: usize, b: usize) -> bool {    a != b && (a / 9 == b / 9 || a % 9 == b % 9 || box_of(a) == box_of(b))}fn eliminate_peers(b: &mut Board, c: usize, d: u8) {    for p in 0..81 {        if peers_share(c, p) {            b.cand[p] &= !(1 << d);        }    }}fn place(b: &mut Board, c: usize, d: u8) {    b.g[c] = d;    b.cand[c] = 0;    eliminate_peers(b, c, d);}struct Step {    technique: &'static str,    cell: Option<(usize, u8)>,    removed: Vec<(usize, u8)>,    why: String,}fn cell_name(c: usize) -> String {    format!("r{}c{}", c / 9 + 1, c % 9 + 1)}fn digits(m: u16) -> Vec<u8> {    (1..=9).filter(|d| m >> d & 1 == 1).collect()}fn naked_single(b: &Board) -> Option<Step> {    for c in 0..81 {        if b.g[c] == 0 && b.cand[c].count_ones() == 1 {            let d = digits(b.cand[c])[0];            return Some(Step { technique: "naked single", cell: Some((c, d)), removed: vec![], why: format!("{} can only be {}", cell_name(c), d) });        }    }    None}fn hidden_single(b: &Board) -> Option<Step> {    for u in 0..27 {        for d in 1..=9u8 {            let at: Vec<usize> = unit_cells(u).iter().copied().filter(|c| b.cand[*c] >> d & 1 == 1).collect();            if at.len() == 1 {                return Some(Step { technique: "hidden single", cell: Some((at[0], d)), removed: vec![], why: format!("{} fits only {} in {}", d, cell_name(at[0]), unit_name(u)) });            }        }    }    None}fn locked(b: &Board) -> Option<Step> {    for u in 0..27 {        for d in 1..=9u8 {            let at: Vec<usize> = unit_cells(u).iter().copied().filter(|c| b.cand[*c] >> d & 1 == 1).collect();            if at.len() < 2 {                continue;            }            for v in 0..27 {                if v == u {                    continue;                }                let inside = unit_cells(v);                if at.iter().all(|c| inside.contains(c)) {                    let removed: Vec<(usize, u8)> = inside.iter().copied().filter(|c| !at.contains(c) && b.cand[*c] >> d & 1 == 1).map(|c| (c, d)).collect();                    if !removed.is_empty() {                        return Some(Step { technique: "locked candidates", cell: None, removed, why: format!("in {}, {} lies only in {}, so it leaves the rest of {}", unit_name(u), d, unit_name(v), unit_name(v)) });                    }                }            }        }    }    None}fn subsets(items: &[usize], k: usize, start: usize, cur: &mut Vec<usize>, out: &mut Vec<Vec<usize>>) {    if cur.len() == k {        out.push(cur.clone());        return;    }    for i in start..items.len() {        cur.push(items[i]);        subsets(items, k, i + 1, cur, out);        cur.pop();    }}fn naked_set(b: &Board, k: usize) -> Option<Step> {    let name = if k == 2 { "naked pair" } else { "naked triple" };    for u in 0..27 {        let open: Vec<usize> = unit_cells(u).iter().copied().filter(|c| b.g[*c] == 0).collect();        let mut sets = vec![];        subsets(&open, k, 0, &mut vec![], &mut sets);        for s in sets {            let m = s.iter().fold(0u16, |a, c| a | b.cand[*c]);            if m.count_ones() as usize != k {                continue;            }            let mut removed = vec![];            for c in &open {                if !s.contains(c) {                    for d in digits(b.cand[*c] & m) {                        removed.push((*c, d));                    }                }            }            if !removed.is_empty() {                return Some(Step { technique: name, cell: None, removed, why: format!("{} hold only {:?} in {}", s.iter().map(|c| cell_name(*c)).collect::<Vec<_>>().join(", "), digits(m), unit_name(u)) });            }        }    }    None}fn hidden_pair(b: &Board) -> Option<Step> {    for u in 0..27 {        let cells = unit_cells(u);        for d1 in 1..=8u8 {            for d2 in d1 + 1..=9u8 {                let a: Vec<usize> = cells.iter().copied().filter(|c| b.cand[*c] >> d1 & 1 == 1).collect();                let e: Vec<usize> = cells.iter().copied().filter(|c| b.cand[*c] >> d2 & 1 == 1).collect();                if a.len() == 2 && a == e {                    let keep = 1u16 << d1 | 1u16 << d2;                    let mut removed = vec![];                    for c in &a {                        for d in digits(b.cand[*c] & !keep) {                            removed.push((*c, d));                        }                    }                    if !removed.is_empty() {                        return Some(Step { technique: "hidden pair", cell: None, removed, why: format!("{} and {} fit only {} and {} in {}", d1, d2, cell_name(a[0]), cell_name(a[1]), unit_name(u)) });                    }                }            }        }    }    None}fn x_wing(b: &Board) -> Option<Step> {    for by_row in [true, false] {        for d in 1..=9u8 {            let lines: Vec<(usize, Vec<usize>)> = (0..9)                .map(|l| (l, (0..9).filter(|p| b.cand[if by_row { l * 9 + p } else { p * 9 + l }] >> d & 1 == 1).collect::<Vec<usize>>()))                .filter(|x| x.1.len() == 2)                .collect();            for i in 0..lines.len() {                for j in i + 1..lines.len() {                    if lines[i].1 != lines[j].1 {                        continue;                    }                    let mut removed = vec![];                    for p in &lines[i].1 {                        for l in 0..9 {                            if l == lines[i].0 || l == lines[j].0 {                                continue;                            }                            let c = if by_row { l * 9 + p } else { p * 9 + l };                            if b.cand[c] >> d & 1 == 1 {                                removed.push((c, d));                            }                        }                    }                    if !removed.is_empty() {                        return Some(Step { technique: "x-wing", cell: None, removed, why: format!("{} forms an x-wing in {}s {} and {}", d, if by_row { "row" } else { "column" }, lines[i].0 + 1, lines[j].0 + 1) });                    }                }            }        }    }    None}fn next_step(b: &Board) -> Option<Step> {    hidden_single(b).or_else(|| naked_single(b)).or_else(|| locked(b)).or_else(|| naked_set(b, 2)).or_else(|| hidden_pair(b)).or_else(|| naked_set(b, 3)).or_else(|| x_wing(b))}fn apply(b: &mut Board, s: &Step) {    if let Some((c, d)) = s.cell {        place(b, c, d);    }    for (c, d) in &s.removed {        b.cand[*c] &= !(1 << d);    }}fn grade_of(g: &Grid) -> Value {    let mut b = board(g);    let mut counts: Vec<(String, u32)> = vec![];    let mut hardest = 0;    while b.g.iter().any(|v| *v == 0) {        let Some(s) = next_step(&b) else {            break;        };        let rank = match s.technique {            "hidden single" => 1,            "naked single" => 2,            "locked candidates" => 3,            "naked pair" | "hidden pair" => 4,            _ => 5,        };        hardest = hardest.max(rank);        match counts.iter_mut().find(|c| c.0 == s.technique) {            Some(c) => c.1 += 1,            None => counts.push((s.technique.to_string(), 1)),        }        apply(&mut b, &s);    }    let done = b.g.iter().all(|v| *v != 0);    let level = if !done {        "evil"    } else {        match hardest {            0 | 1 => "easy",            2 => "medium",            3 | 4 => "hard",            _ => "expert",        }    };    let map: Map<String, Value> = counts.iter().map(|(k, v)| (k.clone(), json!(v))).collect();    json!({ "level": level, "solved_by_logic": done, "techniques": map, "left": b.g.iter().filter(|v| **v == 0).count() })}/// How hard a puzzle is for a person, by the hardest technique it needs: { level, solved_by_logic, techniques, left }. easy needs hidden singles only, medium naked singles, hard locked candidates and pairs, expert triples and x-wings; evil is what these cannot finish.pub fn sudoku_grade(text: &str) -> Result<Value, String> {    let g = parse(text)?;    if !conflicts(&g).is_empty() {        return Err("the puzzle breaks the rules, so it cannot be graded".into());    }    Ok(grade_of(&g))}/// The next logical step: { technique, row, column, value, explanation } for a placed digit, or { technique, removes, explanation } for candidates ruled out; { technique: null } when the listed techniques run dry.pub fn sudoku_hint(text: &str) -> Result<Value, String> {    let g = parse(text)?;    if !conflicts(&g).is_empty() {        return Err("the puzzle breaks the rules, so no hint fits".into());    }    if g.iter().all(|v| *v != 0) {        return Err("the puzzle is complete".into());    }    let mut b = board(&g);    loop {        let Some(s) = next_step(&b) else {            return Ok(json!({ "technique": null, "explanation": "no technique here finishes this: the next step needs a guess" }));        };        match s.cell {            Some((c, d)) => return Ok(json!({ "technique": s.technique, "row": c / 9 + 1, "column": c % 9 + 1, "value": d, "explanation": s.why })),            None => {                let removes: Vec<Value> = s.removed.iter().map(|(c, d)| json!({ "row": c / 9 + 1, "column": c % 9 + 1, "value": d })).collect();                if !removes.is_empty() {                    return Ok(json!({ "technique": s.technique, "removes": removes, "explanation": s.why }));                }                apply(&mut b, &s);            }        }    }}fn full(rng: &mut Rng) -> Grid {    let mut s = Search::new(&[0; 81], 1).unwrap();    let mut r = Some(Rng(rng.next()));    s.go(&mut r);    s.first.unwrap_or([0; 81])}/// A puzzle made from a seed, with exactly one solution: { puzzle, solution, clues, grade, seed }. `options`: { clues (the fewest to aim for, default 28, at least 22), symmetric (default true) }. The same seed gives the same puzzle.pub fn sudoku_generate(seed: i64, options: serde_json::Value) -> Result<Value, String> {    let aim = options.get("clues").and_then(|v| v.as_i64()).unwrap_or(28);    if !(22..=81).contains(&aim) {        return Err(format!("clues is 22 to 81, not {}: fewer than 22 takes far too long to find", aim));    }    let symmetric = options.get("symmetric").and_then(|v| v.as_bool()).unwrap_or(true);    let mut rng = Rng(seed as u64);    let solution = full(&mut rng);    let mut g = solution;    let mut order: Vec<usize> = (0..81).collect();    rng.shuffle(&mut order);    let mut clues = 81;    for c in order {        if clues <= aim as usize {            break;        }        let mate = 80 - c;        if g[c] == 0 {            continue;        }        let (a, m) = (g[c], g[mate]);        g[c] = 0;        if symmetric {            g[mate] = 0;        }        if count(&g, 2).0 != 1 {            g[c] = a;            if symmetric {                g[mate] = m;            }        } else {            clues -= if symmetric && c != mate && m != 0 { 2 } else { 1 };        }    }    Ok(json!({ "puzzle": write(&g), "solution": write(&solution), "clues": clues, "grade": grade_of(&g), "seed": seed }))}/// A grid drawn as text in rows of three boxes, for a log or a `<pre>`.pub fn sudoku_format(text: &str) -> Result<String, String> {    let g = parse(text)?;    let mut o = String::new();    for r in 0..9 {        if r % 3 == 0 && r > 0 {            o.push_str("------+-------+------\n");        }        for c in 0..9 {            if c % 3 == 0 && c > 0 {                o.push_str("| ");            }            o.push(if g[r * 9 + c] == 0 { '.' } else { (g[r * 9 + c] + 48) as char });            o.push(if c == 8 { '\n' } else { ' ' });        }    }    Ok(o)}