Sudoku solver

You are given a 9x9 grid of numbers:

1
27 9 5
8 5 3
8 3 2
5 1 2 9
1 5 7
5 6 3
9 1 62
2

Your task is to fill in the grid in such a way that

  • Each row uses each of the numbers 1,2,...,9 exactly once
  • Each column uses each of the numbers 1,2,...,9 exactly once
  • Each smaller 3x3 square with a thick border uses each of the numbers 1,2,...,9 exactly once

Problem data

In [25]:
# Given data. Unknown entries are specified as "0"
given = [
  0 0 0  0 0 1  0 0 0
  2 7 0  0 9 0  5 0 0
  0 8 0  0 0 5  0 0 3

  0 0 8  0 3 0  0 2 0
  0 5 0  1 0 2  0 9 0
  0 1 0  0 5 0  7 0 0

  5 0 0  6 0 0  0 3 0
  0 0 9  0 1 0  0 6 2
  0 0 0  2 0 0  0 0 0
];
In [26]:
# helper function to print a sudoku grid
function printSudoku(arr)
  u = 0
  println("+-------+-------+-------+")
  for p in 1:3:9
    for q in 0:2
      print("| ")
      for r in 1:3:9
        for s in 0:2
          u = round(Int, arr[p+q,r+s])
          u == 0 ? print(" ") : print(u)
          print(" ")
        end
        print("| ")
      end
      println()
    end
    println("+-------+-------+-------+")
  end
end
;
In [28]:
using JuMP, Cbc

m = Model(solver = CbcSolver())

@variable(m, x[1:9,1:9,1:9], Bin)

# exactly one number per cell
for i in 1:9
  for j in 1:9
    @constraint(m, sum(x[i,j,k] for k in 1:9) == 1)
  end
end

# exactly one of each number per row
for i in 1:9
  for k in 1:9
    @constraint(m, sum(x[i,j,k] for j in 1:9) == 1)
  end
end

# exactly one of each number per column
for j in 1:9
  for k in 1:9
    @constraint(m, sum(x[i,j,k] for i in 1:9) == 1)
  end
end

# exactly one of each number per 3x3 block
for k in 1:9
  for p in 0:3:6
    for q in 0:3:6
      @constraint(m, sum(x[p+i,q+j,k] for i in 1:3, j in 1:3) == 1)
    end
  end
end

# initial conditions
for i in 1:9
  for j in 1:9
    if given[i,j] != 0
      @constraint(m, x[i,j,given[i,j]] == 1)
    end
  end
end

@time(status = solve(m))

if status != :Optimal
    println(status)
else
    # generate solution grid and display the solution
    solution = zeros(9,9)
    for i in 1:9
      for j in 1:9
        for k in 1:9
          if getvalue(x[i,j,k]) == 1
            solution[i,j] = k
            continue
          end
        end
      end
    end

    println("The given problem is: ")
    printSudoku(given)

    println("The solution is: ")
    printSudoku(solution)
end
  0.008579 seconds (91 allocations: 291.578 KiB)
The given problem is: 
+-------+-------+-------+
|       |     1 |       | 
| 2 7   |   9   | 5     | 
|   8   |     5 |     3 | 
+-------+-------+-------+
|     8 |   3   |   2   | 
|   5   | 1   2 |   9   | 
|   1   |   5   | 7     | 
+-------+-------+-------+
| 5     | 6     |   3   | 
|     9 |   1   |   6 2 | 
|       | 2     |       | 
+-------+-------+-------+
The solution is: 
+-------+-------+-------+
| 4 6 5 | 3 7 1 | 2 8 9 | 
| 2 7 3 | 8 9 6 | 5 1 4 | 
| 9 8 1 | 4 2 5 | 6 7 3 | 
+-------+-------+-------+
| 6 9 8 | 7 3 4 | 1 2 5 | 
| 7 5 4 | 1 6 2 | 3 9 8 | 
| 3 1 2 | 9 5 8 | 7 4 6 | 
+-------+-------+-------+
| 5 2 7 | 6 4 9 | 8 3 1 | 
| 8 3 9 | 5 1 7 | 4 6 2 | 
| 1 4 6 | 2 8 3 | 9 5 7 | 
+-------+-------+-------+
In [ ]: