请教有关水晶构建魔法阵的算法问题。

汪汪

举例，
有n个水晶（建立了一个关于属性的1-n的hash表），
水晶有属性（水火风雷光暗共6种）
要构建魔法阵，需要属性水水晶x个，属性风的水晶y个，属性暗的水晶z个，
问魔法阵能否构建成功。
如果水晶只有一种属性，问题十分简单，但是有m个水晶同时具有两种及两种以上属性，使用时可以当所拥有的一种属性的水晶使用。
（如风水属性的水晶，可以当风属性水晶使用，也可以当水属性水晶使用，但是只能当一种，即当风属性水晶使用时不能当水属性水晶使用）
如何计算这些水晶能否构建魔法阵？
实在想不出好办法，求指点。说思路也可以。

1090782026

{:4_96:}

LHY4118

脚本不行为何不使用事件做法
设立能将风水水晶换成风水晶或者水水晶的事件
然后只要判定原来的六种水晶就好了嘛

Thylakoid

RyanBern 发表于 2015-5-16 10:19
不要总是想去把问题丢给人脑解决，这样的话你是写不出算法来的。回避问题并不是很好的选择，该面对的问题 ...

RyanBern

Thylakoid 发表于 2015-5-16 00:39
你这样做的话，在统计数量的时候要把水晶本身的数量和共有属性数量以及各属性所需的数量关联到一起去统计 ...

不要总是想去把问题丢给人脑解决，这样的话你是写不出算法来的。回避问题并不是很好的选择，该面对的问题还是要面对。否则就只能写出一些简单的UI了，程序写着也没什么意思。

使用穷举法，前提之一就是你得会穷举。如果个人的穷举水平不够的话，是写不出来穷举法的。就这个问题而言，我们应该考虑最复杂的情况，而不是那些比较简单的情况。在这个回帖里面，我分别回答你提出的两个问题，这两个问题，如果你排列组合学的够好的话，应该能够想到。如果想不到，那建议还是多学习一下这部分，因为作为一个写程序的人，还是需要一些排列组合的基础。

1.对于水晶种类的分类问题。
这个问题我在回帖中多次提到，既然你已经能够算出，假设所有属性有 n 个，那么不同属性组合一共有 2^n - 1种（去掉空组合）。那么我们就用1~2^n - 1这些整数来表示这所有的属性组合。方法是二进制数法。具体的操作请看我6L的第三个例子，不多说了。

2.对于同一种类的水晶，属性分配的问题。
例如，我们一共有属性为风水土的水晶（3属性水晶）m个，那么我们要举出来这些水晶究竟有多少种分配方式，即有多少个水晶被当做风属性水晶使用，有多少个被当做水属性的，有多少个被当成土属性的。这就是你说的第二个问题。这个问题抽象成数学问题就是，假如 n 个非负数的和是 m，那么这 n 个非负数有多少种可能？（在这里要考虑顺序，比方说x1 = 1, x2 = 2和x1 = 2, x2 = 1这两种情况认为是不同的）。这是一个经典的排列组合问题，它的解也比较简单，为此，我们形象地画一下下面这个图。

* * * * * * ... *

在这个图里面，'*'表示的是一列元素，共 m 个，有先后顺序，现在把他们分成 n 组。显然，对于一种固定的分法，就对于了我们刚才那个问题的一个解，而且这个对应是一一对应！（这点想想就能明白）至于分法，也非常简单，只需要在 m 个'*'形成的 m - 1个间隙中插入分隔符'|'即可（这里的间隙显然不算第一个'*'前面的那个地方和最后一个'*'后面的那个地方）。例如，一种可能的分法就是这样：

* * | * * * | * ... * | *

由于你要分成 n 组，所以你要插入的分隔符就是 n - 1 个分隔符。这个利用组合数公式得知，总共的分法一共就有C(m-1, n-1)种。但是我们注意到，如果这样分的话，每一组的'*'的个数至少是1，而我们允许在分的过程中某组的'*'的个数取0。那这个问题该如何解决？
实际上，我们可以将'*'的个数添加 n 个进去，这样一共就有 m + n 个'*'了，对这些'*'，仍然分成 n 组，这样得到的分法是C(m + n - 1, n - 1)。当然，这样分的话，每一组的'*'的个数至少是1，之后，我们把分好的每个组中的'*'都拿走一个，这样，'*'的总数还是 m ，而且每一组'*'的个数大于等于0。可以验证，这样的对应是一一对应（可能需要想一下）。所以，我们得到结论， n 重属性的水晶有 m 个，现在把这些水晶分配到不同的属性中去，总共的分法就是C(m + n - 1, n - 1)种。当然穷举出一个组合数来并不难，而且也不必按照我们刚才“添加删除”的方式去写，如果利用递归写法的话，程序会很短很短。这个实现问题就留给你去思考吧。

Thylakoid

汪汪 发表于 2015-5-13 07:18
这里我也说一下我的大致想法，不知道可不可行。首先我们已经确定的是魔法阵的属性要求了，所以只要挑选水晶 ...

你这样做的话，在统计数量的时候要把水晶本身的数量和共有属性数量以及各属性所需的数量关联到一起去统计。比如现在有a个风水、b个风火、c个风暗、d个雷暗和e个光暗，而且将这d个雷暗和e个光暗都当成暗去使用依然不够。那么需要从c个风暗中拿出一些来当成暗才够，这样才有解。当然风暗被当成暗之后，就不能当成风了。但是如果不这样做，而是把风暗当成风，那么暗肯定不够，最后无解，魔法阵不能构建。那么这里就有一个问题。x水+y风+z暗=魔法阵，这里的x、y、z不一定相等。很可能造成a+b+c<d+e<z的情况，也就是说即使我含有某项属性的水晶总和很小，也足够用，但另一种属性即使数量多，但还是不够用的情况。其他属性同理，而且这里只计算了5种复数属性且每种只含两个属性的水晶，更复杂的还没考虑。那么这里的优先级如何设计，或者说如何根据现在可能发生的各种各样的情况去设计循环也好、穷举也好的顺序？当时我写的时候，写到这里就发现，我不能强行造一个顺序去循环判断魔法阵的构成条件，否则很可能得到的不是最优解（有浪费），甚至本应有解结果无解（优先级对当前情况不适用）。必须依照每一种情况给出不同的顺序，才可能确保不丢解，并找到最优解。这样的话，问题还是会落到“哪些水晶要被当成哪个属性来使用”这一点上。目前这个例子只有5种水晶、且只有风、暗2个属性之间的冲突。全组合63个，每32个可以算作同一属性，属性与属性之间还有交集，并且全顺序也是一个组合数，要好几层嵌套才能表示万全。所以，那时我才认为，既然本身这个问题就是一个在无序中找解的问题，那就不要强迫电脑拐弯抹角地在无序中找顺序，直接把这个无序状态丢给人，并给人一个固定的顺序——先放什么属性再放什么属性最后放什么属性。但这个顺序是假顺序，真顺序是人脑在资源使用时的思考——目前的情况下用哪些水晶做这种属性可以确保完成魔法阵且最省。让人动脑找解。至于能否找到、是否最优，那要看作为人的这名玩家是否有水平。而制作者，只需要让电脑判断当前被使用的水晶是否符合使用规则就够了。当然，就算只是制作规则的判定条件，属性库的分类构建以及判定条件相关的变量操作依然是个辛苦活。不过话说回来，如果真能利用电脑程序写出一个面面俱到的最一般化的通式算法，那水平不仅可以解决这个水晶与魔法阵的问题，应该也可以用RM引擎去给跳棋甚至象棋写智能AI了。我肯定没那个水平，所以我走多动手的特殊化路线。

RyanBern

谈谈如何编写有效的穷举算法

在写程序的时候，我们或多或少都会碰到算法的问题。而算法中最简单的一种，莫过于穷举法。因穷举法好想，好写，比较无脑，所以被很多人所青睐。虽然从效率的角度上来说，穷举法的效率不高，而且解决问题比较笨，看起来很low的样子。但是，作为一种基本的简单算法，穷举法的适用范围可谓是非常广泛，几乎所有的问题都可以用穷举法解决。如果说，效率低是穷举法的一个缺点，那么适用面广绝对是穷举法的一个巨大的优点。况且，现在算法的发展十分迅速，高效率的穷举法也可谓是比比皆是。那么，如何有效率地进行穷举，也属于我们应该学习的范围。

言归正传，那么穷举法应该如何写出呢？可能有人觉得穷举法不是特别难写，那是因为涉及到的问题都比较简单。
在这里，我把穷举的方式分为三种，普通穷举，深度优先搜索（回溯法），广度优先搜索。后面两种属于有一定筛选条件的搜索方法，适用于一些穷举上比较困难的问题，也具有减少穷举次数的能力。严格意义上来讲，几种方式的界限有时候并不是很清楚。但是对于同一个问题，不同方法的实现还是有区别的。

（一）普通穷举
所谓普通穷举，概括来讲，需要你做下面两个事情：
1.如何按照一定顺序把可能的组合列举出来
2.对于给定的组合，如何计算它是否满足题目要求，或者是在优化问题中，对应的数值是多少。
只要能有办法完成上面两步，那么穷举法就一定能够进行。
下面举一个例子：
某人开枪射击，每次射中的环数为0~10之内的整数，他一共开了5枪，总共的环数为25环。问：他各枪打出的环数组合有多少种？在这里，打出的环数和顺序加以区分，例如[5, 5, 5, 4, 6]和[5, 5, 5, 6, 4]认为是不同的。（这道题是R考场第二期的附加题A题）
那么我们分开进行这两步。
1.所有组合都要按照一定规则列举出来，我们可以先考虑第 i 枪的环数x(i)，每个x(i)取值于0~10，然后对每一枪考虑即可。
2.对于一个组合x(1), x(2), ... x(5)，如果它们加起来等于25，那么符合要求，结果计数变量 +1 即可。
所以，可以写出如下代码：

RUBY 代码复制

def solve(score)
  result = 0
  for x1 in 0..10
    for x2 in 0..10
      for x3 in 0..10
        for x4 in 0..10
          for x5 in 0..10
            result += 1 if x1 + x2 + x3 + x4 + x5 == score
          end
        end
      end
    end
  end
end

def solve(score)


  result = 0


  for x1 in 0..10


    for x2 in 0..10


      for x3 in 0..10


        for x4 in 0..10


          for x5 in 0..10


            result += 1 if x1 + x2 + x3 + x4 + x5 == score


          end


        end


      end


    end


  end


end

代码很容易看，所以我就不解释了，原理就是一个个结果去试，但是前提你要能够用一种方式把所有结果列举出来。
我们再看个例子，请设计一个算法，判断一个字符串a中是否含有某字符串b，例如a="bookkeeper"，b="ookkee"，那么a就是含有b。（即b是a的一个子串）
首先我们想想，如果b是a的子串，那么所有的情况可以按照b的第一个字符在a中的位置进行区分，总共的可能数为m - n + 1，其中 m 是a串的长度，n 是b串的长度，并且规定m >= n。然后找到了这个位置，只需判断从这个位置起是否含有b就可以了。

CPP 代码复制

bool is_substring(char *a, int m, char * b, int n){
    for (int i = 0; i < m - n ; i++){
        for(int j = 0; j < n ; j++){
            if (a[i + j] != b[j]) break;
            if (j == n - 1) return true;
        }
    }
    return false
}

bool is_substring(char *a, int m, char * b, int n){


    for (int i = 0; i < m - n ; i++){


        for(int j = 0; j < n ; j++){


            if (a[i + j] != b[j]) break;


            if (j == n - 1) return true;


        }


    }


    return false


}

代码的原理也比较简单，看一下就没什么问题。在这里我们注意到穷举法涉及到的循环比较多，如果搞不清循环之间的关系，有可能会出错。
再举一个穷举规则稍微复杂一点的例子。假设给定一个序列，长度为 n，序列里面的元素都是正整数。现在问，如果从序列中抽出一列子列，并且要求该子列是单调不增的，那么这个子列最长是多少。注：称一个序列是另外一个序列的子列，是指将原来序列的若干项抽出来，并按照原来顺序排成一列；称一个序列单调不增，指的是该序列的数字后面的一个总不大于前面的一个。（此题为R考场第二期附加题B题）
经过分析，我们需要做的第一件事情就是如何把所有子列都列举出来。进而判断他是否是单调不增。
如果该序列确实符合要求，那么则计算该序列的长度（实际可以用数组的大小表示）
那么，如何列举所有子列出来呢？通过简单的分析，我们知道，如果原序列的长度是 n，那么它所有非空子列的总数就是2^n - 1。也就是说，对于固定位置的数字，要么出现在子列中，要么不出现在子列中，总共只有2种可能，一共 n 个位置，就是 n 个 2 相乘。又要求子列非空，所以结果要去掉 1 。下面我们要做的就是列出所有的子列。
我们知道，如果用 0 表示不在子列中，1表示在子列中，那么我们可以得到一个长度为 n 的0-1序列，这个0-1序列就能表示所有的子列，而这本身又是一个数字的二进制表示。所以我们考虑用一个整数来表示一个序列，表示的方法就是把整数看成二进制数，如果某个位上的数为 1，那么该位上的数字便在子列当中。为了方便起见，我们的整数位数从右到左算起，即二进制数110(对应十进制的6)的第 0 位为0，第 1 位为 1，第 2 位为 1。如果序列a的长度为3，那么110(6)对应的序列就是a[1], a[2]组成的子列。
现在列举的方法已经叙述完毕，那么该如何操作呢？这就涉及到位运算了。一个二进制数，如果我想要知道它的第 i 位是什么，我只需要做右移 i 位的运算，然后看第 0 位的数值即可。在这里位数依然是从右向左的。例如我想知道110(6)的第 2 位是什么，那么我就把它右移 2 位，然后取出第 0 位即可。取出第 0 位的过程可以使用按位与'&'运算。
最后就是如何判断数列是否符合要求，这个比较简单，就不说了。
从上面的思路，我们可以大致写出代码出来了。

RUBY 代码复制

def solve_max_sub_seq(seq)
  n = seq.size
  max = 1
  (1...2 ** n).each do |digit|
    sub_seq = []
    flag = true
    (0...n).each do |pos|
      if (digit >> pos) & 0x01 == 1
        if sub_seq.size == 0 || sub_seq[-1] >= seq[pos]
          sub_seq << seq[pos]
        else
          flag = false
          break
        end
      end
    end
    max = [max, sub_seq.size].max if flag
  end
  return max
en
d

def solve_max_sub_seq(seq)


  n = seq.size


  max = 1


  (1...2 ** n).each do |digit|


    sub_seq = []


    flag = true


    (0...n).each do |pos|


      if (digit >> pos) & 0x01 == 1


        if sub_seq.size == 0 || sub_seq[-1] >= seq[pos]


          sub_seq << seq[pos]


        else


          flag = false


          break


        end


      end


    end


    max = [max, sub_seq.size].max if flag


  end


  return max


en


d

结合上面的思路，看懂此代码应该不难。
（二）深度优先搜索（回溯法）
如果说第一部分是最普通的穷举，把所有可能的情况都列出来，那么这一部分则是有选择的穷举，只是把符合条件的情况列举出来，并加以比较。和普通穷举相比，它大量减少了枚举次数，以便在尽可能少的空间里面需求我们需要的解。
回溯法的原理其实非常简单，例如，我们要列举出所有符合条件的解，而写出这个解我们需要 n 步，每一步我们总共有a(n)种选择，那么我们只需要从第一步开始，依次向下进行即可。当然，每一步我们需要出一种选择，在这里我们按照一定的顺序把选择遍历一遍。一旦选定了一个选择之后，我们就进行下一步的选择（而不再考虑同一步的其他选择）。而到某一步时，我们发现解已经生成或者中途再无选择可做，我们就需要退回到上一部，更改我们上一部的选择（这就是所谓回溯）。当所有选择都遍历完毕时，符合条件的解就已经找到了。
这样说还是很难理解，我们说得形象一点好了。玩RPG的人或多或少都会碰到走迷宫的关卡，而有一种很著名的“贴墙法”，我相信很多人也听说过。简单来说，从迷宫的入口出发，如果遇到岔路就走左边那一条，如果遇到死路就原路返回。这个方法就是一个回溯法。不过这种方法也有一定的缺陷，就是无法处理环路的情况。当把原路返回的条件改成“遇到死路或者走过的路”，那么算法就可以执行下去。
和深度优先相关联的的数据结构就是“栈”，建议在维基百科上查询。
因此我们不妨把这个迷宫问题作为一道例题，来看看回溯法如何编写。
迷宫的数据结构是一个n*n的Table，左上角的(0, 0)位置是起点，右下角的(n-1, n-1)是终点。表格中，数字0表示可以通行，数字1表示不能通行。人只能竖着走或者是横着走。
例如，n = 5时，一个迷宫可以是下面的这样（为了方便起见，起点用s表示，终点用e表示，s和e都是可通行的，实际的数据还是0和1）：

s 1 0 0 0
0 0 0 1 1
1 1 0 0 1
0 0 0 1 1
1 1 0 0 e

对于每一个点，我们对四个方向做试探，试探的顺序为[下左右上]，如果发现某个方向能够走通，不管这条路将来通向哪里，我们都往这个方向走一步，并且，最重要的，我们需要把当前的位置做标记，从而记录我们到过的位置和选择的方向，这一步是回溯必不可少的环节。记录我们到过的位置是为了避免走重复的路从而绕圈，而记录选择的方向是为了给回溯做准备，如果某个方向的路没有走通，那么接下来将从何处开始。
我在下面的代码里面写了详细的注释，请认真阅读并领会回溯法的过程。

RUBY 代码复制

module Maze
  # 记录路径点的类，每个点记录坐标和行走方向
  class Path_Point
    attr_accessor :x         # 该点 x 坐标
    attr_accessor :y         # 该点 y 坐标
    attr_accessor :d         # 该点行走方向，0 : 向下，1 : 向左，2 : 向右，3 : 向上
    def initialize(x = 0, y = 0, d = -1)
      @x = x
      @y = y
      @d = d
    end
  end
  # 判断坐标是否有效（不能走出迷宫外）
  # map是一个 Table 对象
  def valid?(x, y, map)
    return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize
  end
  # 求迷宫的一条路径
  # map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑
  def self.solve(map)
    # 记录迷宫路径点所用栈
    stack = []
    # 方向数组，方便表示向各个方向行走时的坐标增量
    direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
    # 给起点做标记
    map[0, 0] = 2
    # 起点入栈
    stack.push(Path_Point.new(0, 0, -1))
    # 当栈不空时，证明还有路径点需要处理，此时进行循环
    while !stack.empty?
      # 取出栈顶元素
      point = stack.pop
      # 试探下一个方向
      point.d += 1
      # 当该方向是有效方向时
      while point.d <= 3
        # 计算沿着该方向行走一步之后的新坐标
        new_x = point.x + direction[point.d][0]
        new_y = point.y + direction[point.d][1]
        # 如果走到终点(Table右下角的点)
        if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0
          # 此时栈中的路径点合起来就是一条路径
          # 但是还缺少两个点：当前点和终点
          # 把当前点和终点加上就是一条完整路径
          stack << point
          stack << Path_Point.new(new_x, new_y)
          # 返回 stack 数组
          return stack
        end
        # 如果下一步的坐标在地图内，并且是没有走过的通路
        if valid?(new_x, new_y, map) && map[new_x, new_y] == 0
          # 走向下一个路径点，并做标记为已走过
          map[new_x, new_y] = 2
          # 当前点入栈，记录
          stack << point
          # 设置当前点为新的路径点
          point = Path_Point.new(new_x, new_y)
        end
        # 无论是否找到新路径点，point的d值均 +1
        # 如果point为新路径点，那么此操作会让其d值从-1变为0，可操作
        # 如果point为原有路径点，那么此操作是试探下一个可能的方向
        point.d += 1
      end
    end
    # 如果栈为空，依然没有找到通路，返回 nil
    return nil
  end
end

module Maze


  # 记录路径点的类，每个点记录坐标和行走方向


  class Path_Point


    attr_accessor :x         # 该点 x 坐标


    attr_accessor :y         # 该点 y 坐标


    attr_accessor :d         # 该点行走方向，0 : 向下，1 : 向左，2 : 向右，3 : 向上


    def initialize(x = 0, y = 0, d = -1)


      @x = x


      @y = y


      @d = d


    end


  end


  # 判断坐标是否有效（不能走出迷宫外）


  # map是一个 Table 对象


  def valid?(x, y, map)


    return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize


  end


  # 求迷宫的一条路径


  # map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑


  def self.solve(map)


    # 记录迷宫路径点所用栈


    stack = []


    # 方向数组，方便表示向各个方向行走时的坐标增量


    direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]


    # 给起点做标记


    map[0, 0] = 2


    # 起点入栈


    stack.push(Path_Point.new(0, 0, -1))


    # 当栈不空时，证明还有路径点需要处理，此时进行循环


    while !stack.empty?


      # 取出栈顶元素


      point = stack.pop


      # 试探下一个方向


      point.d += 1


      # 当该方向是有效方向时


      while point.d <= 3


        # 计算沿着该方向行走一步之后的新坐标


        new_x = point.x + direction[point.d][0]


        new_y = point.y + direction[point.d][1]


        # 如果走到终点(Table右下角的点)


        if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0


          # 此时栈中的路径点合起来就是一条路径


          # 但是还缺少两个点：当前点和终点


          # 把当前点和终点加上就是一条完整路径


          stack << point


          stack << Path_Point.new(new_x, new_y)


          # 返回 stack 数组


          return stack


        end


        # 如果下一步的坐标在地图内，并且是没有走过的通路


        if valid?(new_x, new_y, map) && map[new_x, new_y] == 0


          # 走向下一个路径点，并做标记为已走过


          map[new_x, new_y] = 2


          # 当前点入栈，记录


          stack << point


          # 设置当前点为新的路径点


          point = Path_Point.new(new_x, new_y)


        end


        # 无论是否找到新路径点，point的d值均 +1


        # 如果point为新路径点，那么此操作会让其d值从-1变为0，可操作


        # 如果point为原有路径点，那么此操作是试探下一个可能的方向


        point.d += 1


      end


    end


    # 如果栈为空，依然没有找到通路，返回 nil


    return nil


  end


end

仿照上面的回溯算法，我们可以解决著名的“八皇后问题”。
例：八皇后问题。国际象棋的棋盘为8*8的方阵，现在在这个棋盘上放置8枚“皇后”棋子，要求这8枚皇后的任何两枚都不能互相进攻。注：在棋盘上，皇后的行走规则是横、竖、对角线，也就是说，我们需要任何两个皇后都不能在同一行，同一列，或者是同一对角线上。请列举出所有可能的放置方法。
分析：我们利用回溯法求解此题。首先，我们并不知道可行的解究竟长成什么样子，只能一个一个进行试探。如果利用普通的穷举法，先把所有可能的放置方法穷举一遍，然后判断某个固定的放置方法是否符合要求，如果符合要求就输出。利用普通的穷举法，一共要列举8^8种情况。再对于每一种情况进行判断，任意两个皇后都不能互相攻击，还需要比较8*7/2=28次，计算代价较高。因此我们放弃普通的穷举法。
那么回溯法的思想是怎样的呢？首先，我们一步一步进行试探。我们先放置第一列（或者第一行的皇后，在这里我们统一选择第一列），因为我们不知道解长成什么样子，所以我们不妨取第一列的第一个位置，放置第一个皇后。放置完毕后，我们需要考虑这个皇后带给其他位置的影响，即“假设这个位置有皇后，那么哪些地方不能再放置皇后了呢”？显然，和它同行，同列，以及同对角线的位置都不能放置。为了简单起见，由于我们接下来放置的是第二列的皇后，本来就不会跟第一列的皇后在同一列上，因此对列的考虑可以省去。考虑影响之后，我们放置第二列的皇后，选择的位置当然是已经排除了第一个皇后产生影响之外的位置。放置第二列的皇后之后，我们还需要考虑第二个皇后对其他位置的影响。
以此列推，我们这样不断放置，直到遇到下面两种情况之一：
（1）成功放置了第8列的皇后。
（2）放置了某列时，发现所有的位置均不能放置。
出现这两种情况之后，我们需要做的事情是一样的，就是要把最近一列的皇后移除，然后考虑下一个可能的位置。如果不存在下一个可能的位置，那么就继续移除最近一列的皇后。当所有可能的位置都不存在时，证明穷举已经结束了。（1）和（2）的不同之处在于，（1）情况时，你要先输出这组解，然后再进行回退，而（2）情况不需要。同时，一定要注意，将某个皇后从棋盘上移除时，记得要清除它对其他位置造成的影响。
上面的两个过程用图表示大概是这样的。我们假设棋盘是4*4的（0表示可用位置，1表示不可用位置，*表示皇后）：

* 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1

* 1 1 1 1 1 1 0 1 * 1 0 1 1 1 1

* 1 1 1 1 1 0 1 1 1 1 1 1 * 1 1

