game.rb
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
def cross(cols, rows) cols.split('').product(rows.split('')).map{|c, r| c + r} end $digits = '123456789' $rows = 'ABCDEFGHI' $cols = $digits $squares = cross($rows, $cols) $unitlist = $cols.split('').map{|c| cross($rows, c)} + $rows.split('').map{|r| cross(r, $cols)} + ['ABC', 'DEF', 'GHI'].product(['123', '456', '789']).map{|c, r| cross(c, r)} $units = Hash[$squares.zip($squares.map{|s| $unitlist.select{|u| u.include?(s)}})] $peers = Hash[$squares.zip($squares.map{|s| $units[s].flatten.uniq - [s]})] def parse_grid(grid) values = Hash[$squares.zip($squares.map{$digits.dup})] grid_values(grid).each{|s, d| return false if $digits.include?(d) && !assign(values, s, d) } values end def grid_values(grid) chars = grid.split('').select{|c| $digits.include?(c) || '0.'.include?(c)} raise ArgumentError.new("can't convert grid into a Hash") if chars.size != 81 Hash[$squares.zip(chars)] end def assign(values, s, d) other_values = values[s].delete(d) if other_values.split('').all?{|d2| eliminate(values, s, d2)} values else false end end def eliminate(values, s, d) return values if !values[s].include?(d) values[s] = values[s].delete(d) case values[s].size when 0 return false when 1 d2 = values[s] return false if !$peers[s].all?{|s2| eliminate(values, s2, d2)} end $units[s].each{|u| dplaces = u.select{|s2| values[s2].include?(d)} case dplaces.size when 0 return false when 1 return false if !assign(values, dplaces[0], d) end } values end def display(values) width = 1 + $squares.map{|d| d.size}.max line = (['-' * (width * 3)] * 3).join('+') $rows.split('').each{|r| $cols.split('').each{|c| print values[r + c].center(width) print '|' if '36'.include?(c) print "\n" if c == '9' } puts line if 'CF'.include?(r) } puts end def solve(grid) search(parse_grid(grid)) end def search(values) return false if !values return values if $squares.all?{|s| values[s].size == 1} s, n = values.select{|s, d| d.size > 1}.min_by{|s, d| d.size} values[s].split('').map{|d| search(assign(values.dup, s, d))}.find{|v| v} end display(solve('003020600900305001001806400008102900700000008006708200002609500800203009005010300')) display(solve('4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......')) display(solve('005300000800000020070010500400005300010070006003200080060500009004000030000009700')) |
