Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
245 lines (214 sloc) 7.456 kb
defmodule SudokuSolver do
@moduledoc """
Solves 9x9 Sudoku puzzles, Peter Norvig style.
http://norvig.com/sudoku.html
"""
@size 9
@rows 'ABCDEFGHI'
@cols '123456789'
import Enum
# used to cache all squares, units, and peer relationships
defmodule Board do
defstruct squares: nil, units: nil, peers: nil
end
def cross(list_a, list_b) do
for a <- list_a, b <- list_b, do: [a] ++ [b]
end
@doc "Return all squares"
def squares, do: cross(@rows, @cols)
@doc """
All squares divided by row, column, and box.
"""
def unit_list do
(for c <- @cols, do: cross(@rows, [c])) ++
(for r <- @rows, do: cross([r], @cols)) ++
(for rs <- chunk(@rows, 3), cs <- chunk(@cols, 3), do: cross(rs, cs))
end
@doc """
All squares from unit_list, organized in a Dict with each square as key.
iex> Dict.get(SudokuSolver.units, 'C2')
[['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
"""
def units do
ul = unit_list
list = for s <- squares, do: {s, (for u <- ul, s in u, do: u)}
Enum.into(list, HashDict.new)
end
@doc """
Like units/0 above, returning a Dict, but not including the key itself.
iex> Dict.get(SudokuSolver.peers, 'C2')
HashSet.new(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
'A1', 'A3', 'B1', 'B3'])
"""
def peers do
squares = cross(@rows, @cols)
u = units
list = for s <- squares do
all = u |> Dict.get(s) |> concat |> Enum.into(HashSet.new)
me = [s] |> Enum.into(HashSet.new)
{s, HashSet.difference(all, me)}
end
Enum.into(list, HashDict.new)
end
@doc """
Convert grid to a Dict of possible values, {square: digits}, or
return false if a contradiction is detected.
"""
def parse_grid(grid, board) do
# To start, every square can be any digit; then assign values from the grid.
values = Enum.into((for s <- board.squares, do: {s, @cols}), HashDict.new)
do_parse_grid(values, Dict.to_list(grid_values(grid)), board)
end
defp do_parse_grid(values, [{square, value} | rest], board) do
values = do_parse_grid(values, rest, board)
if value in '0.' do
values
else
assign(values, square, value, board)
end
end
defp do_parse_grid(values, [], _), do: values
@doc """
Convert grid into a Dict of {square: char} with '0' or '.' for empties.
"""
def grid_values(grid) do
chars = for c <- grid, c in @cols or c in '0.', do: c
unless count(chars) == 81, do: raise('error')
Enum.into(zip(squares, chars), HashDict.new)
end
@doc """
Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return false if a contradiction is detected.
"""
def assign(values, s, d, board) do
values = Dict.put(values, s, [d])
p = Dict.to_list(Dict.get(board.peers, s))
eliminate(values, p, [d], board)
end
@doc """
Eliminate values from given squares and propagate.
"""
def eliminate(values, squares, vals_to_remove, board) do
reduce_if_truthy squares, values, fn square, values ->
eliminate_vals_from_square(values, square, vals_to_remove, board)
end
end
# Remove value(s) from a square, then:
# (1) If a square s is reduced to one value, then eliminate it from the peers.
# (2) If a unit u is reduced to only one place for a value d, then put it there.
defp eliminate_vals_from_square(values, square, vals_to_remove, board) do
vals = Dict.get(values, square)
if Set.intersection(Enum.into(vals, HashSet.new), Enum.into(vals_to_remove, HashSet.new)) |> any? do
vals = reduce vals_to_remove, vals, fn val, vals -> List.delete(vals, val) end
if length(vals) == 0 do
# contradiction, removed last value
false
else
values = Dict.put(values, square, vals)
values = if length(vals) == 1 do
# eliminate value(s) from the peers.
eliminate(values, Dict.to_list(Dict.get(board.peers, square)), vals, board)
else
values
end
# eliminate value(s) from units
eliminate_from_units(values, Dict.get(board.units, square), vals_to_remove, board)
end
else
values
end
end
# If a unit u is reduced to only one place for a value d, then put it there.
defp eliminate_from_units(values, units, vals_to_remove, board) do
reduce_if_truthy units, values, fn unit, values ->
reduce_if_truthy vals_to_remove, values, fn val, values ->
dplaces = for s <- unit, val in Dict.get(values, s), do: s
case length(dplaces) do
0 -> false # contradiction: no place for this value
1 -> assign(values, at(dplaces, 0), val, board) # d can only be in one place in unit; assign it there
_ -> values
end
end
end
end
# Similar to Enum.reduce/3 except it won't continue to call the work function
# if the accumulator becomes false or nil.
defp reduce_if_truthy(coll, acc, fun) do
reduce coll, acc, fn i, a ->
a && fun.(i, a)
end
end
@doc """
Given a puzzle char list, find the solution and return as a char list.
Use display/1 to print the grid as a square.
"""
def solve(grid) do
board = %Board{squares: squares, units: units, peers: peers}
grid
|> parse_grid(board)
|> search(board)
|> flatten(board)
end
@doc """
Flatten a values Dict back into a single char list.
"""
def flatten(values, board) do
board.squares
|> map(fn s -> Dict.get(values, s) end)
|> concat
end
@doc """
Using depth-first search and propagation, try all possible values.
"""
def search(false, _), do: false
def search(values, board) do
if all?(board.squares, fn s -> count(Dict.get(values, s)) == 1 end) do
values # solved!
else
# Chose the unfilled square s with the fewest possibilities
{square, _count} = map(board.squares, &({&1, count(Dict.get(values, &1))}))
|> filter(fn {_, c} -> c > 1 end)
|> sort(fn {_, c1}, {_, c2} -> c1 < c2 end)
|> List.first
find_value Dict.get(values, square), fn d ->
assign(values, square, d, board) |> search(board)
end
end
end
@doc """
Display these values as a 2-D grid.
"""
def display(grid) do
chunk(grid, @size)
|> map(fn row -> chunk(row, 1) |> join(" ") end)
|> join("\n")
|> IO.puts
end
end
ExUnit.start
defmodule SudokuSolverTest do
use ExUnit.Case
import SudokuSolver
def print(grid, solved) do
IO.puts "puzzle-----------"
display(grid)
IO.puts "solved-----------"
display(solved)
IO.puts "\n"
end
test "solve easy" do
grid1 = '..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..'
solved = solve(grid1)
assert solved == '483921657967345821251876493548132976729564138136798245372689514814253769695417382'
print(grid1, solved)
end
test "solve hard" do
grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
solved = solve(grid2)
assert solved == '417369825632158947958724316825437169791586432346912758289643571573291684164875293'
print(grid2, solved)
end
end
Jump to Line
Something went wrong with that request. Please try again.