Skip to content

Instantly share code, notes, and snippets.

@iamed2
Created May 17, 2015 17:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iamed2/25d997791d93657cec7f to your computer and use it in GitHub Desktop.
Save iamed2/25d997791d93657cec7f to your computer and use it in GitHub Desktop.
Sudoku solver written at !!con!
5 3 _ _ 7 _ _ _ _
6 _ _ 1 9 5 _ _ _
_ 9 8 _ _ _ _ 6 _
8 _ _ _ 6 _ _ _ 3
4 _ _ 8 _ 3 _ _ 1
7 _ _ _ 2 _ _ _ 6
_ 6 _ _ _ _ 2 8 _
_ _ _ 4 1 9 _ _ 5
_ _ _ _ 8 _ _ 7 9
module Sukano
using JuMP
function sudoku_setup()
m = Model()
@defVar(m, 0 <= board[1:9,1:9,1:9] <=1, Int)
# each square can only have one value
@addConstraint(m, squareconst[i=1:9,j=1:9], sum(board[i,j,:]) == 1)
@addConstraint(m, rowconst[i=1:9,j=1:9], sum(board[:,i,j]) == 1)
@addConstraint(m, colconst[i=1:9,j=1:9], sum(board[i,:,j]) == 1)
# boxes are hard!
@addConstraint(m, boxconst[baserow=1:3:7,basecol=1:3:7,i=1:9], sum(board[baserow:(baserow+2),basecol:(basecol+2),i]) == 1)
return m, board
end
function add_fixed_nums!(m, board, fixed_nums)
for ((i, j), k) in fixed_nums
@addConstraint(m, board[i,j,k] == 1)
end
end
function print_board(board)
for i = 1:9
for j = 1:9
for k = 1:9
if round(Int, board[i,j,k]) != 0
print(' ', k)
end
end
if mod(j, 3) == 0
print(' ')
end
end
if mod(i, 3) == 0
println()
end
println()
end
end
function read_board(input_text)
fixed_nums = Dict{Tuple{Int,Int},Int}()
row = 1
for line in input_text
tokens = split(line)
if length(tokens) < 9
continue
end
for col = 1:9
try
fixed_nums[row, col] = parse(Int, tokens[col])
end
end
row += 1
if row > 9
break
end
end
return fixed_nums
end
function main()
fixed_nums = read_board(readlines(STDIN))
m, board = sudoku_setup()
add_fixed_nums!(m, board, fixed_nums)
status = solve(m)
if status == :Optimal
println("Hooray!!\n")
board_vals = getValue(board)
print_board(board_vals)
else
println("Keep trying, you'll get it!")
end
end
end
Sukano.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment