チェス盤にあるピースのグループの可能な位置をすべて見つけるアルゴリズムが必要です。数N個の位置の可能な組み合わせをすべて見つけるのと同じように。どの部分が私は3個の全ての可能な位置のために、例えば計算できるアルゴリズムを取得したい位置可能なすべての位置を見つけるアルゴリズム
(x,y) where 1 <= x <= 8 and 1 <= y <= 8
であろうデカルト座標系のように番号チェス盤、例えば
ボード内の作品。しかし、私はどのようにしてそれらをどのような順序で得ることができないのか分かりません。私は単一の作品のすべての可能な位置を得ることができますが、私はより多くの作品とそれらを混在させる方法を知らない。
どのようにチェス盤の中でピースの位置を見つけるために良いアルゴリズムを得ることができますか？
ありがとうございました。
あなたは8x8ボードなので合計64個の正方形です。
これらの64 sqauresを含むリストに[list]を入力し、可能性のすべてを見つけてくださいrecursively：各ステップは1つのポイントを「推測」し、再帰呼び出しを呼び出して他のポイントを検索します。
擬似コード：
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()
はlistは64個の要素が事前にリストされ、そしてnumPiecesはあなたが配置しようとしている作品であるchoose(list,numPieces,[])で起動します。
注：この解決策は、がではないと仮定しているので、[(1,2),(2,1)]と[(2,1),(1,2)]はどちらも良い解決策です。
EDIT：
複雑さについての言葉だけ、あなたの問題のため(n^2)!/(n^2-k)!可能な解決策があるので - あなたはそれらのすべてを探している、任意のアルゴリズムはそうでそれを起動しようとすると、指数関数実行時に苦しむだろうわずか10個〜400年はかかるだろう
[上記の表記では、nは、ボードの幅と長さで、かつkはピースの数である]
あなたはすべてのpossiblitiesを生成するために、再帰的なアルゴリズムを使用することができます。
void combine(String instr, StringBuffer outstr, int index)
{
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
System.out.println(outstr);
combine(instr, outstr, i + 1);
outstr.deleteCharAt(outstr.length() - 1);
}
}
combine（ "abc"、new StringBuffer（）、0）;
私が理解しているように、いくつかのフィギュアは、空のボード上に届くフィギュアの潜在的な位置を妨げる可能性があると考えてください。私はそれが最も難しい部分だと思う。 したがって、いくつかの単一の頂点（初期ボード状態）から到達するいくつかの頂点セット（ボード状態のセット）を構築する必要があります。
私の心に来る最初のアルゴリズム：
事前条件：円を形成するために、何らかの方法で
アクション
これは一種の息-最初と深さ優先探索
位置に関する制限を混在さ？またはあなたはnポジションのすべての可能な選択をしたいですか？ – Nick
法的ポジションでなければなりませんか（例えば、白人の騎士、黒人の騎士、最初の2つのランクの駒なしなど） – DNA
@Nick制限は全くありません。私はちょうどそれがより簡単にするためにチェスの例を追加しましたが、私は要素の可能なすべての分布を見つけるために任意の "マップ"です）numbrerのアイテムの可能なすべての構成が必要です。 – Juanillo