这是个例子，从第二个格子到第三个格子就发生了回溯，因为如果将第二列的皇后放在第三个位置上，那么第三列的位置均不可用，所以应该试探第二列第四个位置。
此问题的代码和上面的那个迷宫问题基本相似，我在这里不给出注释，看看你能不能理解吧。

RUBY 代码复制

module Queen_Problem
  class Queen
    attr_accessor :x
    attr_accessor :y
    def initialize(x = 0, y = 0)
      @x = x
      @y = y
    end
  end
  # 判断坐标是否有效
  # map是一个 Table 对象
  def valid?(x, y, map)
    return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize
  end
  # 设置位置限制
  def set_restriction(queen, map, res = 1)
    return unless valid?(queen.x, queen.y, map)
    d = 1
    for i in queen.y + 1...map.ysize
      [-d, 0, d].each do |j|
        map[j, i] += res if valid?(j, i, map)
      end
      d += 1
    end
  end
  # 消除位置限制
  def remove_restriction(queen, map)
    set_restriction(queen, map, -1)
  end
  def self.solve(map)
    stack = []
    stack.push(Queen.new(-1, 0))
    while !stack.empty?
      queen = stack.pop
      remove_restriction(queen, map)
      queen.x += 1
      while queen.x < map.xsize
        if queen.y == map.ysize 
          p stack
          queen = stack.pop
        elsif valid?(queen.x, queen.y, map) && map[queen.x, queen.y] == 0
          set_restriction(queen, map)
          stack << queen
          queen = Queen.new(-1, queen.y + 1)
        end
        queen.x += 1
      end
    end
  end
end

module Queen_Problem


  class Queen


    attr_accessor :x


    attr_accessor :y


    def initialize(x = 0, y = 0)


      @x = x


      @y = y


    end


  end


  # 判断坐标是否有效


  # map是一个 Table 对象


  def valid?(x, y, map)


    return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize


  end


  # 设置位置限制


  def set_restriction(queen, map, res = 1)


    return unless valid?(queen.x, queen.y, map)


    d = 1


    for i in queen.y + 1...map.ysize


      [-d, 0, d].each do |j|


        map[j, i] += res if valid?(j, i, map)


      end


      d += 1


    end


  end


  # 消除位置限制


  def remove_restriction(queen, map)


    set_restriction(queen, map, -1)


  end


  def self.solve(map)


    stack = []


    stack.push(Queen.new(-1, 0))


    while !stack.empty?


      queen = stack.pop


      remove_restriction(queen, map)


      queen.x += 1


      while queen.x < map.xsize


        if queen.y == map.ysize 


          p stack


          queen = stack.pop


        elsif valid?(queen.x, queen.y, map) && map[queen.x, queen.y] == 0


          set_restriction(queen, map)


          stack << queen


          queen = Queen.new(-1, queen.y + 1)


        end


        queen.x += 1


      end


    end


  end


end

（三）广度优先搜索（BFS）
这是第二种有选择的搜索方式，我们称其为广度优先搜索。它相当于是深度优先搜索的相对方法。在深度优先搜索中，我们遇到分支的情况，会毫不犹豫地进入到一个分支中，然后遇到分支就进入，直到找到的问题的解或者是回头。而广度优先搜索，则是在遇到分支时，不急着进入一个分支当中，而是把当前分支的所有情况考虑之后，再进行下一步。
和深度优先相似，广度优先搜索也有专门的数据结构，那就是“队列”，建议在维基百科上查询相关内容。
我们还是拿走迷宫举例，上面我们说，深度优先是“一条路走到黑”地搜索，那么广度优先就是一种“地毯式”的搜索。我们回忆在深度优先中，我们遇到岔路就指定一个方向，然后继续走下去，那么在广度优先中，我们要如何做呢？
首先，我们在起点位置，假如走到某个地方发现有分支，那么，相对地，我们要考虑所有的分支方向，在这里，我们假设自己可以“分身”。那么遇到分支，我们“分身”出与分支个数相同的分身，然后让这些“分身”来测试每个路径。如果分身遇到岔路，就继续“分身”。直到某一个分身到达了出口为止。值得注意的是，如果分身在途中遇到了死路，或者是其他分身已经走过的路，那么该分身就应该消失。显然，在广度优先搜索中，每种情况处理且只处理了一次。
基于这个想法，我们写出代码如下。在代码里，我详细给出注释，请仔细比较此代码和深度优先搜索代码的不同。

RUBY 代码复制

module Maze
  # 记录路径点的类，每个点记录坐标和行走方向
  class Path_Point
    attr_accessor :x         # 该点 x 坐标
    attr_accessor :y         # 该点 y 坐标
    def initialize(x = 0, y = 0)
      @x = x
      @y = y
    end
  end
  # 判断坐标是否有效（不能走出迷宫外）
  # map是一个 Table 对象
  def valid?(x, y, map)
    return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize
  end
  # 求迷宫的一条路径
  # map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑
  def self.solve(map)
    # 记录待处理路径所用队列
    queue = []
    # 方向数组，方便表示向各个方向行走时的坐标增量
    direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
    # 方向 Table，用于记录各个点的上一个点是哪个方向的。-1 : 起点，0 : 下，1 : 左，2 : 右，3 : 上。
    dir_table = Table.new(map.xsize, map.ysize)
    # 给起点做标记，记录方向
    map[0, 0] = 2
    dir_table[0, 0] = -1
    # 起点入队列
    queue.push(Path_Point.new(0, 0))
    # 当队列不空时，证明还有路径点需要处理，此时进行循环
    while !queue.empty?
      # 取出队列最前面的元素
      point = queue.shift
      # 试探每个方向，k 表示试探方向
      k = 0
      while k <= 3
        # 计算沿着该方向行走一步之后的新坐标
        new_x = point.x + direction[k][0]
        new_y = point.y + direction[k][1]
        # 如果走到终点(Table右下角的点)
        if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0
          # 此时要回溯路径，具体方法在后面给出
          # 注意方向的反转问题
          return make_reverse_path(Path_Point.new(new_x, new_y)).reverse
        end
        # 如果下一步的坐标在地图内，并且是没有走过的通路
        if valid?(new_x, new_y, map) && map[new_x, new_y] == 0
          # 做标记为已走过
          map[new_x, new_y] = 2
          # 记录该新点的来路方向，注意方向的反转问题
          dir_table[new_x, new_y] = 3 - k
          # 新路径点入队列
          queue << Path_Point.new(new_x, new_y)
        end
        # 考虑下一个方向
        k += 1
      end
    end
    # 如果队列为空，依然没有找到通路，返回 nil
    return nil
  end
  # 由路径终点倒推，产生路径
  # dir_table : 用于记录来路方向的表格
  def make_reverse_path(final_point, dir_table)
    path = []
    # 设定初值
    point = final_point
    d = dir_table[point.x, point.y]
    # 方向数组，方便表示向各个方向行走时的坐标增量
    direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
    while d != -1
      # 把该点放入路径
      path << point
      # 获取来路方向
      d = dir_table[point.x, point.y]
      # 获取来路坐标
      new_x = point.x + direction[d][0]
      new_y = point.y + direction[d][1]
      # 当前点转换为来路
      point = Path_Point.new(new_x, new_y)
    end
    # 此时起点还未放入路径
    path << point
    # 此时的 path 为反转路径
    return path
  end
