查看完整版本: 2008-04-24 Ruby 测试题(00014)

2008-04-24 Ruby 测试题(00014)

本周出差，没机会碰Ruby，所以晚了一点。
今天的题目依然是经典题，八皇后问题。
我们知道，在国际象棋里，皇后的攻击范围是最广的，可以攻击到同行，同列，同一对角线（主副）上的棋子。
那么，在一个8*8的棋盘上，是否可以摆放8个皇后，并使她们任意两者间都不能互相攻击到？如果可以，那么怎么摆放？
输出方式随意，只要能表达清楚即可。

等出差回去，好好写点有关回溯的东西。

[[i] 本帖最后由 jmouse 于 2008-4-24 15:28 编辑 [/i]]

:Q :L  看答案吧。

[code]$column = Array.new(9,1)
$rup = Array.new(17,1)
$lup = Array.new(17,1)
$queen=Array.new(9)
$num=0

def backtrack(i)
  if i > 8
    show_answer()
  else
    (1..8).each do |j|
      if $column[j]==1&&$rup[i+j]==1&&$lup[i-j+8]==1
        $queen[i] = j
        $column[j] = $rup[i+j] = $lup[i-j+8] = 0
        backtrack(i+1)
        $column[j] = $rup[i+j] = $lup[i-j+8] = 1
      end
    end
  end
end


def show_answer
  $num+=1
  puts "\n解答 #{$num}"
  (1..8).each do |i|
    (1..8).each do |j|
      print $queen[i]==j ? ' Q' : ' .'
    end
    puts ''
  end
end

backtrack(1)[/code]

[[i] 本帖最后由 feza 于 2008-4-25 19:29 编辑 [/i]]

对回溯有点头大，先来个暴力算法

**** Hidden Message *****

