The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes contains the digits from 1 to 9. The puzzle setter provides a partially completed grid. – Wikipedia
1 require 'rubygems' 2 require 'gecoder' 3 require 'enumerator' 4 5 # Solves the sudoku problem: http://en.wikipedia.org/wiki/Soduko 6 7 # The sudoku we want to solve (0 represents that the square is empty). 8 sudoku = Matrix[ 9 [0,0,0, 2,0,5, 0,0,0], 10 [0,9,0, 0,0,0, 7,3,0], 11 [0,0,2, 0,0,9, 0,6,0], 12 13 [2,0,0, 0,0,0, 4,0,9], 14 [0,0,0, 0,7,0, 0,0,0], 15 [6,0,9, 0,0,0, 0,0,1], 16 17 [0,8,0, 4,0,0, 1,0,0], 18 [0,6,3, 0,0,0, 0,8,0], 19 [0,0,0, 6,0,8, 0,0,0]] 20 21 solution = Gecode.solve do 22 # Verify that the input is of a valid size. 23 n = sudoku.row_size 24 sub_matrix_size = Math.sqrt(n).round 25 unless sudoku.square? and sub_matrix_size**2 == n 26 raise ArgumentError, 'Incorrect value matrix size.' 27 end 28 sub_count = sub_matrix_size 29 30 # Create the squares and initialize them. 31 squares_is_an int_var_matrix(n, n, 1..n) 32 sudoku.row_size.times do |i| 33 sudoku.column_size.times do |j| 34 squares[i,j].must == sudoku[i,j] unless sudoku[i,j] == 0 35 end 36 end 37 38 # Constraints. 39 n.times do |i| 40 # All rows must contain distinct numbers. 41 squares.row(i).must_be.distinct(:strength => :domain) 42 # All columns must contain distinct numbers. 43 squares.column(i).must_be.distinct(:strength => :domain) 44 # All sub-matrices must contain distinct numbers. 45 squares.minor( 46 (i % sub_count) * sub_matrix_size, 47 sub_matrix_size, 48 (i / sub_count) * sub_matrix_size, 49 sub_matrix_size).must_be.distinct(:strength => :domain) 50 end 51 52 # Branching, we use first-fail heuristic. 53 branch_on squares, :variable => :smallest_size, :value => :min 54 end.squares.values 55 56 # Output the solved sudoku in a grid. 57 puts solution.enum_slice(sudoku.row_size).map{ |slice| slice.join(' ') }.join($/)
3 7 8 2 6 5 9 1 4 5 9 6 8 1 4 7 3 2 1 4 2 7 3 9 5 6 8 2 1 7 3 8 6 4 5 9 8 5 4 9 7 1 6 2 3 6 3 9 5 4 2 8 7 1 7 8 5 4 2 3 1 9 6 4 6 3 1 9 7 2 8 5 9 2 1 6 5 8 3 4 7