-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sudoku.jl
156 lines (132 loc) · 4.48 KB
/
Sudoku.jl
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
module Sudoku
export createNormalSudokuMap, createSudoku, solveSudokuHeuristic
# create the colormap for a traditional sudoku, where a 9*9 board is split into 9 3*3 areas of the same colour
function createNormalSudokuMap()
out = zeros(Int8,9,9)
inc = [1 1 1 2 2 2 3 3 3]
for i in [1,4,7]
big = [inc;inc;inc]
inc = inc .+ 3
out[i:i+2,:] = big
end
return out
end
#=
sudoku -> the sudoku grid, can have some numbers already filled
sudoku_map -> the colormap for the sudoku, a color cannot have two numbers with the same value
number -> the number we are trying to insert
cartesian -> (i,j) touple, where i is the row index and j is the column index
=#
function checkForAvailability(sudoku, sudoku_map, number, cartesian::CartesianIndex{2})
function checkRowAva(number, row)
if number in row
return false
end
return true
end
row_available = checkRowAva(number,sudoku[cartesian[1],:])
column_available = checkRowAva(number,sudoku[:,cartesian[2]])
colour = sudoku_map[cartesian]
result = map(x -> x == number, sudoku)
colors = map(x -> x == colour, sudoku_map)
ultraRes = result .* colors
if (row_available && column_available && !(true in ultraRes))
return true
end
return false
end
# creates a new sudoku based on the sudoku_map, with "filled" fields filled, (filled is a number, that many fields remain filled)
function createSudoku(sudoku_map,filled = 17)
sudoku = zeros(Int8,size(sudoku_map))
sudoku_heuristic = createHeuristicRandom(sudoku_map)
sudoku = solveSudokuHeuristic(sudoku,sudoku_map,sudoku_heuristic)[3]
to_leave = zeros(Int8,size(sudoku_map))
while filled >= 0
i = rand(1:maximum(size(sudoku)))
j = rand(1:maximum(size(sudoku)))
if to_leave[i,j] != 1
to_leave[i,j] = 1
filled = filled - 1
end
end
solution = copy(sudoku)
sudoku = sudoku .* to_leave
return (sudoku,solution)
end
function createHeuristicRandom(sudoku_map,filled = 16)
sudoku_heuristic = ones(Int8,size(sudoku_map))
while filled >= 0
i = rand(1:maximum(size(sudoku_map)))
j = rand(1:maximum(size(sudoku_map)))
if sudoku_heuristic[i,j] != 2
sudoku_heuristic[i,j] = 2
filled = filled - 1
end
end
return sudoku_heuristic
end
#=
sudoku -> the sudoku grid, can have some numbers already filled
sudoku_map -> the colormap for the sudoku, a color cannot have two numbers with the same value
sudoku_heuristic -> optional, which fields the sudoku solver prioritizes, if not provided all fields have an equal pripority, the solver will solve up to down, left to right
returns (solution_found, number of steps, sudoku)
solution_found -> boolean, weather a solution was found or not
number of steps -> number of different numbers tried to arrive to the returned sudoku
sudoku -> the sudoku the program had stored at the end
=#
function solveSudokuHeuristic(sudoku,sudoku_map,sudoku_heuristic = nothing)
function is_zero(x)
if x == 0
return 1
end
return 0
end
if sudoku_heuristic == nothing
sudoku_heuristic = map(is_zero,sudoku)
else
values = map(x -> x == 0,sudoku)
sudoku_heuristic = sudoku_heuristic .* values
end
start = findmax(sudoku_heuristic)[2]
return solveSudokuRek(sudoku,sudoku_map,sudoku_heuristic,start,Int64(0))
end
#=
helper function for function solveSudokuHeuristic
curr -> current field being filled, type CartesianIndex(i, j)
=#
function solveSudokuRek(sudoku,sudoku_map,sudoku_heuristic,curr,num_steps)
if num_steps < 0
@warn "overflow for number of steps, result will be inaccurate", num_steps
elseif num_steps > 1000000
error("exceded 1000000 steps", sudoku,sudoku_heuristic)
end
heuristic = sudoku_heuristic[curr]
for number in 1:maximum(size(sudoku))
num_steps += 1
if checkForAvailability(sudoku,sudoku_map,number,curr)
sudoku[curr] = number
sudoku_heuristic[curr] = 0
next = findmax(sudoku_heuristic)
# solved sudoku
if next[1] == 0
return (true,num_steps,sudoku)
end
solution = solveSudokuRek(sudoku,sudoku_map,sudoku_heuristic,next[2],num_steps)
# if we found a solution
if solution[1]
return solution
# if we didn't find a solution, change the number of steps to that of the subtree
else
num_steps = solution[2]
end
# cleanup if a solution was not found
sudoku_heuristic[curr] = heuristic
sudoku[curr] = 0
end
end
return (false,num_steps,sudoku)
end
end
#sudoku_map = createNormalSudokuMap()
#sudoku = createSudoku(sudoku_map)
#println(sudoku)