end

module Maze


  # 记录路径点的类，每个点记录坐标和行走方向


  class Path_Point


    attr_accessor :x         # 该点 x 坐标


    attr_accessor :y         # 该点 y 坐标


    def initialize(x = 0, y = 0)


      @x = x


      @y = y


    end


  end


  # 判断坐标是否有效（不能走出迷宫外）


  # map是一个 Table 对象


  def valid?(x, y, map)


    return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize


  end


  # 求迷宫的一条路径


  # map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑


  def self.solve(map)


    # 记录待处理路径所用队列


    queue = []


    # 方向数组，方便表示向各个方向行走时的坐标增量


    direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]


    # 方向 Table，用于记录各个点的上一个点是哪个方向的。-1 : 起点，0 : 下，1 : 左，2 : 右，3 : 上。


    dir_table = Table.new(map.xsize, map.ysize)


    # 给起点做标记，记录方向


    map[0, 0] = 2


    dir_table[0, 0] = -1


    # 起点入队列


    queue.push(Path_Point.new(0, 0))


    # 当队列不空时，证明还有路径点需要处理，此时进行循环


    while !queue.empty?


      # 取出队列最前面的元素


      point = queue.shift


      # 试探每个方向，k 表示试探方向


      k = 0


      while k <= 3


        # 计算沿着该方向行走一步之后的新坐标


        new_x = point.x + direction[k][0]


        new_y = point.y + direction[k][1]


        # 如果走到终点(Table右下角的点)


        if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0


          # 此时要回溯路径，具体方法在后面给出


          # 注意方向的反转问题


          return make_reverse_path(Path_Point.new(new_x, new_y)).reverse


        end


        # 如果下一步的坐标在地图内，并且是没有走过的通路


        if valid?(new_x, new_y, map) && map[new_x, new_y] == 0


          # 做标记为已走过


          map[new_x, new_y] = 2


          # 记录该新点的来路方向，注意方向的反转问题


          dir_table[new_x, new_y] = 3 - k


          # 新路径点入队列


          queue << Path_Point.new(new_x, new_y)


        end


        # 考虑下一个方向


        k += 1


      end


    end


    # 如果队列为空，依然没有找到通路，返回 nil


    return nil


  end


  # 由路径终点倒推，产生路径


  # dir_table : 用于记录来路方向的表格


  def make_reverse_path(final_point, dir_table)


    path = []


    # 设定初值


    point = final_point


    d = dir_table[point.x, point.y]


    # 方向数组，方便表示向各个方向行走时的坐标增量


    direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]


    while d != -1


      # 把该点放入路径


      path << point


      # 获取来路方向


      d = dir_table[point.x, point.y]


      # 获取来路坐标


      new_x = point.x + direction[d][0]


      new_y = point.y + direction[d][1]


      # 当前点转换为来路


      point = Path_Point.new(new_x, new_y)


    end


    # 此时起点还未放入路径


    path << point


    # 此时的 path 为反转路径


    return path


  end


end

（四）剪枝技术
说完了普通穷举和两种搜索方法，下面简单说下这个剪枝技术。剪枝技术是对于两种搜索方式有比较好的效果。那么，什么是剪枝技术呢？在深度优先搜索和广度优先搜索中，如果我们遇到了选择分支，那么我们就以某种方式进入到这个分支当中。但是，如果我们能够在进入分支之前，对分支的情况估计一下，如果满足一定的条件才进入分支，否则不进入，这就是我们所谓的“剪枝技术”。这就好像把本来应有的分支统统减掉，不去进行搜索一样。
我们举个例子，假如我们在一系列过程中要寻找最优解。现在，我们已经进行了若干步搜索，搜索到了若干解，而且这些解中最大值为20（假设数值最大的解是最优解）。那么，我们在对其他情况继续搜索的时候，如果我们能想办法在搜索之前能够估计出来这个解的上界，例如，如果沿着另外一个方向搜索，解最大值不会超过19，现在我已经有了一个值为20的解了，那么沿着该方向就完全不必继续搜索了。这就是剪枝技术。
下面是一个非常特殊的例子，虽然拿它当做剪枝的例子未必合适，但是至少说明了“剪枝”的思想。
例：计算斐波那契数列，其中，a(0)=a(1)=1，a(n+1)=a(n)+a(n-1)，即某一项是它前面两项的和。
为了简单起见，我们称斐波那契数列的第 n 项为 Fib(n)，于是，如果我们要知道Fib(n)，那么就要知道Fib(n-1)和Fib(n-2)，利用简单的递归写法，我们马上就能写出这样的程序：

RUBY 代码复制

def fib(n)
  if n == 0 || n == 1
    return 1
  end
  return fib(n-1) + fib(n-2)
end

def fib(n)


  if n == 0 || n == 1


    return 1


  end


  return fib(n-1) + fib(n-2)


end

上面的这个代码比较短，原理也很清楚，就是利用分支，不断地对 n 进行缩减，最后都归结为算Fib(0)和Fib(1)。
你可以试试在计算机上调用fib(40)，然后，计算机就会算上一分钟，然后告诉你答案。这未免有点太慢了。我们看看这个方法的执行过程，以求Fib(4)为例：
Fib(4)-Fib(3)--Fib(2)-Fib(1)
    |        |            |
    |        |            -----Fib(0)
    |        |
    |        -------Fib(1)
    |
    |
    -----Fib(2)--Fib(1)
             |
             -------Fib(0)
