Skip to content

Instantly share code, notes, and snippets.

# jonelf/gist:914326 Created Apr 11, 2011

Sudoku solver refactored from Luddite Geek and based on the Python solution by Peter Norvig.
 #!usr/bin/env ruby # 2011-04-11 jonelf@gmail.com # Sudoku solver refactored from Luddite Geek http://theludditegeek.com/blog/?page_id=92 # and that in turn is a translation from the Python solution by Peter Norvig # http://norvig.com/sudoku.html ## Throughout this program we have: ## r is a row, e.g. 'A' ## c is a column, e.g. '3' ## s is a square, e.g. 'A3' ## d is a digit, e.g. '9' ## u is a unit, e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1'] ## grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7... ## values is a dict/hash of possible values, e.g. {'A1':'12349', 'A2':'8', ...} ROWS = ('A'..'I') COLS = ('1'..'9') DIGITS = "123456789" def cross(rows,cols) cols.map {|x| rows.map {|y| y + x }}.flatten end @squares = cross(ROWS, COLS) # total of 81 squares # rowset(9) + colset (9) + subgrids (9) - 27 total nine_squares = ROWS.each_slice(3).map {|r| COLS.each_slice(3).map{|c| cross(r,c)}}.flatten(1) @unitlist = COLS.map{|c| cross(ROWS,[c])} << ROWS.map{|r| cross([r], COLS)} << nine_squares @units = @squares.inject({}) {|h, s| h[s]=@unitlist.select{|arr| arr.include?(s)};h} # All on the same row, same column and same 1/9 unit except the square itself @peers = @squares.inject({}) {|h,s| peers=(cross(ROWS,[s]) << cross([s],COLS) << nine_squares.select{|sq| sq.include?(s)} ). flatten; peers.delete(s); h[s]=peers; h} def grid_values(grid) # Convert grid into a dict of {square: char} with '0' or '.' for empties. @squares.zip(grid.each_char.grep(/[0-9\.]/)) end ################ Constraint Propagation ################ def assign(values, s, d) # eliminate all other values (except d) from values[s] and propogate # return updated values, unless a contradiction is detected (then return false) other_values = values[s].sub(d,'') other_values.each_char do |d2| return false unless eliminate(values, s, d2) end values end def eliminate(values, s, d) # Eliminate digit from values list; propogate when # of values/places reduced to <= 2 # Return false if contradiction is detected; else return values return values unless values[s].include?(d) ## Already eliminated values[s] = values[s].sub(d,'') ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers. if values[s].size== 0 return false ## Contradiction: removed last value elsif values[s].size == 1 d2 = values[s] @peers[s].each do |s2| return false unless (eliminate(values, s2, d2)) end end ## (2) If a unit u is reduced to only one place for a value d, then put it there. sa = [s] @units[s].each do |u| dplaces = values[s].include?(d) ? sa & u : [] ## Contradiction: no place for this value return values if dplaces.size == 0 if dplaces.size == 1 return false unless assign(values, dplaces, d) end end values end # def ################ Display Results as 2-D grid ################ def display(values) #"Display these values as a 2-D grid." #width = 2 since the "DG" and "36" are hardcoded anyway. width = 2 #1 + values.max_by {|a| a.size}.size puts line = [['-'*width*3]*3].join('+') # 81 square grid ROWS.each do |r| puts line if "DG".include?(r) # 3x3 grid COLS.each do |c| print values["#{r}#{c}"].center(width) print '|' if '36'.include?(c) end puts end puts line end ################ Utilities ################ def get_min(d) # Find best candidate to process next (i.e. entry w least # of possible values) = steps are: # 1) filter list - only select those with length > 1 (otherwise it's a solved square) # 2) return key, value and length of shortest entry min = d.select{|k,v| v.length>1}. min_by{|h| h.length} return min, min, min.length end ################ Parse a Grid ################ def parse_grid (grid) # Convert grid to a list of possible values and parses grid into a values dictionary # the values hash/dict contains a text string of possible values for each cell # if cell is completed then the string is 1 char long with the correct/solved value # the grid is an array containing the initial/current?? value(s) defined in the puzzle values = {} # define values dictionary @squares.each do |s| values[s] = DIGITS end grid_values(grid).each do |zg| # extract cell names and values from zip grid array s, d = zg if DIGITS.include?(d) return false unless assign(values, s, d) end end values end # parse_grid ################ Search Grid Values ################ def search(values) # Depth first search and propagation return false unless values ## Failed earlier return values unless @squares.any?{|s| values[s].size != 1} # For harder puzzles there is some more work to do # Find the unfilled square s with the fewest possibilities # and continue the search/elimination process k,v,l = get_min(values) v.each_char do |d| r = search(assign(values.clone, k, d)) return r if r end return false end # search def require 'benchmark' puts ">>>> Start <<<<" # define set of test games puzzles = %w{ 003020600900305001001806400008102900700000008006708200002609500800203009005010300 4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... 1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3.. 500000009020100070008000300040600000000050000000207010003000800060004020900000005 600302000040000080000000000702600000000000054300000000080150000000080200000000700 } # .....6....59.....82....8....45........3........6..3.54...325..6.................. Benchmark.bm do |benchmark| puzzles.each do |puzzle| benchmark.report do puts "Puzzle: #{puzzle}" puts "Solution:" display(search(parse_grid(puzzle))) end puts end end puts ">>> Done <<<"
Owner Author

### jonelf commented Apr 11, 2011

 Test run at http://ideone.com/46grY but be aware that the last puzzle times out. It finishes in 8s on my machine, all the others finishes in a couple hundreds of a second.

### attractivechaos commented Jun 17, 2011

 Thanks for the example. Nonetheless, I think solving any puzzle in 8s does not sound right. Peter Norvig's python version solves that in 0.05 second. Another Ruby reimplementation solves the puzzle in a similar amount of time. Here is a Javascript implementation. You may test the speed.
Owner Author

### jonelf commented Jun 17, 2011

 Peter Norvig's python version solves that in 0.05 second. Nice but kind of strange that at http://norvig.com/sudoku.html it says 188.79 seconds.
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.