Skip to content

Instantly share code, notes, and snippets.

@n7itro
Created November 13, 2023 17:44
Show Gist options
  • Save n7itro/1adeb3caeb79b225ab869de69419ae74 to your computer and use it in GitHub Desktop.
Save n7itro/1adeb3caeb79b225ab869de69419ae74 to your computer and use it in GitHub Desktop.
Sudoku solver using backtracking algorithm written in Nim
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