[1, 5, 8, 6, 3, 7, 2, 4]
[1, 6, 8, 3, 7, 4, 2, 5]
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[2, 4, 6, 8, 3, 1, 7, 5]
[2, 5, 7, 1, 3, 8, 6, 4]
[2, 5, 7, 4, 1, 8, 6, 3]
[2, 6, 1, 7, 4, 8, 3, 5]
[2, 6, 8, 3, 1, 4, 7, 5]
[2, 7, 3, 6, 8, 5, 1, 4]
[2, 7, 5, 8, 1, 4, 6, 3]
[2, 8, 6, 1, 3, 5, 7, 4]
[3, 1, 7, 5, 8, 2, 4, 6]
[3, 5, 2, 8, 1, 7, 4, 6]
[3, 5, 2, 8, 6, 4, 7, 1]
[3, 5, 7, 1, 4, 2, 8, 6]
[3, 5, 8, 4, 1, 7, 2, 6]
[3, 6, 2, 5, 8, 1, 7, 4]
[3, 6, 2, 7, 1, 4, 8, 5]
[3, 6, 2, 7, 5, 1, 8, 4]
[3, 6, 4, 1, 8, 5, 7, 2]
[3, 6, 4, 2, 8, 5, 7, 1]
[3, 6, 8, 1, 4, 7, 5, 2]
[3, 6, 8, 1, 5, 7, 2, 4]
[3, 6, 8, 2, 4, 1, 7, 5]
[3, 7, 2, 8, 5, 1, 4, 6]
[3, 7, 2, 8, 6, 4, 1, 5]
[3, 8, 4, 7, 1, 6, 2, 5]
[4, 1, 5, 8, 2, 7, 3, 6]
[4, 1, 5, 8, 6, 3, 7, 2]
[4, 2, 5, 8, 6, 1, 3, 7]
[4, 2, 7, 3, 6, 8, 1, 5]
[4, 2, 7, 3, 6, 8, 5, 1]
[4, 2, 7, 5, 1, 8, 6, 3]
[4, 2, 8, 5, 7, 1, 3, 6]
[4, 2, 8, 6, 1, 3, 5, 7]
[4, 6, 1, 5, 2, 8, 3, 7]
[4, 6, 8, 2, 7, 1, 3, 5]
[4, 6, 8, 3, 1, 7, 5, 2]
[4, 7, 1, 8, 5, 2, 6, 3]
[4, 7, 3, 8, 2, 5, 1, 6]
[4, 7, 5, 2, 6, 1, 3, 8]
[4, 7, 5, 3, 1, 6, 8, 2]
[4, 8, 1, 3, 6, 2, 7, 5]
[4, 8, 1, 5, 7, 2, 6, 3]
[4, 8, 5, 3, 1, 7, 2, 6]
[5, 1, 4, 6, 8, 2, 7, 3]
[5, 1, 8, 4, 2, 7, 3, 6]
[5, 1, 8, 6, 3, 7, 2, 4]
[5, 2, 4, 6, 8, 3, 1, 7]
[5, 2, 4, 7, 3, 8, 6, 1]
[5, 2, 6, 1, 7, 4, 8, 3]
[5, 2, 8, 1, 4, 7, 3, 6]
[5, 3, 1, 6, 8, 2, 4, 7]
[5, 3, 1, 7, 2, 8, 6, 4]
[5, 3, 8, 4, 7, 1, 6, 2]
[5, 7, 1, 3, 8, 6, 4, 2]
[5, 7, 1, 4, 2, 8, 6, 3]
[5, 7, 2, 4, 8, 1, 3, 6]
[5, 7, 2, 6, 3, 1, 4, 8]
[5, 7, 2, 6, 3, 1, 8, 4]
[5, 7, 4, 1, 3, 8, 6, 2]
[5, 8, 4, 1, 3, 6, 2, 7]
[5, 8, 4, 1, 7, 2, 6, 3]
[6, 1, 5, 2, 8, 3, 7, 4]
[6, 2, 7, 1, 3, 5, 8, 4]
[6, 2, 7, 1, 4, 8, 5, 3]
[6, 3, 1, 7, 5, 8, 2, 4]
[6, 3, 1, 8, 4, 2, 7, 5]
[6, 3, 1, 8, 5, 2, 4, 7]
[6, 3, 5, 7, 1, 4, 2, 8]
[6, 3, 5, 8, 1, 4, 2, 7]
[6, 3, 7, 2, 4, 8, 1, 5]
[6, 3, 7, 2, 8, 5, 1, 4]
[6, 3, 7, 4, 1, 8, 2, 5]
[6, 4, 1, 5, 8, 2, 7, 3]
[6, 4, 2, 8, 5, 7, 1, 3]
[6, 4, 7, 1, 3, 5, 2, 8]
[6, 4, 7, 1, 8, 2, 5, 3]
[6, 8, 2, 4, 1, 7, 5, 3]
[7, 1, 3, 8, 6, 4, 2, 5]
[7, 2, 4, 1, 8, 5, 3, 6]
[7, 2, 6, 3, 1, 4, 8, 5]
[7, 3, 1, 6, 8, 5, 2, 4]
[7, 3, 8, 2, 5, 1, 6, 4]
[7, 4, 2, 5, 8, 1, 3, 6]
[7, 4, 2, 8, 6, 1, 3, 5]
[7, 5, 3, 1, 6, 8, 2, 4]
[8, 2, 4, 1, 7, 5, 3, 6]
[8, 2, 5, 3, 1, 7, 4, 6]
[8, 3, 1, 6, 2, 5, 7, 4]
[8, 4, 1, 3, 6, 2, 7, 5]

回复 2# 的帖子

就是92种解。。老师一个月前刚讲完。。。。
（旋转、翻转不算一种解的话）

哈哈，我就是那个跟老师唱反调的人，可通过旋转，翻转成为同一局面的都只能算一个解。
当然，这个是附加题了。

速度很慢，欢迎指导！

:lol[code]class Bahh
  def initialize
    @chart = [
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'],
      ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x']
    ]
    @row = Array.new()
    @col = Array.new()
    @left = Array.new()
    @right = Array.new()
  end

  def sitDown(n, sPos)
    return if n > 8
    for pos in sPos .. 63
      if try?(pos)
        make(pos)
        paint if n == 8
        sitDown(n + 1, pos + 1)
        unmake(pos)
      end
    end
  end

