Created
August 3, 2021 17:28
-
-
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)
This file contains hidden or 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
// 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