summaryrefslogtreecommitdiff
path: root/sudoku
diff options
context:
space:
mode:
authorj-james2022-11-15 07:56:36 +0000
committerj-james2022-11-15 07:56:36 +0000
commit06615702d85d5640984ab0e6a7b3155df4d261a3 (patch)
tree5312a622f513cb6650623cfbc1ce662eac2f5f45 /sudoku
parent667253f48d20f76aff54f7ce9464b13c169ad96e (diff)
Add Sudoku solver
Diffstat (limited to 'sudoku')
-rw-r--r--sudoku/sudoku.nim100
1 files changed, 100 insertions, 0 deletions
diff --git a/sudoku/sudoku.nim b/sudoku/sudoku.nim
new file mode 100644
index 0000000..aa0672b
--- /dev/null
+++ b/sudoku/sudoku.nim
@@ -0,0 +1,100 @@
+# Simple, inefficient sudoku solver.
+# But it's cute. Written on a plane.
+import std/[sequtils, sugar]
+type Board = seq[seq[int]]
+
+const input: Board = @[
+ @[0,5,8, 6,0,0, 0,4,0],
+ @[1,0,0, 7,0,0, 0,9,0],
+ @[0,6,0, 0,0,4, 8,0,0],
+ @[0,8,0, 9,0,0, 0,0,0],
+ @[4,0,0, 0,1,0, 0,0,2],
+ @[0,0,0, 0,0,3, 0,6,0],
+ @[0,0,2, 3,0,0, 0,7,0],
+ @[0,9,0, 0,0,1, 0,0,4],
+ @[0,1,0, 0,0,7, 5,3,0]
+]
+
+func valid_input(board: Board): bool =
+ for j in 0 ..< 9:
+ for i in 0 ..< 9:
+ if input[i][j] != 0 and input[i][j] != board[i][j]:
+ return false
+ return true
+
+assert input.valid_input()
+
+func valid_rows(board: Board): bool =
+ for i in 0 ..< 9:
+ var used: seq[int]
+ for j in 0 ..< 9:
+ var num = board[i][j]
+ if num in used:
+ return false
+ if num != 0:
+ used.add(num)
+ return true
+
+assert input.valid_rows()
+
+func valid_columns(board: Board): bool =
+ for j in 0 ..< 9:
+ var used: seq[int]
+ for i in 0 ..< 9:
+ var num = board[i][j]
+ if num in used:
+ return false
+ if num != 0:
+ used.add(num)
+ return true
+
+assert input.valid_rows()
+
+func valid_boxes(board: Board): bool =
+ for l in 0 ..< 3:
+ for k in 0 ..< 3:
+ var used: seq[int]
+ for j in 0 ..< 3:
+ for i in 0 ..< 3:
+ var num = board[3*k + i][3*l + j]
+ if num in used:
+ return false
+ if num != 0:
+ used.add(num)
+ return true
+
+assert input.valid_boxes()
+
+func valid(board: Board): bool =
+ return board.valid_input() and board.valid_boxes() and
+ board.valid_rows() and board.valid_columns()
+
+assert input.valid()
+
+proc print(board: Board) =
+ for j in 0 ..< 9:
+ for i in 0 ..< 9:
+ stdout.write(board[j][i])
+ stdout.write(" ")
+ if i == 2 or i == 5:
+ stdout.write("| ")
+ stdout.write("\n")
+ if j == 2 or j == 5:
+ stdout.write("---------------------")
+ stdout.write("\n")
+ stdout.write("\n\n")
+
+proc generate_boards(board: Board) =
+ var board = board
+ for j in 0 ..< 9:
+ for i in 0 ..< 9:
+ if board[i][j] == 0:
+ for k in 1 .. 9:
+ board[i][j] = k
+ if board.valid():
+ generate_boards(board)
+ if board.valid():
+ board.print()
+ quit()
+
+generate_boards(input)