private
  def try?(pos)
    x, y = pos / 8, pos % 8
    !(@row[x] == 1 || @col[y] == 1 || @left[x + y] == 1 || @right[x - y + 7] == 1)
  end

  def make(pos, flag = 1)
    x, y = pos / 8, pos % 8
    @row[x] = flag
    @col[y] = flag
    @left[x + y] = flag
    @right[x - y + 7] = flag
    @chart[x][y] = 'Q' if flag == 1
    @chart[x][y] = 'x' if flag == 0
  end
   
  def unmake(pos)
    make(pos, 0)
  end
  
  def paint
    8.times do |x|
      8.times {|y| print @chart[x][y], " "}
      print "\n"
    end
    print "----------------------------\n"
  end
end

Bahh.new.sitDown(1, 0)[/code]#感觉太慢了，哪位能对题目做一下分析吗？

[[i] 本帖最后由 jmouse 于 2008-4-28 15:01 编辑 [/i]]

先贴上回溯解法[code]def EightQueen(n)
  $m = []
  0.upto(n){$m<<0}#准备棋盘，因为每行只能放一个，所以用一维数组就可以了。下标是行，值是列。
  k = 1#初始行
  while true
    $m[k]+=1#当前行列数加一，即探索当前步骤下一选择。
    if $m[k]==n+1#若已无选择
      $m[k]=0#当前步骤现场还原
      k-=1#退步。
      if k==0#若退到头，则结束
        break
      end
    else
      if check(k)#检验当前探索是否可行，若不可行，循环继续采用下一探索
        k+=1#可行，前进一步
        if k==n+1#若前进至最终，则出解
          puts $m[1..n].join(",")
          k-=1#此处用break代替则是求得一个解的出口，用退一步则是为了找到所有解
        end
      end
    end
  end
end
def check(k)
  for i in (1..k-1)
    return false if $m[i] == $m[k]#检验列
    return false if ($m[i]+i)==($m[k]+k)#检验主对角线
    return false if ($m[i]-i)==($m[k]-k)#检验副对角线
  end
  return true
end
EightQueen(8)[/code]

[[i] 本帖最后由 jmouse 于 2008-4-28 16:01 编辑 [/i]]

回溯的思想比较简单，是一种摸着石头过河的想法。
总结起来就是，能进则进，不能进则退，退到底就结束。
所以，一般写回溯是一个while true过程（这也就是为什么没写好就会死循环的原因）。
出口有2个，一个是找到解，一个是退到头，于是，我们应该至少看到一个break（如果需要找到全部解，那就只有一个break了）。以及一个print（打印解）。
然后，我们肯定要有“前进”的动作，这里的前进有2个意思，一个是进一步，一个是在本步上采用下一个选择。
最后，我们需要一个check方法来决定当前的摸索是否可行。
最后的最后，想一个简单点的模型来对付你要完成的事情。
还要注意，退步的时候要让现场还原。

总结一下：[code]#预备工作
while true
#  当前步骤下一选择；
#  若当前步骤已无选择，则退一步；若退到头，则结束。
#  有选择，检验是否合理；
#   合理，进一步，若已到最后一步，则出解。（结束或者继续随意）。
#  不合理，退一步。
end[/code]

嗯～学习了

ORZ, 彻底学习了。

回溯难就难在“简单的”数据模型上了，这个模型决定了你该怎么进，怎么退，怎么还原！
这个模型同样决定了你程序的可读性和可维护性甚至可扩充性。
虽然执行效率是肯定回溯高，但不是特别需要我还是会选择递归或者穷举。
当然定义巧妙的数据模型还是非常值得欣赏的。
比如题目的八皇后问题，定义2维数组结构的程序可以肯定不如定义1维数组的程序效率高。:lol

Jmouse的做法已经说得很清楚了，我说说我的做法：
首先根据题意 8*8的棋盘放8个不能互吃的皇后，
那么肯定：
1 每一行有且只有1个皇后。
2 同样每一列有且只有1个皇后。

我们把每一行皇后的位置看成一个数，总共有8个数字。
结果可以肯定是1到8这八个数字的排列方式。
所以我首先是利用以前做的全排列函数找出所有可能的排列方式，
然后定义一个检查函数去掉对角线能互吃的情况。
然后输出结果。

相信对于初学者来说，会更容易理解一点吧。:lol

[[i] 本帖最后由 bbschat 于 2008-4-30 19:02 编辑 [/i]]

支持支持支持支持支持支持

找到了点门路，呵呵，继续跟进！

新手~新手~请指教