close
module Queen
class Struct
. 建立 row col 及 判斷 衝
class Queen < Struct
. 建立 單向 LINK 及 尋找 col 不衝突的位罩 ，如果找不到 last 移動 到不衝突的位置後 再重新尋找
. tail nextans() 可以找下一個答案 直到 第一個 QUEEN 沒有位置 共有 92
class Queen1 < Queen
. 增加雙向連結 且 自動 建立 N Queen1 直到 MAX
. nextans() 可以位移 最後 一個 QUEEN 找下一個解 ，共92解
1
# struct.rb
2
module Queen
3
class Struct
4
attr_reader :row,:col
5
def initialize(r,c)
6
@row=r
7
@col=c
8
end
9
def corss(q)
10
(row - q.row).abs == (col - q.col).abs
11
end
12
def attack(q) # 檢查衝突
13
row == q.row || col == q.col || corss(q)
14
end
15
def next # 移下一位置
16
@col= col.next
17
end
18
def to_s
19
"row: #{row} col:#{col}"
20
end
21
end
22
end
23
# 獨立測試
24
if __FILE__ == $0
25
require 'test/unit'
26
include Test::Unit::Assertions
27
q=->(r,c) { Queen::Struct.new(r,c) }
28
qatt= ->( r1,c1,r2,c2 ) { q.(r1,c1).attack( q.(r2,c2) ) }
29
puts "test start ==================="
30
assert( qatt.(1,1,2,2) == true ,"attack fail " )
31
assert( qatt.(4,4,6,2) == true ,"attack fail " )
32
assert( qatt.(1,1,2,3) == false ," not attach " )
33
assert( qatt.(2,2,4,3) == false ," not attach " )
34
puts "test to_s format #{q.(1,-1)} "
35
36
puts "finish test ======================= "
37
end
38
x
1
# queen.rb
2
require_relative '../queen'
3
require_relative 'struct'
4
class NoPos < RuntimeError ; end #col全走完 沒有搔到找到位置
5
module Queen
6
class Queen < Struct
7
@@max=4
8
class << self # 設定 Queen 最大數量
9
def max()
10
@@max
11
end
12
def max=(max)
13
@@max=max
14
end
15
end
16
17
def initialize(last=nil,row=1,col=1)
18
@last=last
19
super row,col
20
self.next if check() # 有衝突 位移直到無衝突 或 無位置
21
end
22
def max()
23
@@max
24
end
25
def printout()
26
puts self
27
@last.printout() if type_of_self?(@last)
28
end
29
30
def nextans() # 再次找下一解
31
self.next()
32
end
33
34
def to_a
35
return @last.to_a + [[@row,@col]]
36
end
37
protected
38
def next() # 有衝突 位移直到無衝突 或 無位置
39
40
raise NoPos if @col >= max() #
41
super # Queen::Struct next() @col+=1
42
self.next if check()
43
rescue NoPos
44
if type_of_self?(@last) # @
45
# last Queen move to next suitable pos and reset pos and recheck
46
@last.next()
47
@col=1 # reset col and recheck
48
self.next if check()
49
else
50
# havn't solv when first Queen NoPos
51
puts "--#{self}----- no answer ----------"
52
raise RuntimeError
53
end
54
end
55
def type_of_self?(obj)
56
obj.is_a? self.class
57
end
58
59
def check()
60
return false unless type_of_self?(@last) # first Queen do not check
61
@last.chk_attack(self) #
62
end
63
def chk_attack(q) # for @last
64
65
return true if attack(q)
66
return false unless type_of_self?( @last)
67
return @last.chk_attack(q)
68
end
69
70
end
71
end
72
if __FILE__ == $0
73
MAX=8
74
Queen::Queen.max=MAX
75
begin
76
i=0
77
a=Queen::Queen.new(nil,i+=1)
78
b=Queen::Queen.new(a,i+=1)
79
#;puts "-----------"; b.printout
80
c=Queen::Queen.new(b,i+=1)
81
#;puts "-----------"; c.printout
82
d=Queen::Queen.new(c,i+=1)
83
#;puts "-----------"; d.printout
84
e=Queen::Queen.new(d,i+=1)
85
#;puts "-----------"; e.printout
86
f=Queen::Queen.new(e,i+=1)
87
#;puts "-----------"; f.printout
88
g=Queen::Queen.new(f,i+=1)
89
#;puts "-----------"; g.printout
90
h=Queen::Queen.new(g,i+=1)
91
#;puts "-----------"; h.printout
92
# find all solv
93
puts "solv 1: #{h.to_a}"
94
(2..).each {|i| h.nextans ; puts "solv #{i} #{h.to_a}"}
95
rescue RuntimeError
96
puts " finish find"
97
end
98
99
begin
100
puts " ---------------------------- Array ---------------"
101
last=nil
102
#ar=(1..MAX).reduce([]){|ar,i| ar.push( last =Queen::Queen.new(last,i) ) }
103
ar=(1..MAX).map{|i| last =Queen::Queen.new(last,i) }
104
# find all solv
105
puts "solv 1: #{ar[-1].to_a}"
106
(2..).each { |i| ar[-1].nextans ; puts "solv #{i}: #{ar[-1].to_a}"}
107
rescue RuntimeError
108
puts " finish find"
109
end
110
111
end
112
113
xxxxxxxxxx
1
#queen1.rb
2
3
require_relative 'queen'
4
module Queen
5
class Queen1 < Queen
6
def initialize(last=nil,row=1,col=1)
7
super(last,row,col)
8
@next=self.class.new(self,@row.next) if @row < max()
9
end
10
def nextans()
11
tail.next()
12
end
13
14
def tail()
15
#return self unless @next.is_a? self.class
16
#return @next.tail
17
return type_of_self?(@next) ? @next.tail : self
18
end
19
def printout1()
20
# head line
21
puts (1..max).reduce(" :") {|str,i| str += " #{i}" } unless type_of_self?(@last)
22
#
23
puts "#{row}:" + " " * (@col-1) + " Q"
24
@next.printout1() if @row < max()
25
end
26
def to_a
27
return [[@row,@col]] + @next.to_a
28
end
29
protected :tail
30
end
31
end
32
if __FILE__ == $0
33
MAX=8
34
Queen::Queen1.max=MAX
35
a1=Queen::Queen1.new(nil,1,1)
36
a1.printout1
37
begin
38
puts " 1: #{a1.to_a}"
39
(2..).each {|i|
40
a1.nextans()
41
puts " #{i}: #{a1.to_a}"
42
}
43
rescue RuntimeError
44
puts "finish --------------------"
45
end
46
47
end
48
文章標籤
全站熱搜
留言列表
nodemcu (0)
