forked from seven1m/30-days-of-elixir
-
Notifications
You must be signed in to change notification settings - Fork 1
/
11-sudoku-solver.exs
167 lines (131 loc) · 4.6 KB
/
11-sudoku-solver.exs
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
157
158
159
160
161
162
163
164
165
166
167
Code.load_file("./10-sudoku-board.exs")
defmodule SudokuSolver do
@moduledoc """
Brute force solve a Sudoku puzzle.
TODO this is not a feasible approach for a 9x9 board since it generates too many combinations.
I will be working on a better solution soon.
This module does not concern itself with input/output -- it's up to you to feed
it a list of lists that represents the board, where `nil` is used to indicate a blank.
Here is a very small board to be solved:
iex> board = [[1, nil, 3 ],
[3, nil, 2 ],
[nil, 3, nil]]
The solve/1 method accepts the board and returns it solved:
iex> SudokuSolver.solve(board)
[[1, 2, 3],
[3, 1, 2],
[2, 3, 1]]
The way it works is by first determining possible solutions. Each solution is determined
by first building a list of non-used numbers for each row, e.g. in the sample board
above, the missing number in the first row is 2, second row is 1, and third row is 1 and 2.
Then, these "possibles" are combined to find possible solutions. For the sample board above,
possible solutions are: [2, 1, 1, 2] and [2, 1, 2, 1].
From there, we simply brute force check each solution against the board to see if it's solved.
In effect, we are using logic to find possible solutions that work for each *row*, then we
use brute force to check the solutions against each *column*.
"""
import Enum
@doc """
Given a list of lists (a square) containing some numbers (which represents a Sudoku board),
and containing nils where blanks are, return a square with all numbers filled in.
## Example
iex> board = [[1, nil, 3 ],
[3, nil, 2 ],
[nil, 3, nil]]
iex> SudokuSolver.solve(board)
[[1, 2, 3],
[3, 1, 2],
[2, 3, 1]]
"""
def solve(board) do
board
|> solutions
|> map(fn s -> apply_solution(board, s) end)
|> find(fn b -> SudokuBoard.solved?(b) end)
end
@doc """
Given a board and a solution, insert the values from the solution
into the nil spots in the board.
TODO I'm not happy with how this method turned out.
It seems inefficient to flatten and reconstitute the board on each iteration.
## Example
iex> board = [[1, nil],
[nil, 1 ]]
iex> SudokuSolver.apply_solution(board, [2, 2])
[[1, 2], [2, 1]]
"""
def apply_solution(board, [first | rest]) do
size = count(board)
board = List.flatten(board)
pos = find_index board, fn col -> col == nil end
List.replace_at(board, pos, first)
|> chunk(size)
|> apply_solution(rest)
end
def apply_solution(board, []), do: board
@doc """
Returns possible combinations for solving the board.
## Example
iex> board = [[1, nil, 3 ],
[3, nil, 2 ],
[nil, 3, nil]]
iex> SudokuSolver.solutions(board)
[[2, 1, 1, 2], [2, 1, 2, 1]]
"""
def solutions(board) do
possibles(board) |> combinations
end
defp possibles([row | rest]) do
possible = to_list(1..count(row)) -- row
[possible | possibles(rest)]
end
defp possibles([]), do: []
@doc """
Given a list of possibilities for each row, return all possible combinations.
## Example
iex> SudokuSolver.combinations([[1], [2], [3, 4]])
[[1, 2, 3, 4], [1, 2, 4, 3]]
"""
def combinations([list | rest]) do
crest = combinations(rest)
for p <- permutations(list), r <- crest do
List.flatten([p | r])
end
end
def combinations([]), do: [[]]
@doc """
Return all possible permuations of a list.
## Example
iex> SudokuSolver.permutations([1,2,3])
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
"""
# http://whileonefork.blogspot.com/2010/11/erlang-so-awesome-it-makes-my-brain.html
def permutations([]), do: [[]]
def permutations(list) do
for h <- list, t <- permutations(list -- [h]), do: [h | t]
end
end
ExUnit.start
defmodule SudokuSolverTest do
use ExUnit.Case
import SudokuSolver
test "correct behavior of combinations" do
assert combinations([[1]]) == [[1]]
assert combinations([[2, 3], [1]]) == [[2, 3, 1], [3, 2, 1]]
assert combinations([[1], [2], [3, 4]]) == [[1, 2, 3, 4], [1, 2, 4, 3]]
end
test "solves a small board" do
board = [[1, nil, 3 ],
[3, nil, 2 ],
[nil, 3, nil]]
assert solve(board) == [[1, 2, 3],
[3, 1, 2],
[2, 3, 1]]
end
test "returns nil on unsolvable board" do
board = [[1, nil, 3 ],
[3, nil, 2 ],
[nil, 2, nil]]
assert solve(board) == nil
end
end