extern crate dlx;
use dlx::{Index, Row};
fn main() {
let mut solver = dlx::Solver::new(324, sudoku_cover_matrix().into_iter());
let stdin = ::std::io::stdin();
let mut line = String::new();
loop {
line.clear();
if stdin.read_line(&mut line).unwrap() == 0 {
return;
}
let mut solutions = Solutions { solved: false };
solver.solve(rows_from_line(line.trim()), &mut solutions);
if !solutions.solved {
println!("No solution");
}
}
}
const SIZE_RT: dlx::Index = 3;
const SIZE: dlx::Index = 9;
const SIZE_SQ: dlx::Index = 81;
fn sudoku_cover_matrix() -> Vec<Row> {
let mut matrix = Vec::new();
for num in 0..SIZE {
for row in 0..SIZE {
for col in 0..SIZE {
matrix.push(sudoku_cover_row(num, row, col));
}
}
}
matrix
}
fn sudoku_cover_row(num: Index, row: Index, col: Index) -> Vec<Index> {
let bx = ((row / SIZE_RT) * SIZE_RT) + (col / SIZE_RT);
vec![
row * SIZE + col,
SIZE_SQ + num * SIZE + col,
SIZE_SQ * 2 + num * SIZE + row,
SIZE_SQ * 3 + num * SIZE + bx,
]
}
#[cfg_attr(feature = "cargo-clippy", allow(needless_range_loop))]
fn rows_from_line(line: &str) -> Vec<Row> {
if line.len() != SIZE_SQ {
panic!("unknown format");
}
let mut rows = Vec::new();
let line = line.as_bytes();
for row in 0..SIZE {
for col in 0..SIZE {
let c = line[row * SIZE + col];
if c < b'1' || c > b'9' {
continue;
}
let num = c - b'1';
rows.push(sudoku_cover_row(num as Index, row, col));
}
}
rows
}
struct Solutions {
solved: bool,
}
impl dlx::Solutions for Solutions {
fn push(&mut self, sol: dlx::Solution) -> bool {
self.solved = true;
let mut grid = vec![b'0'; SIZE_SQ];
for row in sol {
let cell_row = row[0] / SIZE;
let dlx_col = row[1] - SIZE_SQ;
let cell_num = dlx_col / SIZE;
let cell_col = dlx_col % SIZE;
grid[cell_row * SIZE + cell_col] = b'1' + cell_num as u8;
}
println!("{}", ::std::str::from_utf8(&grid).unwrap());
false
}
}