Sudoku solver for demonstration purposes

sudoku.go

package main

import (
	"fmt"
)

type Sudoku = [9][9]int

func main() {
	unsolved := Sudoku{
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
	}

	solved := Sudoku{
		{7, 2, 6, 4, 9, 3, 8, 1, 5},
		{3, 1, 5, 7, 2, 8, 9, 4, 6},
		{4, 8, 9, 6, 5, 1, 2, 3, 7},
		{8, 5, 2, 1, 4, 7, 6, 9, 3},
		{6, 7, 3, 9, 8, 5, 1, 2, 4},
		{9, 4, 1, 3, 6, 2, 7, 5, 8},
		{1, 9, 4, 8, 3, 6, 5, 7, 2},
		{5, 6, 7, 2, 1, 4, 3, 8, 9},
		{2, 3, 8, 5, 7, 9, 4, 6, 1},
	}

	printGrid(unsolved)
	printSolved(unsolved)
	printGrid(solved)
	printSolved(solved)
}

func printGrid(grid Sudoku) {
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			fmt.Printf("%2d ", grid[i][j])
		}
		fmt.Println()
	}
}

func printSolved(grid Sudoku) {
	if isSolved(grid) {
		fmt.Println("Board is solved")
	} else {
		fmt.Println("Board is not solved")
	}
}

func isSolved(grid Sudoku) bool {
	// Check rows and columns
	for i := 0; i < 9; i++ {
		row := make(map[int]bool)
		col := make(map[int]bool)
		for j := 0; j < 9; j++ {
			if row[grid[i][j]] || col[grid[j][i]] {
				return false
			}
			row[grid[i][j]] = true
			col[grid[j][i]] = true
		}

		// Check lengths of row and column
		if !isFullGroup(row) || !isFullGroup(col) {
			return false
		}
	}

	// Check subgrids
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			subgrid := make(map[int]bool)
			for x := 0; x < 3; x++ {
				for y := 0; y < 3; y++ {
					if subgrid[grid[i*3+x][j*3+y]] {
						return false
					}
					subgrid[grid[i*3+x][j*3+y]] = true
				}
			}

			// Check length of subgrid
			if !isFullGroup(subgrid) {
				return false
			}
		}
	}

	return true
}

func isFullGroup(group map[int]bool) bool {
	_, ok := group[0]
	return len(group) == 9 && !ok
}

sudoku.py

from collections import defaultdict
from typing import DefaultDict, List, Set

# Module-level constants
_GRID_SIZE: int = 9
_SUBGRID_SIZE: int = 3
_FULL_NUMS: Set[int] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
_NULL: int = 0

# Custom type hinting
Grid = List[List[int]]


def is_solved(grid: Grid) -> bool:
    """Check if Sudoku grid is solved.

    A Sudoku grid is solved if the following is true:

    - All rows have the numbers 1..9
    - All columns have the numbers 1..9
    - All 3x3 subgrids have the numbers 1..9

    :param grid: 2-dimensional list of numbers
    :return: whether the grid is solved or not
    """
    subgrid_mapping: DefaultDict[int, set] = defaultdict(set)
    for i in range(_GRID_SIZE):
        current_row: Set[int] = set()
        current_col: Set[int] = set()

        for j in range(_GRID_SIZE):
            current_row.add(grid[i][j])
            current_col.add(grid[j][i])

            subgrid_row = i // _SUBGRID_SIZE
            subgrid_col = j // _SUBGRID_SIZE
            subgrid_idx = subgrid_row * _SUBGRID_SIZE + subgrid_col
            subgrid_mapping[subgrid_idx].add(grid[i][j])

        if current_row != _FULL_NUMS or current_col != _FULL_NUMS:
            return False

    return all(grid_vals == _FULL_NUMS for grid_vals in subgrid_mapping.values())


def can_solve_sudoku(grid: Grid) -> bool:
    """Check if Sudoku grid can be solved.

    Note that the Sudoku grid becomes the first solution that
    the function finds when it returns True. Otherwise, the
    grid remains as-is.

    :param grid: 2-dimensional list of numbers
    :return: whether the grid can be solved or not
    """
    for i in range(_GRID_SIZE):
        for j in range(_GRID_SIZE):
            # This grid cell has not been solved yet, so let's
            # try setting some numbers and hope for the best!
            if grid[i][j] == _NULL:
                for num in _FULL_NUMS:
                    # Fill the cell (i, j) with any number
                    grid[i][j] = num

                    # If the Sudoku grid can be solved with the filled
                    # cell, then we don't check any further and simply
                    # return True. When the function exits, the grid
                    # is the first solution that was found
                    if can_solve_sudoku(grid):
                        return True

                    # If the Sudoku grid cannot be solved with the filled
                    # cell, then we unfill it so that another number can
                    # be filled. This is what we refer to as backtracking
                    grid[i][j] = _NULL
    return is_solved(grid)


