Last active
October 7, 2024 05:39
-
-
Save huangsam/c878d1eb94e8693bb3e3fe03c79b7595 to your computer and use it in GitHub Desktop.
Sudoku solver for demonstration purposes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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