Sudoku

Git repository

Problem statement

This program generates every possible solved sudoku board in an order with no repeats.

A solved sudoku board is a $9x9$ board for which every row and column contains each of the numbers $1\dots 9$ exactly once. Additionally, it is tiled with $3x3$ squares, all of which must contain each number from $1$ to $9$. Clearly there must be a bijective mapping for all $3$ requirements.

Algorithm

The program is essentially just a massive iterator. It places digits in every possible position from left to right and then top to bottom. So the first digit to be placed is a $1$ in the top left corner of the top left square. This makes the top row and leftmost column unavailable for future picks. And so on. An iterator is constructed over every possible way $1$ can be placed.

let squares = vec![
    vec![0, 1, 2, 9, 10, 11, 18, 19, 20],
    vec![3, 4, 5, 12, 13, 14, 21, 22, 23],
    vec![6, 7, 8, 15, 16, 17, 24, 25, 26],
    vec![27, 28, 29, 36, 37, 38, 45, 46, 47],
    vec![30, 31, 32, 39, 40, 41, 48, 49, 50],
    vec![33, 34, 35, 42, 43, 44, 51, 52, 53],
    vec![54, 55, 56, 63, 64, 65, 72, 73, 74],
    vec![57, 58, 59, 66, 67, 68, 75, 76, 77],
    vec![60, 61, 62, 69, 70, 71, 78, 79, 80],
];

let mut a = layer(&squares);

fn layer(squares: &Vec<Vec<u8>>) -> impl Iterator<Item = [u8; 9]> {
    let a = {
    let s0 = squares[0].iter();
    s0.flat_map(move |&o| {
        let s1 = squares[1].iter().filter(move |&&d| d / 3 != o / 3 + 1);
        s1.flat_map(move |&tw| {
            let s2 = squares[2].iter().filter(move |&&d| (d / 3 != o / 3 + 2) & (d / 3 != tw / 3 + 1));
            s2.flat_map(move |&th| {
                let s3 = squares[3].iter().filter(move |&&d| d % 3 != o % 3);
                s3.flat_map(move |&fo| {
                    let s4 = squares[4].iter().filter(move |&&d| (d % 3 != tw % 3) & (d / 3 != fo / 3 + 1));
                    s4.flat_map(move |&fi| {
                        let s5 = squares[5].iter().filter(move |&&d| (d % 3 != th % 3) & (d / 3 != fo / 3 + 2) & (d / 3 != fi / 3 + 1));
                        s5.flat_map(move |&si| {
                            let s6 = squares[6].iter().filter(move |&&d| (d % 3 != o % 3) & (d % 3 != fo % 3));
                            s6.flat_map(move |&se| {
                                let s7 = squares[7].iter().filter(move |&&d| (d % 3 != tw % 3) & (d % 3 != fi % 3) & (d / 3 != se / 3 + 1));
                                s7.flat_map(move |&e| {
                                    let s8 = squares[8].iter().filter(move |&&d| (d % 3 != th % 3) & (d % 3 != si % 3) & (d / 3 != se / 3 + 2) & (d / 3 != e / 3 + 1));
                                    s8.map(move |&n| [o, tw, th, fo, fi, si, se, e, n])
                                })
                            })
                        })
                    })
                })
            })
        })
    })};
    a
}

Until the elements of this iterator are exhausted, taken squares are removed and the process is repeated to create an iterator of $2$ placements.

loop {
    let _ = match a.next() {
        None => break,
        Some(val) => {
            let mut squares2 = squares.clone();
            for i in 0..9 {
                let index = squares2[i].iter().position(|x| *x == val[i]).unwrap();
                squares2[i].remove(index);
            }
            let mut b = layer(&squares2);

This is further repeated for $3,\dots,9$. A count is updated, and printed every time the $4$s change position. Speed is heavily bottlenecked if the boards are displayed in any way.

Future work

Generating minimal puzzles rather than solved boards.

Displaying solutions like every UUID.