Instantly share code, notes, and snippets.

# jonelf/gist:914326

Created April 11, 2011 20:57
Sudoku solver refactored from Luddite Geek and based on the Python solution by Peter Norvig.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!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 <<<"

### 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.

### 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.