ホーム
製品
Red Hat Process Automation Manager
7.13
Red Hat Process Automation Manager 使用ガイド
31.6. N クィーン

31.6. N クィーン

n サイズのチェスボードに、他のクィーンに取られないクィーンに n 個のクィーンを置きます。最も一般的な n クィーンパズルは、n = 8 の 8 個のクィーンパズルです。

制約:

n 列および n 行のチェスボードを使用します。
チェスボードに n 個のクィーンを置きます。
クィーンが他のクィーンに取られないように配置します。クィーンは、同じ水平線上、垂直線上、対角線上にある他のクィーンを取ることができます。

このドキュメントでは、4 つのクイーンパズルを主な例として多用しています。

以下が提案された解です。

図31.1 4 個のクィーンパズルの誤った解

上記の解は、A1 と B0 (および B0 と D0) のクィーンがお互いに駒を取れるので間違っています。B0 のクィーンをどかせば "他のクィーンに取られないようにする" という制約は順守できますが、"n 個のクィーンを置く" という制約に違反します。

以下は正しい解です。

図31.2 クィーン 4 個のパズルの正しい解

すべての制約が満たされているので、これが正解です。

n クィーンパズルでは、正解が複数存在する場合が多々あります。特定の n に対して考えられる解を見つけるのではなく、特定の n に対する正しい解を 1 つ導き出すことにフォーカスします。

問題の規模

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

Copy to Clipboard

Toggle word wrap

n クィーンは、初心者用のサンプルとして実装されているため、最適化はされていません。それにもかかわらず、クィーンが 64 個になっても簡単に処理できます。何点か変更を加えると、クィーンが 5000 個以上になっても簡単に対応できることが立証されています。

31.6.1. N クィーンのドメインモデル
リンクのコピー

この例では、4 つのクィーンの問題を解決するドメインモデルを使用します。

ドメインモデルの作成

適切なドメインモデルを使用すると、プランニングの問題をより簡単に理解し、解決することができます。

以下は、n クィーンの例のドメインモデルです。

public class Column {

    private int index;

    // ... getters and setters
}

public class Column {

    private int index;

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

public class Row {

    private int index;

    // ... getters and setters
}

public class Row {

    private int index;

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

探索空間の計算

Queen インスタンスには Column (例: 0 は列 A、1 は列 B) および Row (例: 0 は行 0、1 は行 1) が含まれます。

列と行をもとに、昇順の対角線、および降順の対角線を計算することができます。

列と行のインデックスは、チェスボードの左上隅から数えています。

public class NQueens {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

public class NQueens {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

Copy to Clipboard

Toggle word wrap

解の求め方
1 つの NQueens インスタンスには Queen インスタンスのリストが含まれています。これが Solution 実装として提供され、Solver が解決して読み出します。

たとえば、4 クイーンのサンプルでは、NQueens の getN() メソッドが常に 4 を返します。

図31.3 クィーン 4 個の解

Expand

表31.2 ドメインモデルの解の詳細
	columnIndex	rowIndex	ascendingDiagonalIndex (columnIndex + rowIndex)	descendingDiagonalIndex (columnIndex - rowIndex)
A1	0	1	1 ()**	-1
B0	1	*0 ()**	1 ()**	1
C2	2	2	4	0
D0	3	*0 ()**	3	3

(*) や (**) のように、クィーン 2 つが同じ行、列、対角線を共有する場合は、2 つの駒が互いを取ることができます。

31.6. N クィーン

31.6.1. N クィーンのドメインモデル
リンクのコピー

詳細情報

試用、購入および販売

コミュニティー

Red Hat ドキュメントについて

多様性を受け入れるオープンソースの強化

会社概要

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links

31.6. N クィーン

31.6.1. N クィーンのドメインモデルリンクのコピーリンクがクリップボードにコピーされました!

詳細情報

試用、購入および販売

コミュニティー

Red Hat ドキュメントについて

多様性を受け入れるオープンソースの強化

会社概要

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links

31.6.1. N クィーンのドメインモデル
リンクのコピー