通过上面的图，我们可以看到，计算Fib(4)时需要Fib(3)和Fib(2)，但是在计算Fib(3)的时候，已经计算了Fib(2)，不需要再计算一遍了，但是当计算Fib(3)完毕后，Fib(2)又重新被计算了一次。你可能说，多算个一两次没什么，但是你要知道，这仅仅是算Fib(4)的情况，如果计算Fib(40)，那么重复的计算将会有相当多。计算机是算不过来的。我们看到，每计算一个值时，如果不能有效地砍掉分支，那么效率将会变得非常低。
因此，我们对此作出改进。我们在计算的过程中，把中间能用到的结果都保存下来。这样，如果下次再碰到，就不必进行分支中的内容，而是直接提取数据就好了。这样做会节省很多的时间。
请阅读以下代码，并测试，体会其中的不同：

RUBY 代码复制

$solution_hash = {}
def fib(n)
  if n == 0 || n == 1
    return 1
  end
  # 如果已经算出结果，直接取出，否则再计算
  a = $solution_hash[n-1].nil? ? fib(n-1) : $solution_hash[n-1]
  # 计算完毕后，计算结果保存，以便下回使用
  $solution_hash[n-1] = a
  b = $solution_hash[n-2].nil? ? fib(n-2) : $solution_hash[n-2]
  $solution_hash[n-2] = b
  return a + b
end

$solution_hash = {}


def fib(n)


  if n == 0 || n == 1


    return 1


  end


  # 如果已经算出结果，直接取出，否则再计算


  a = $solution_hash[n-1].nil? ? fib(n-1) : $solution_hash[n-1]


  # 计算完毕后，计算结果保存，以便下回使用


  $solution_hash[n-1] = a


  b = $solution_hash[n-2].nil? ? fib(n-2) : $solution_hash[n-2]


  $solution_hash[n-2] = b


  return a + b


end

在这里，虽然$solution_hash被设定为全局变量，写法可能不够严谨。但是完全可以把它写成局部变量，这个请自行思考。
在我给出的水晶代码中，也有对应的剪枝部分，可以防止重复遍历。

好了，关于穷举我就写这么多，希望不要看得不耐烦了。其实我感觉论坛上多数人对算法不太感兴趣呢，何况是这么'low'的穷举和搜索。写这个回帖的时候，我还参考了我的算法教程，不过现在想想，貌似有点小题大做了。如果以后再遇到算法问题，欢迎在讨论区发帖，我尽量会参加讨论的。
（完）

汪汪

这里我也说一下我的大致想法，不知道可不可行。首先我们已经确定的是魔法阵的属性要求了，所以只要挑选水晶就可以了。
开始时，先算水晶数量，如果数量不够，自然不能构成。
首先，我们先从所有的水晶里搜索，删除所有不含任何魔法阵需要水晶的水晶，接着再计算一次数量。其次，再赋予水晶权重，符合魔法阵属性少的水晶越优先去处理。但是……这种穷举我不会写……是不是用一堆循环来实现啊？

Thylakoid

我觉得这个问题的关键在于确定“哪些水晶要被当成哪种属性来使用”，只要能确定这一点，就可以让同一种复数属性的水晶不能同时出现在不同属性的判断中。

PS：本来写了好多话，但无奈于思路太繁琐，最后还是决定不扯那么多了。简单来说，我是想把这个关键点的确定交给玩家。构建魔法阵的时候通过玩家的选择来确定被预定使用的水晶，方法是选择的同时进行配套的变量操作。一个麻烦之处是对所有属性（不论单属性还是复数属性）的分类，这是个很大的工程量，6个属性计算出的组合数之和为63（C61+C62+...+C66，即风水、暗火、光水、风暗火等等等等加在一起的总数），6个类别每类有32种不同的水晶（C50+C51+C52+...+C55，即风、风水、风火、风暗、风光、风水暗、风水光等等等等加在一起的总数），当然这是全组合，具体设计的时候未必这么多。另一个麻烦之处是在分类完成的基础上，对水晶预定的判断。若未预定，可自由判断，判断方法就是看它是否是当前属性类别hash表中的主键；若已预定，则判断预定的是否是当前的基础属性，不是则不能参与构建，是则可以参与构建，而这一切的标准都来自于对那每一种水晶所对应的变量操作。这个63个变量，操作时每个都要关联6个属性，以确定当前水晶是否被预定，以及被预定成哪种属性。复数属性这种设定让我想不出该怎么写循环，没规律。所以我只能想出这种类似于列举的手动分类法，是很机械的笨办法。不管有没有参考价值，姑且算是一条路子吧。

RyanBern

问题有点难度，LZ发了这么多天没有什么回复，现在发上来一个渣渣算法，希望能够抛砖引玉吧，引出来个更好的算法也是有可能的。

先说明一下这个算法的本质是穷举……不过呢，是有技巧的穷举（看来R君你的算法功力也不怎么样嘛，pia~）

（一）问题的提法
再次简单叙述一下LZ提出的问题，假设有n种不同的属性，编号为0~n-1，水晶的个数为m个，属性可以取其中的1个或者多个。现在给定一组数据a0，a1，...，a(n-1)，要求从给定的水晶中选出a(i)个属性为i的水晶，同一个水晶不能重复使用，问能否达到要求。
（二）数据结构
由于水晶属性持有的情况比较复杂，如果属性的个数为n，那么水晶的种类应该有2^n - 1种（不算无属性水晶）。那么该如何表示这些水晶呢？一种办法是构造种类的hash表，把每一种水晶的数量记下来，另一种办法是记录每一个水晶的属性信息。在这里，我选择第二种办法，下面就来看下如何记录每一个水晶的信息。
假设属性一共有n种，那么我们可以用n个0或者1来表示该水晶是否具有某属性。这些0和1排列起来便是一个二进制数。因此，我们利用0~2^n-1的整数便可以表示所有水晶的状态。
具体的，如果要判断某水晶是否含有某状态i，那么只需把1向左平移i位（实际采用相反方向平移法），然后和表示水晶属性的整数做按位与运算即可。

RUBY 代码复制

N = 5 # 属性数
class Crystal
  attr_reader :element
  def initialize(element = 0)
    @element = element
  end
  # 判断是否具有属性 i
  def element?(element_id)
    return (@element >> element_id) & 0x01 == 1
  end
  # 强制附加属性 i
  def attach_element(element_id)
    @element |= (1 << element_id)
  end
  # 强制解除属性 i
  def detach_element(element_id)
    @element &= ~(1 << element_id)
  end
