1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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)
|