def print_sudoku(grid: Grid) -> None:
    """Print Sudoku grid.

    Example output:

    -------------------------------------
    | 7 | 2 | 6 | 4 | 9 | 3 | 8 | 1 | 5 |
    -------------------------------------
    | 3 | 1 | 5 | 7 | 2 | 8 | 9 | 4 | 6 |
    -------------------------------------
    | 4 | 8 | 9 | 6 | 5 | 1 | 2 | 3 | 7 |
    -------------------------------------
    | 8 | 5 | 2 | 1 | 4 | 7 | 6 | 9 | 3 |
    -------------------------------------
    | 6 | 7 | 3 | 9 | 8 | 5 | 1 | 2 | 4 |
    -------------------------------------
    | 9 | 4 | 1 | 3 | 6 | 2 | 7 | 5 | 8 |
    -------------------------------------
    | 1 | 9 | 4 | 8 | 3 | 6 | 5 | 7 | 2 |
    -------------------------------------
    | 5 | 6 | 7 | 2 | 1 | 4 | 3 | 8 | 9 |
    -------------------------------------
    | 2 | 3 | 8 | 5 | 7 | 9 | 4 | 6 | 1 |
    -------------------------------------

    :param grid: 2-dimensional list of numbers
    """

    def _number_repr(n: int):
        return str(n) if n > _NULL else " "

    def _grid_row_line():
        return "-" * 37

    for row in range(_GRID_SIZE):
        print(_grid_row_line())
        grid_row_data = [_number_repr(n) for n in grid[row]]
        print(f"| {' | '.join(grid_row_data)} |")
    print(_grid_row_line())
    print("")


def main() -> None:
    # An empty grid with invalid numbers
    unsolved_grid: Grid = [[_NULL] * _GRID_SIZE for _ in range(_GRID_SIZE)]
    assert not is_solved(unsolved_grid)

    # A complete grid with valid numbers
    # fmt: off
    solved_grid: Grid = [
        [7, 2, 6, 4, 9, 3, 8, 1, 5],
        [3, 1, 5, 7, 2, 8, 9, 4, 6],
        [4, 8, 9, 6, 5, 1, 2, 3, 7],
        [8, 5, 2, 1, 4, 7, 6, 9, 3],
        [6, 7, 3, 9, 8, 5, 1, 2, 4],
        [9, 4, 1, 3, 6, 2, 7, 5, 8],
        [1, 9, 4, 8, 3, 6, 5, 7, 2],
        [5, 6, 7, 2, 1, 4, 3, 8, 9],
        [2, 3, 8, 5, 7, 9, 4, 6, 1],
    ]
    # fmt: on

    assert is_solved(solved_grid)

    # A partial grid similar to the one above, with empty numbers
    # to prove that can_solve_sudoku finds the correct solution
    # fmt: off
    another_grid: Grid = [
        [7, 2, 6, 4, 9, 3, 8, 1, 5],
        [3, _NULL, 5, 7, 2, 8, 9, 4, 6],
        [4, 8, 9, 6, 5, 1, _NULL, 3, 7],
        [8, 5, 2, 1, 4, 7, 6, 9, 3],
        [6, 7, 3, 9, _NULL, 5, 1, 2, 4],
        [9, 4, 1, 3, 6, 2, 7, 5, 8],
        [1, 9, 4, 8, 3, 6, 5, 7, 2],
        [5, _NULL, 7, 2, 1, 4, 3, 8, 9],
        [2, 3, 8, 5, 7, 9, 4, 6, _NULL],
    ]
    # fmt: on

    print("NOT SOLVED.")
    print_sudoku(another_grid)

    print("SOLVING...\n")
    assert not is_solved(another_grid)
    assert can_solve_sudoku(another_grid)
    assert is_solved(another_grid)

    # After running can_solve_sudoku
    print("SOLVED.")
    print_sudoku(another_grid)


if __name__ == "__main__":
    main()

sudoku.rs

use std::collections::{HashMap, HashSet};

type Sudoku = [[i32; 9]; 9];

fn main() {
    let unsolved: Sudoku = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ];

    let solved: Sudoku = [
        [7, 2, 6, 4, 9, 3, 8, 1, 5],
        [3, 1, 5, 7, 2, 8, 9, 4, 6],
        [4, 8, 9, 6, 5, 1, 2, 3, 7],
        [8, 5, 2, 1, 4, 7, 6, 9, 3],
        [6, 7, 3, 9, 8, 5, 1, 2, 4],
        [9, 4, 1, 3, 6, 2, 7, 5, 8],
        [1, 9, 4, 8, 3, 6, 5, 7, 2],
        [5, 6, 7, 2, 1, 4, 3, 8, 9],
        [2, 3, 8, 5, 7, 9, 4, 6, 1],
    ];

    print_grid(&unsolved);
    print_solved(&unsolved);
    print_grid(&solved);
    print_solved(&solved);
}

fn print_grid(grid: &Sudoku) {
    for row in grid {
        for cell in row {
            print!("{:2} ", cell);
        }
        println!();
    }
}

fn print_solved(grid: &Sudoku) {
    if is_solved(&grid) {
        println!("Board is solved");
    } else {
        println!("Board is not solved");
    }
}

fn is_solved(grid: &Sudoku) -> bool {
    let mut subgrids: HashMap<usize, HashSet<i32>> = HashMap::new();
    for i in 0..9 {
        let mut row: HashSet<i32> = HashSet::new();
        let mut col: HashSet<i32> = HashSet::new();
        for j in 0..9 {
            row.insert(grid[i][j]);
            col.insert(grid[j][i]);

            let key: usize = (i / 3) * 3 + (j / 3);
            let subgrid = subgrids.entry(key).or_insert(HashSet::new());
            subgrid.insert(grid[i][j]);
        }
        if !is_full_group(&row) || !is_full_group(&col) {
            return false;
        }
    }
    return subgrids.values().all(|gs: &HashSet<i32>| is_full_group(gs));
}

fn is_full_group(set: &HashSet<i32>) -> bool {
    set.len() == 9 && !set.contains(&0)
}