找出所有可能位置的算法

Question

我需要一种算法来找出棋盘中一组棋子的所有可能位置。就像找到 N 件棋子位置的所有可能组合。

例如在像笛卡尔坐标系一样编号的棋盘中，任何棋子都会在一个位置

(x,y) where 1 <= x <= 8 and 1 <= y <= 8

我想要一个算法，可以计算例如 3 个棋子在棋盘上所有可能的位置。但我不知道如何按任何顺序获取它们。我可以得到单个棋子的所有可能位置，但我不知道如何将它们与更多棋子混合。

for(int i = 0; i<= 8; i++){
    for(int j = 0; j<= 8; j++){
        System.out.println("Position: x:"+i+", y:"+j);
    }
}

我怎样才能找到一个好的算法来找到棋盘上棋子的所有可能位置？

谢谢。

Answer 1

你有 8x8 的棋盘，所以总共有 64 个方 block 。
填充包含这 64 个正方形的列表 [让它成为 list]，并找到所有可能性 recursively : 每一步都会“猜测”一个点，并调用递归调用来寻找其他点。

伪代码:

choose(list,numPieces,sol):
   if (sol.length == numPieces): //base clause: print the possible solution
       print sol
       return
   for each point in list:
       sol.append(point) //append the point to the end of sol
       list.remove(point)
       choose(list,numPieces,sol) //recursive call
       list.add(point)  //clean up environment before next recursive call
       sol.removeLast()

使用 choose(list,numPieces,[]) 调用，其中 list 是包含 64 个元素的预填充列表，numPieces 是您要放置的棋子。

注意:此解决方案假设片段不相同，因此 [(1,2),(2,1)] 和 [(2,1 ),(1,2)] 都是很好的不同解决方案。

编辑:
简单说一下复杂性，因为有 (n^2)!/(n^2-k)! 可能的解决方案来解决您的问题 - 而您正在寻找所有这些解决方案，任何算法都会遭受指数运行时间的困扰，因此尝试仅用 10 个片段来调用它，将需要大约 400 年的时间
[上述表示法中，n为棋盘的宽和长，k为棋子的个数]