Skip to content

Instantly share code, notes, and snippets.

@huangsam
Last active October 7, 2024 05:39
Show Gist options
  • Save huangsam/c878d1eb94e8693bb3e3fe03c79b7595 to your computer and use it in GitHub Desktop.
Save huangsam/c878d1eb94e8693bb3e3fe03c79b7595 to your computer and use it in GitHub Desktop.
Sudoku solver for demonstration purposes
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
}
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()
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment