Skip to content

Instantly share code, notes, and snippets.

@HumanEquivalentUnit
Created August 3, 2021 17:28
Show Gist options
  • Save HumanEquivalentUnit/6daf46bd4cfe4cc3dbdf296a2eb6a5ab to your computer and use it in GitHub Desktop.
Save HumanEquivalentUnit/6daf46bd4cfe4cc3dbdf296a2eb6a5ab to your computer and use it in GitHub Desktop.
A port of a PowerShell Sudoku brute-force to Rust, staying as close as possible to the original (without knowing Rust very well)
// a naive Rust port of a PowerShell brute-force Sudoku solver
// trying to keep everything as close to the same implementation as possible.
fn main() {
let mut board : [[i8; 9]; 9] = [
[0,0,0, 0,3,0, 0,0,0],
[0,0,1, 0,7,6, 9,4,0],
[0,8,0, 9,0,0, 0,0,0],
[0,4,0, 0,0,1, 0,0,0],
[0,2,8, 0,9,0, 0,0,0],
[0,0,0, 0,0,0, 1,6,0],
[7,0,0, 8,0,0, 0,0,0],
[0,0,0, 0,0,0, 4,0,2],
[0,9,0, 0,1,0, 3,0,0]
];
print_board(&board);
let _ = solve(&mut board);
println!("\n");
print_board(&board);
}
fn print_board(board : &[[i8; 9]; 9]) {
for row in 0..=8 {
if (row % 3 == 0) && (0 != row) {
println!("- - - - - - - - - - -");
}
for col in 0..=8 {
if (col % 3 == 0) && (0 != col) {
print!("| ");
}
if 8 == col {
println!("{}", board[row][col]);
} else {
print!("{} ", board[row][col]);
}
}
}
}
fn valid(board : &[[i8; 9]; 9], num: i8, row: usize, col: usize) -> bool {
// check row
for i in 0..=8 {
if (board[row][i] == num) && (col != i) {
return false;
}
}
// check col
for i in 0..=8 {
if (board[i][col] == num) && (row != i) {
return false;
}
}
// check box
let box_x = col / 3;
let box_y = row / 3;
for i in (3*box_y)..=(3*box_y+2) {
for j in (3*box_x)..=(3*box_x+2) {
if (board[i][j] == num) && (i != col) && (j != col) {
return false;
}
}
}
return true;
}
fn find_empty(board : &[[i8; 9]; 9]) -> (i8, i8) {
for row in 0..=8 {
for col in 0..=8 {
if 0 == board[row][col] {
return ((row as i8), (col as i8));
}
}
}
return (-1, -1);
}
fn solve(board: &mut[[i8; 9]; 9]) -> bool {
let (row, col) = find_empty(&board);
if (row < 0) || (col < 0) { // no empties found, board solved
return true;
} else {
//print!("\rsolving... {}, {}", row, col);
}
for i in 1..=9 {
if valid(&board, i, row as usize, col as usize) {
board[row as usize][col as usize] = i; // try assigning this value and solve from there
if solve(board) {
return true;
}
board[row as usize][col as usize] = 0; // couldn't solve, revert change
}
}
return false; // no solution found after exhaustive search
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment