Created
November 13, 2023 17:44
-
-
Save n7itro/1adeb3caeb79b225ab869de69419ae74 to your computer and use it in GitHub Desktop.
Sudoku solver using backtracking algorithm written in Nim
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
import strutils | |
var grid = [ | |
[6, 0, 0, 0, 0, 4, 5, 3, 0], | |
[8, 0, 0, 0, 5, 0, 0, 0, 9], | |
[5, 9, 4, 0, 0, 0, 8, 2, 0], | |
[0, 5, 0, 3, 0, 0, 0, 0, 0], | |
[0, 3, 0, 0, 0, 0, 0, 8, 5], | |
[0, 0, 2, 0, 0, 1, 0, 7, 0], | |
[2, 0, 8, 0, 0, 0, 0, 5, 0], | |
[0, 0, 0, 7, 0, 0, 0, 1, 0], | |
[0, 0, 0, 0, 0, 2, 4, 0, 6], | |
] | |
proc safe(row, col, num: int): bool = | |
for rows in grid: | |
if rows[col] == num or num in grid[row]: | |
return false | |
for i in 0 ..< 3: | |
for j in 0 ..< 3: | |
let cell = grid[row - (row mod 3) + i][col - (col mod 3) + j] | |
if cell == num: | |
return false | |
true | |
proc solve: bool = | |
for row in 0..8: | |
for col in 0..8: | |
if grid[row][col] != 0: | |
continue | |
for value in 1..9: | |
if not safe(row, col, value): | |
continue | |
grid[row][col] = value | |
if solve(): | |
return true | |
grid[row][col] = 0 | |
return false | |
true | |
if solve(): | |
for row in grid: | |
echo join(row, " ") | |
else: | |
echo "No solution was found." |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment