8-queensの良い/簡潔なアルゴリズムの例を知っている人はいますか? Web 検索を行いましたが、適切な例が見つかりませんでした。
23191 次
14 に答える
16
これは単純な再帰アルゴリズムの単純な Java 実装です。それは有益であるべきです。
public class NQueens {
final static int N = 4;
static int[] position = new int[N];
public static void main(String[] args) {
solve(0);
}
static boolean isSafe(int k, int p) {
// for (int i = 1; i <= k; i++) {
// int other = position[k - i];
// if (other == p || other == p - i || other == p + i) {
// return false;
// }
// }
return true;
}
static void solve(int k) {
if (k == N) {
System.out.println(java.util.Arrays.toString(position));
} else {
for (char p = 0; p < N; p++) {
if (isSafe(k, p)) {
position[k] = p;
solve(k+1);
}
}
}
}
}
isSafe現在、コメント行が含まれていることに注意してください。それは意図的に行われます。これらの行をコメント化すると、プログラムは再帰的なN-tuple ジェネレーターになり、各値は0(包括的) とN(排他的) の間になります。つまり、プログラムはそのままで次の出力を生成します。
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
:
:
[3, 3, 3, 0]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]
このNタプルの生成は、NQueens 問題の具体的なサブ問題です。入れ子になったループの書き方については、スタックオーバーフローで既に多くの質問がありますが、何がN何であるかがわからない場合ですN。この問題に一時的に立ち止まって、最初isSafeに単純にコメントアウトしてその解決策を理解しreturn true;、最初に再帰が何をするかを感じることは有益だと思います。
この再帰的なタプル ジェネレーターが機能することに慣れたら、これらの行のコメントを外すだけで、シンプルでナイーブですが、機能する NQueens ソルバーが得られます。N=5および行のコメントをisSafe解除すると、プログラムは次の出力を生成します。
[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]
各行は 5 クイーン問題の解です。配列の- 番目の要素は、 - 番目の列に配置された - 番目のクイーンiの行位置を示します (すべてのインデックスは 0 ベースです)。したがって、最初のソリューションはボード上で次のようになります。ii
[0,2,4,1,3]
Q · · · ·
· · · Q ·
· Q · · ·
· · · · Q
· · Q · ·
なぜisSafe機能するのか、ボード レイアウトを印刷する方法、およびより高速ではあるがより複雑な再帰アルゴリズムを実装する方法を理解するための演習として残します。
楽しい学習。
于 2010-05-24T04:03:36.093 に答える
3
多くの場合、8 クイーン問題の要点は、剪定と組み合わせた検索の力を説明することです。検索空間のブルート フォース検索をほとんど実行できますが、ソリューションの制約に違反する場合 (つまり、1 つのクイーンが別のクイーンをチェックする) は、部分的なソリューションを削除します。
この枝刈りを使うだけで、8-queens は簡単に解けます。
たとえば、100 個または 1000 個の女王に役立つより効率的なソリューションが必要な場合は、別の話であり、ウィキペディアの内容を見ることができます。しかし、8 クイーンの場合は、ブルート フォースとプルーニングで十分です。(つまり、探索空間の深さ優先探索を行い、チェック中のクイーンを含む中間ノードを排除します)。
于 2010-05-24T02:51:48.930 に答える
3
行 r にクイーンを配置するには:
if r = 0 then you're done -- return ok
for each c [1 .. 8]:
if (r,c) is safe:
mark (r,c)
if you can place queen on row r-1 then return ok
unmark (r,c) (if you're here, this c won't work)
return not ok (if you're here, no c generated a solution)
(r,c) は、各行 [r+1 .. 8] に対して次の場合に安全です。
- (行、c) はマークされていません
- c - (行 - r) < 1 または (行、c - (行 - r)) はマークされていません
- c + (row - r) > 8 または (row, c + (row - r)) はマークされていません
于 2010-05-24T02:58:56.973 に答える
2
// Demonstration of the 8-Queens problem
// This handout shows interactively how the 8-Queens problem can be solved
// using recursion and backtracking (with exhaustive search with pruning).
// As far as this code goes, some improvements can definitely be made,
// especially with regard to the interface and the flexibility for the
// user. However, it does an adequate job of showing the steps involved in
// solving the 8-Queens problem.
import javax.swing.*;
import java.awt.*;
import java.awt.geom.*;
import java.awt.event.*;
public class JRQueens extends JFrame implements Runnable
{
public ChessSquare [][] squares;
public boolean [] saferow; // is the row empty? true or false
public boolean [] safeleftdiag; // is the left (from upper right to lower left)
// diagonal unthreatened? true or false
public boolean [] saferightdiag; // is the right (from upper left to lower right)
// diagonal unthreatened? true or false
private ShapePanel drawPanel; // panel for the board to be drawn -- see details
// in class definition below
private JLabel info; // informative label
private JButton runDemo; // button to allow interaction
private Thread runThread; // thread to allow "motion"
private int delay; // delay between moves
private PauseClass pauser; // class to allow execution to pause in between
// solutions -- see details in definition below
private boolean paused; // is execution paused? true or false
private int sol, calls;
public JRQueens(int delta)
{
super("Interactive 8 Queens Problem");
delay = delta;
drawPanel = new ShapePanel(450, 450);
runDemo = new JButton("See Solutions"); // Set up button
ButtonHandler bhandler = new ButtonHandler();
runDemo.addActionListener(bhandler);
info = new JLabel("The 8 Queens Problem", (int) CENTER_ALIGNMENT);
Container c = getContentPane(); // Set up layout
c.add(drawPanel, BorderLayout.CENTER);
c.add(info, BorderLayout.NORTH);
c.add(runDemo, BorderLayout.SOUTH);
squares = new ChessSquare[8][8]; // initialize variables
saferow = new boolean[8];
safeleftdiag = new boolean[15];
saferightdiag = new boolean[15];
int size = 50;
int offset = 25;
for (int row = 0; row < 8; row++)
{
saferow[row] = true; // all rows are safe
for (int col = 0; col < 8; col++)
{
squares[row][col] = new ChessSquare(offset + col*size,
offset + row*size,
size, size);
}
}
for (int i = 0; i < 15; i++)
{ // initialize all diagonals to safe
safeleftdiag[i] = true;
saferightdiag[i] = true;
}
sol = 0;
calls = 0;
runThread = null;
setSize(475, 525);
setVisible(true);
}
// Is the current location safe? We check the row and both diagonals.
// The column does not have to be checked since our algorithm proceeds in
// a column by column manner.
public boolean safe(int row, int col)
{
return (saferow[row] && safeleftdiag[row+col] &&
saferightdiag[row-col+7]);
}
// This recursive method does most of the work to solve the problem. Note
// that it is called for each column tried in the board, but, due to
// backtracking, will overall be called many many times. Each call is from
// the point of view of the current column, col.
public void trycol(int col)
{
calls++; // increment number of calls made
for (int row = 0; row < 8; row++) // try all rows if necessary
{
// This test is what does the "pruning" of the execution tree --
// if the location is not safe we do not bother to make a recursive
// call from that position, saving overall many thousands of calls.
// See notes from class for details.
if (safe(row, col))
{
// if the current position is free from a threat, put a queen
// there and mark the row and diags as unsafe
saferow[row] = false;
safeleftdiag[row+col] = false;
saferightdiag[row-col+7] = false;
(squares[row][col]).occupy();
repaint();
if (col == 7) // queen safely on every column, announce
{ // solution and pause execution
sol++;
info.setText("Solution " + sol + " Found After " + calls + " Calls");
runDemo.setText("Click to Continue");
runDemo.setEnabled(true);
pauser.pause();
}
else
{
// Still more columns left to fill, so delay a bit and then
// try the next column recursively
try
{
Thread.sleep(delay);
}
catch (InterruptedException e)
{
System.out.println("Thread error B");
}
trycol(col+1); // try to put a queen onto the next column
}
saferow[row] = true; // remove the queen from
safeleftdiag[row+col] = true; // the current row and
saferightdiag[row-col+7] = true; // unset the threats. The
(squares[row][col]).remove(); // loop will then try the
// next row down
}
}
// Once all rows have been tried, the method finishes, and execution
// backtracks to the previous call.
}
// This method executes implicitly when the Thread is started. Note that
// its main activity is the call trycol(0), which starts the recursive
// algorithm on its way.
public void run()
{
paused = false;
pauser = new PauseClass();
trycol(0);
repaint();
info.setText("Program Completed: " + sol + " Solutions, "
+ calls + " Calls, "
+ (8*calls) + " iterations ");
}
public static void main(String [] args)
{
// Use the delay value entered by the user, or use 100 if no
// value is entered.
int delay;
if (args != null && args.length >= 1)
delay = Integer.parseInt(args[0]);
else
delay = 100;
JRQueens win = new JRQueens(delay);
win.addWindowListener(
new WindowAdapter()
{
public void windowClosing(WindowEvent e)
{ System.exit(0); }
}
);
}
// This class is used to enable the execution to pause between
// solutions. The Java details of this class have to do with monitors
// and synchronized Threads and are beyond the scope of the CS 1501
// course. However, if you are interested in learning more about these
// Java features, feel free to look them up in the Java API.
private class PauseClass
{
public synchronized void pause()
{
paused = true;
try
{
wait();
}
catch (InterruptedException e)
{
System.out.println("Pause Problem");
}
}
public synchronized void unpause()
{
paused = false;
notify();
}
}
// Class to handle button. For more on the Java details, see
// the API online.
private class ButtonHandler implements ActionListener
{
public void actionPerformed(ActionEvent e)
{
if (e.getSource() == runDemo)
{
if (!paused)
{
runDemo.setEnabled(false);
info.setText("Searching for Solutions");
runThread = new Thread(JRQueens.this);
runThread.start();
}
else
{
runDemo.setEnabled(false);
info.setText("Searching for Solutions");
pauser.unpause();
}
repaint();
}
}
}
// Inner class to represent a square on the board. This class extends
// Rectangle2D.Double, which can be drawn graphically by the draw() method
// of the Graphics2D class. The main additions I have made in the subclass
// are the occupied variable and the drawing of the Q if the space is
// occupied.
private class ChessSquare extends Rectangle2D.Double
{
private boolean occupied;
public ChessSquare(double x1, double y1, double wid, double hei)
{
super(x1, y1, wid, hei);
occupied = false;
}
public void draw(Graphics2D g2d)
{
g2d.draw(this);
int x = (int) this.getX();
int y = (int) this.getY();
int sz = (int) this.getWidth();
if (occupied)
{
g2d.setFont(new Font("Serif", Font.BOLD, 36));
g2d.drawString("Q", x+10, y+sz-10);
}
}
public void occupy()
{
occupied = true;
}
public void remove()
{
occupied = false;
}
public boolean isOccupied()
{
return occupied;
}
}
// Class that allows the board to be rendered in a nice way.
// See that Java API or a good book on Java graphics for more
// details about this class.
private class ShapePanel extends JPanel
{
private int prefwid, prefht;
public ShapePanel (int pwid, int pht)
{
prefwid = pwid;
prefht = pht;
}
public Dimension getPreferredSize()
{
return new Dimension(prefwid, prefht);
}
public void paintComponent (Graphics g)
{
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
(squares[i][j]).draw(g2d);
}
}
}
}
}
于 2010-10-11T14:22:21.273 に答える
1
public class NQueensSolver
{
private readonly List<int[]> _solutions = new List<int[]>();
private readonly int[] _current;
public int N { get; private set; }
public NQueensSolver(int n)
{
N = n;
_current = new int[N];
}
public IList<int[]> FindAllFormations()
{
PopulateFormations(0);
return _solutions;
}
private void PopulateFormations(int row)
{
if (row == N)
{
_solutions.Add(_current.ToArray());
return;
}
for (int col = 0; col <= N-1; col++)
{
if (Threatened(row, col))
continue;
_current[row] = col;
PopulateFormations(row + 1);
}
}
private bool Threatened(int row, int col)
{
for (int i = 0; i <= row - 1; i++)
if (_current[i] == col || row - i == Math.Abs(col - _current[i]))
return true;
return false;
}
}
いくつかのテスト:
[TestMethod]
public void TestNQueens()
{
Assert.AreEqual(1, new NQueensSolver(1).FindAllFormations().Count);
Assert.AreEqual(0, new NQueensSolver(2).FindAllFormations().Count);
Assert.AreEqual(0, new NQueensSolver(3).FindAllFormations().Count);
Assert.AreEqual(2, new NQueensSolver(4).FindAllFormations().Count);
Assert.AreEqual(10, new NQueensSolver(5).FindAllFormations().Count);
Assert.AreEqual(4, new NQueensSolver(6).FindAllFormations().Count);
Assert.AreEqual(40, new NQueensSolver(7).FindAllFormations().Count);
Assert.AreEqual(92, new NQueensSolver(8).FindAllFormations().Count);
Assert.AreEqual(352, new NQueensSolver(9).FindAllFormations().Count);
Assert.AreEqual(724, new NQueensSolver(10).FindAllFormations().Count);
}
于 2012-12-08T22:48:07.293 に答える
1
これは C# での簡単なソリューションです。
//----N Queens ----
public static bool NQueens(bool[,] board, int x)
{
for (int y = 0; y < board.GetLength(1); y++)
{
if (IsAllowed(board, x, y))
{
board[x, y] = true;
if (x == board.GetLength(0) - 1 || NQueens(board, x + 1))
{
return true;
}
board[x, y] = false;
}
}
return false;
}
//verify diagonals, column and row from i=0 to x because from x to down it dont put anything
private static bool IsAllowed(bool[,] board, int x, int y)
{
for (int i = 0; i <= x; i++)
{
if (board[i, y] || (i <= y && board[x - i, y - i]) || (y + i < board.GetLength(0) && board[x - i, y + i]))
{
return false;
}
}
return true;
}
于 2015-10-30T16:17:35.957 に答える
1
これは簡単なC＃ソリューションです。うまくいくと思います
public static class EightQueens
{
static int[] board = new int[8];
static int MaxRows = 8, MaxCols = 8;
public static int[] GetPosition()
{
if (GetPosition(0)) return board;
else return null;
}
public static bool IsCollision(int row, int col)
{
for (int i = 0; i < col; i++)
{
if (board[i] == row) return true; // Same Row
if ((board[i] + col - i == row) || (board[i] - col + i == row))
return true;
}
return false;
}
public static bool GetPosition(int col)
{
if (col == MaxCols) return true;
for (int row = 0; row < MaxRows; row++)
if (!IsCollision(row, col))
{
board[col] = row;
if (GetPosition(col + 1)) return true;
}
return false;
}
}
于 2010-05-24T04:35:23.203 に答える
1
ウィキペディアから：
このヒューリスティックは、任意の nn ≥ 4 または n = 1 に対して n 個のクイーンを解決します。
- n を 12 で割ります。余りを覚えておいてください (8 クイーン パズルの場合、n は 8 です)。
- 2からnまでの偶数のリストを順番に書きなさい。
- 残りが 3 または 9 の場合、2 をリストの最後に移動します。
- 1 から n までの奇数を順番に追加しますが、残りが 8 の場合はペアを切り替えます (つまり、3、1、7、5、11、9、…)。
- 余りが 2 の場合、1 と 3 の場所を入れ替えて、5 をリストの最後に移動します。
- 余りが 3 または 9 の場合、1 と 3 をリストの最後に移動します。
- 1 列目のクイーンをリストの最初の数字の行に配置し、2 列目のクイーンをリストの 2 番目の数字の行に配置します。
于 2010-05-24T02:42:36.170 に答える
1
EWD316で、ダイクストラはエイト クイーン問題の解決策を形式的に導き出しています。試してみてください。気に入るかもしれません。
于 2010-07-27T19:05:44.523 に答える
0
private const int Size = 8;
private static readonly bool[,] chessboard = new bool[Size, Size];
//The Rows are 8, numbered from 0 to 7.
//The Columns are 8, numbered from 0 to 7.
//The left diagonals are 15, numbered from -7 to 7. following formula : leftDiag = col - row.
//The right diagonals are 15, numbered from 0 to 14 by the formula: rightDiag = col + row.
private static readonly HashSet<int> AttackedRows = new HashSet<int>();
private static readonly HashSet<int> AttackedCols = new HashSet<int>();
private static readonly HashSet<int> AttackedLeftDiagonals = new HashSet<int>();
private static readonly HashSet<int> AttackedRightDiagonals = new HashSet<int>();
private static int solutionsFound;
private static void Main(string[] args)
{
PutQueens(0);
Console.WriteLine(solutionsFound);
}
private static void PutQueens(int row)
{
if (row == Size)
{
PrintBoard();
solutionsFound++;
}
else
{
for (var col = 0; col < Size; col++)
{
if (CanPlaceQueen(row, col))
{
MarkAllAttackedPositons(row, col);
PutQueens(row + 1);
UnMarkAllAttackedPositons(row, col);
}
}
}
}
private static void UnMarkAllAttackedPositons(int row, int col)
{
AttackedRows.Remove(row);
AttackedCols.Remove(col);
AttackedLeftDiagonals.Remove(col - row);
AttackedRightDiagonals.Remove(col + row);
chessboard[row, col] = false;
}
private static void MarkAllAttackedPositons(int row, int col)
{
AttackedRows.Add(row);
AttackedCols.Add(col);
AttackedLeftDiagonals.Add(col - row);
AttackedRightDiagonals.Add(col + row);
chessboard[row, col] = true;
}
private static bool CanPlaceQueen(int row, int col)
{
var positionOccuppied = AttackedCols.Contains(col) || AttackedRows.Contains(row)
|| AttackedLeftDiagonals.Contains(col - row)
|| AttackedRightDiagonals.Contains(col + row);
return !positionOccuppied;
}
private static void PrintBoard()
{
for (var row = 0; row < Size; row++)
{
for (var col = 0; col < Size; col++)
{
Console.Write(chessboard[row, col] ? "Q " : "- ");
}
Console.WriteLine();
}
Console.WriteLine();
}
于 2015-09-28T19:51:33.307 に答える
0
TheWalnut.ioには、N-Queens の視覚化があります。これは、制約充足問題と見なされ、ローカル検索アルゴリズム (min-conflicts ヒューリスティックを使用) を使用して解決します。コード (Javascript) もあります。
視覚化は N == 8 の特定のケース用ですが、任意の N に変更できます。
于 2015-07-28T17:39:23.060 に答える