Rubyで数独（ナンプレ）を解く（解決編）

4月 26th, 2008 admin Posted in Ruby, 今日のコード | 2 Comments »

※このコードでは解けない問題があることがわかったのでコードを書き直しました。
新しいコードはこちら「Rubyで数独（ナンプレ）を解く（本当の解決編）」

前回はそもそもナンプレを１度しかやったことがないこともあってルールを間違えており解けませんでした。
今回やっと解決編としてナンプレを解くコードを掲載します。

アルゴリズム

(1)全マスについて候補を求め、候補リスト（配列）を作成
（２）全マスについて、そのマスに関係するマスの候補リストから置ける数字を調べる
（３）（２）をマス数回行う < -このへんが頭悪い感じが出ているので改良候補

コード

PLAIN TEXT

RUBY:

1. class Numpla
2.     def initialize(sheet)
3.         @sheet = sheet
4.         @size = Math.sqrt(sheet.size).to_i
5.         @side_size = Math.sqrt(@size).to_i
6.         @possible = Array.new
7.     end
8.    
9.     def resolve
10.     81.times{
11.             (0...@sheet.length).each do |i|
12.                 if @sheet[i] == 0
13.                     @possible[i] = get_possibles(get_neighbors(i))
14.                 else
15.                     @possible[i] = []
16.                 end
17.             end
18.            
19.             (0...@sheet.length).each do |i|
20.                 if @possible[i].size> 0
21.                     if @possible[i].size == 1
22.                         @sheet[i] = @possible[i].pop
23.                     else
24.                         @sheet[i] = get_answer(i,get_neighbors(i))
25.                     end
26.                 end
27.             end
28.             }
29.             @sheet
30.     end
31.    
32.     def get_answer(index,neighbors)
33.         answer = @possible[index]
34.         possibles = Array.new
35.         neighbors.each do |i|
36.             possibles |= @possible[i]
37.         end
38.         possibles.each do |v|
39.             answer.delete(v)
40.         end
41.      result = (answer.size == 1) ? answer.pop : 0;
42.      return result
43.     end
44.    
45.     def get_neighbors(index)
46.         get_neighbors_h(index) | get_neighbors_v(index) | get_neighbors_b(index)
47.     end
48.    
49.     def get_neighbors_h(index)
50.         neighbors = Array.new
51.         horizone = index / @size * @size
52.         @size.times {|i|
53.             neighbors.push(i + horizone)
54.         }
55.         neighbors.delete(index)
56.         neighbors
57.     end
58.    
59.     def get_neighbors_v(index)
60.         neighbors = Array.new
61.         vertical = index % @size
62.         @size.times {|i|
63.             neighbors.push(@size * i + vertical);
64.         }
65.         neighbors.delete(index)
66.         neighbors
67.     end
68.  
69.  
70.     def get_neighbors_b(x)
71.           tf = x / @side_size * @side_size
72.           offset = tf / @size % @side_size
73.           fc = tf - @size * offset
74.  
75.           neighbors = Array.new
76.           (0..(@side_size-1)).each do |j|
77.             (fc+@size*j..fc+@size*j+(@side_size-1)).each do |i| neighbors.push(i) end
78.           end
79.  
80.           neighbors
81.     end
82.  
83.     def get_possibles(neighbors)
84.         possibles = Array.new
85.         (1..@size).each{|i| possibles.push i }
86.         neighbors.each do |i|
87.             possibles.delete(@sheet[i])
88.         end
89.        
90.         possibles
91.     end
92. end
93.  
94. sheet = Array.new
95. sheet.concat [3,7,0,6,2,0,0,0,1]
96. sheet.concat [0,0,8,0,5,0,0,6,9]
97. sheet.concat [4,0,0,0,7,0,0,8,0]
98. sheet.concat [0,6,0,0,0,4,0,3,8]
99. sheet.concat [8,0,0,0,3,0,0,0,6]
100. sheet.concat [5,2,0,0,8,6,0,9,0]
101. sheet.concat [0,4,0,0,1,0,0,0,3]
102. sheet.concat [9,3,0,0,6,0,8,0,0]
103. sheet.concat [6,0,0,0,4,2,0,7,5]
104. width = 9
105. height= 9
106.  
107.  
108. foo = Numpla.new(sheet)
109.  
110. result = foo.resolve
111.  
112. count = 1
113. result.each do |x|
114.   print x
115.   print ","
116.   print "\n" unless count % 9> 0
117.   count += 1
118. end

出力

まとめ

コードを書いていてとても楽しかった。仕事ではWebアプリを書くことが多いのですが、Webアプリではアルゴリズムを自分で考えるということがあまりないんだなというのを改めて思い知らされました。ショッピングサイトでない限り掛け算や割り算はおろか足し算引き算もしなかったりしますからね。

とりあえず問題を解けるようになったので、まずは他のナンプレの解法をみて比較したり改良してもっとRubyっぽくしてみたいと思います。