end

N = 5 # 属性数


class Crystal


  attr_reader :element


  def initialize(element = 0)


    @element = element


  end


  # 判断是否具有属性 i


  def element?(element_id)


    return (@element >> element_id) & 0x01 == 1


  end


  # 强制附加属性 i


  def attach_element(element_id)


    @element |= (1 << element_id)


  end


  # 强制解除属性 i


  def detach_element(element_id)


    @element &= ~(1 << element_id)


  end


end

（三）算法
算法本质上是一个穷举法，但是中间做了一些优化。还是详细说一下吧。
我们先把m个水晶随便规定一个次序，例如利用我们在（二）中的数据结构来给定一个长度为m的Crystal数组。根据题目，还需要另外一个数组来记录现在需要各种属性的水晶多少个。现在我们从前往后考虑每个水晶该如何使用。
假设我们取出了一个水晶，那么我们看看它是何种属性的水晶，假设水晶的属性为[e1,e2,...,ek]，那么我分别考虑，如果把这个水晶当成属性为e(i)的水晶进行使用，那么我们还需要从剩下的水晶里面做何选择？做好这个决定之后，问题的规模会减小1，之后我们递归地进行处理就行了。

下面的脚本未经严格测试，只测了几组简单的数据。

为了方便理解，我在脚本里面打上详细的注释。这个方法利用了“剪枝技术”，来减小穷举带来的复杂度和不必要的计算。

此方法只能判断能不能达成目标，而不能具体说明如果能达成目标，那么具体的方式是怎么样的。

如果大家还有好的方法可以继续探讨。

RUBY 代码复制

#------------------------------
# 辅助方法，只使用序数大于等于 index 的水晶完成任务
# index : 水晶的起始编号
# need : 需要的水晶数，是一个 N 元数组
# crystals : 水晶的全序列，在这里被当做全局变量使用
# solutions : 存储中间结果的 Hash 表，是剪枝技术的基础，也是一个全局变量
#----------------------------------
def process_one_crystal(index, need, crystals, solutions)
  # 如果是从最后一个水晶后面的那个位置开始算（也就是一个水晶都不允许用）
  if index == crystals.size
    # 只有当一个水晶都不需要时才返回 true
    return need.all?{|n| n == 0}
  end
  # 取出当前位置的水晶
  crystal = crystals[index]
  # 记录该方法 process_one_crystal 的返回值
  flag = false
  # 对所有属性进行遍历
  (0...N).each do |i|
    # 如果这个水晶可以被当做此属性使用，并且需要此属性水晶的个数为正数
    if crystal.element?(i) && need[i] > 0
      # 假定将此水晶就当做这个属性为 i 的水晶使用，那么对于需求数应该减 1
      need[i] -= 1
      # 这个地方是难点
      # 将该位置上的水晶当做属性为 i 的水晶之后，相当于减小问题的规模
      # 如果问题规模减小后，解已经算过（问号'?'左边的表达式为 false）
      #    那么直接利用已经算过的解即可
      # 如果没有算过，则要递归计算规模减小 1 之后的问题
      flag = solutions[[index + 1, need]].nil? ? process_one_crystal(index + 1, need, crystals, solutions) : solutions[[index + 1, need]]
      # 由于 need 数组是公用的，假定完毕后要把 need[i] 加回去
      need[i] += 1
      # 如果已经找到解就直接跳出
      break if flag
    end
  end
  # 记录已经算过的值，以便将来重新利用
  solutions[[index, need]] = flag
  return flag
end
 
#----------------------------------------
# solve 方法，实际是对辅助方法的包装
# 由于 solutions 这种变量是相对全局的
# 所以不应该把它设置为全局变量
# crystals : 水晶的全序列
# need : 需要的水晶数，是一个 N 元数组
#----------------------------------------
def solve(crystals, need)
  # 初始化
  solutions = {}
  # 调用辅助方法
  process_one_crystal(0, need, crystals, solutions)
end

#------------------------------


# 辅助方法，只使用序数大于等于 index 的水晶完成任务


# index : 水晶的起始编号


# need : 需要的水晶数，是一个 N 元数组


# crystals : 水晶的全序列，在这里被当做全局变量使用


# solutions : 存储中间结果的 Hash 表，是剪枝技术的基础，也是一个全局变量


#----------------------------------


def process_one_crystal(index, need, crystals, solutions)


  # 如果是从最后一个水晶后面的那个位置开始算（也就是一个水晶都不允许用）


  if index == crystals.size


    # 只有当一个水晶都不需要时才返回 true


    return need.all?{|n| n == 0}


  end


  # 取出当前位置的水晶


  crystal = crystals[index]


  # 记录该方法 process_one_crystal 的返回值


  flag = false


  # 对所有属性进行遍历


  (0...N).each do |i|


    # 如果这个水晶可以被当做此属性使用，并且需要此属性水晶的个数为正数


    if crystal.element?(i) && need[i] > 0


      # 假定将此水晶就当做这个属性为 i 的水晶使用，那么对于需求数应该减 1


      need[i] -= 1


      # 这个地方是难点


      # 将该位置上的水晶当做属性为 i 的水晶之后，相当于减小问题的规模


      # 如果问题规模减小后，解已经算过（问号'?'左边的表达式为 false）


      #    那么直接利用已经算过的解即可


      # 如果没有算过，则要递归计算规模减小 1 之后的问题


      flag = solutions[[index + 1, need]].nil? ? process_one_crystal(index + 1, need, crystals, solutions) : solutions[[index + 1, need]]


      # 由于 need 数组是公用的，假定完毕后要把 need[i] 加回去


      need[i] += 1


      # 如果已经找到解就直接跳出


      break if flag


    end


  end


  # 记录已经算过的值，以便将来重新利用


  solutions[[index, need]] = flag


  return flag


end


 


#----------------------------------------


# solve 方法，实际是对辅助方法的包装


# 由于 solutions 这种变量是相对全局的


# 所以不应该把它设置为全局变量


# crystals : 水晶的全序列


# need : 需要的水晶数，是一个 N 元数组


#----------------------------------------


def solve(crystals, need)


  # 初始化


  solutions = {}


  # 调用辅助方法


  process_one_crystal(0, need, crystals, solutions)


end