Anybody kn开发者_如何学编程ows good/concise algorithm examples for 8-queens? I did a Web search and did not find any good example.
Here's a simple Java implementation of the naive recursive algorithm; it should be instructive.
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);
}
}
}
}
}
Note that isSafe contains commented lines right now; it's done on purpose. With these lines commented, the program becomes a recursive N-tuple generator, where each value is between 0 (inclusive) and N (exclusive). That is, the program as is generates the following output:
[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]
This N-tuple generation is a concrete sub-problem of the NQueens problem. There are many questions already on stackoverflow on how to write an N-nested loops, when you don't know what N is. I feel that it's instructional to make a temporary stop at this problem and first understand its solution, with isSafe commented out to simply return true;, to first get a feel of what the recursion does.
Once you're comfortable that this recursive tuple generator works, simply uncomment those lines, and you will get a simple, naive, but working, NQueens solver. With N=5 and isSafe lines uncommented, the program now generates the following output:
[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]
Each line is a solution to the 5-queens problem. The i-th element of the array denotes the row position of the i-th queen placed on the i-th column (all indices are 0-based). So, the first solution looks like this on the board:
[0,2,4,1,3]
Q · · · ·
· · · Q ·
· Q · · ·
· · · · Q
· · Q · ·
I will leave it as an exercise to understand why isSafe works, and how to print the board layout, and how to implement faster but more complicated recursive algorithms.
Happy learning.
The point of the 8-queens problem is often just to illustrate the power of search combined with pruning. You can pretty much do a brute force search of the search space, but eliminate any partial solution when it violates the constraints of the solution (i.e. one queen checks another).
Just using this pruning, 8-queens is easily solvable.
If you want more efficient solutions that would be useful for e.g. 100 or 1000 queens, that's a different story and you can look at the stuff in wikipedia. But for 8-queens, brute force and pruning are enough. (i.e. do depth first search of the search space, eliminating any intermediate node that includes a queen in check).
to place queen on row 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) is safe if, for each row [r+1 .. 8]:
- (row,c) is not marked
- c - (row - r) < 1 or (row, c - (row - r)) is not marked
- c + (row - r) > 8 or (row, c + (row - r)) is not marked
// 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);
}
}
}
}
}
From Wikipedia:
This heuristic solves n queens for any n n ≥ 4 or n = 1:
- Divide n by 12. Remember the remainder (n is 8 for the eight queens puzzle).
- Write a list of the even numbers from 2 to n in order.
- If the remainder is 3 or 9, move 2 to the end of the list.
- Append the odd numbers from 1 to n in order, but, if the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
- If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
- If the remainder is 3 or 9, move 1 and 3 to the end of the list.
- Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.
Here is a simple C# Solution I think it works
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;
}
}
In EWD316, Dijkstra derives a solution to the Eight Queens problem rather formally. Try it, you might like it!
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;
}
}
Some tests:
[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);
}
This is a simple solution in 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;
}
In TheWalnut.io there's a visualization of the N-Queens: it is considered a constraint satisfaction problem and uses a local-search algorithm (with a min-conflicts heuristic) to solve it. The code (in Javascript) is also there.
The visualization is for particular case of N == 8 but it can be changed to any N.
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();
}
I wrote up a detailed, commented example of the N Queens problem in Python, and put it up on GitHub. Take a look!
I solved this deploying C++, see the right moves on terminal.
You might see more details on my queen.cpp
function for placing chess
void amo::Queen::place(int probing, int n) {
if (n != row || n != col ) {
if (chess != nullptr) {
for (int i=0;i<row;i++) delete *(chess+i);
delete chess;
}
row = n;
col = n;
chess = new int*[n];
for (int i=0;i<n;i++) {
*(chess+i) = new int[col];
for (int j=0; j<col; j++)
*(*(chess+i)+j) = 100*(i+1)+j;
}
}
if (probing >= n) {
ans += 1;
std::cout << GREEN <<"[Queen::place()]: returns when met the pass-the-end of probing which means deduced one of answer:" << ans << WHITE << std::endl;
for (std::vector<int>::iterator it=queens.begin(); it!=std::next(queens.begin(), n); it++)
collect(moves, 1, std::distance(queens.begin(), it), *it);
traverse(moves);
moves.clear();
return;
}
for (int pruning=0; pruning<col; pruning++) {
track++;
//traverse(probing, pruning);
//if (probing==n-1 && pruning==col-1) std::cout << RED <<"[Queen::place()]: track:" << track << WHITE << std::endl; //final track=4^4+4^3+4^2+4^1=340 if n=4 or track=3^3+3^2+3^1=39 if n=3
if (!check(probing, pruning)) {
//if (false) { //watching all moves
//std::cout << "[Queen::place()]: going to prune" << WHITE << std::endl;
/**
* 'prunes' when met one of dead ends of this probing at this pruning
*/
continue;
}
else { //found one of rights of this probing at this pruning and digs into the one more deeper
//std::cout << "[Queen::place()]: going to probe" << WHITE << std::endl;
if (queens.size() < n) queens.resize(n);
queens.at(probing) = pruning;
/**
* 'probes' one more deeper by making one more call stack returning back here as backtracking and proceeding to another pruning
*/
place(probing+1, n);
}
}
/**
* 'backtracks'
*/
return;
}
and function for checking if moves are solutions
bool amo::Queen::check(int row, int column) {
if (row == 0) {
//std::cout << CYAN << "okay chess[" << row <<"][" << column << "]" << WHITE << std::endl;
return true;
}
for (std::vector<int>::iterator it=queens.begin(); it!=std::next(queens.begin(), row); it++) {
int placed_row = std::distance(queens.begin(), it);
int placed_column = queens.at(placed_row);
if (placed_column == column) {
//std::cout << MAGENTA << "not across, queen[" << placed_row << "][" << placed_column << "] and chess[" << row <<"][" << column << "]" << WHITE << std::endl;
return false;
}
if (std::abs(placed_column-column) == std::abs(placed_row-row)) {
//std::cout << MAGENTA << "not diagonal, queen[" << placed_row << "][" << placed_column << "] and chess[" << row <<"][" << column << "]" << WHITE << std::endl;
return false;
}
}
//std::cout << CYAN << "okay chess[" << row <<"][" << column << "]" << WHITE << std::endl;
return true;
}
SQL:
with tx1 as (select 1 as k union all select t2.k + 1 from tx1 as t2 where t2.k < 8)
select *
from tx1 as x1
join tx1 as x2 on
x2.k <> x1.k and
x2.k <> x1.k + 1 and x2.k <> x1.k - 1
join tx1 as x3 on
x3.k <> x1.k and x3.k <> x2.k and
x3.k <> x2.k + 1 and x3.k <> x2.k - 1 and
x3.k <> x1.k + 2 and x3.k <> x1.k - 2
join tx1 as x4 on
x4.k <> x1.k and x4.k <> x2.k and x4.k <> x3.k and
x4.k <> x3.k + 1 and x4.k <> x3.k - 1 and
x4.k <> x2.k + 2 and x4.k <> x2.k - 2 and
x4.k <> x1.k + 3 and x4.k <> x1.k - 3
join tx1 as x5 on
x5.k <> x1.k and x5.k <> x2.k and x5.k <> x3.k and x5.k <> x4.k and
x5.k <> x4.k + 1 and x5.k <> x4.k - 1 and
x5.k <> x3.k + 2 and x5.k <> x3.k - 2 and
x5.k <> x2.k + 3 and x5.k <> x2.k - 3 and
x5.k <> x1.k + 4 and x5.k <> x1.k - 4
join tx1 as x6 on
x6.k <> x1.k and x6.k <> x2.k and x6.k <> x3.k and x6.k <> x4.k and x6.k <> x5.k and
x6.k <> x5.k + 1 and x6.k <> x5.k - 1 and
x6.k <> x4.k + 2 and x6.k <> x4.k - 2 and
x6.k <> x3.k + 3 and x6.k <> x3.k - 3 and
x6.k <> x2.k + 4 and x6.k <> x2.k - 4 and
x6.k <> x1.k + 5 and x6.k <> x1.k - 5
join tx1 as x7 on
x7.k <> x1.k and x7.k <> x2.k and x7.k <> x3.k and x7.k <> x4.k and x7.k <> x5.k and x7.k <> x6.k and
x7.k <> x6.k + 1 and x7.k <> x6.k - 1 and
x7.k <> x5.k + 2 and x7.k <> x5.k - 2 and
x7.k <> x4.k + 3 and x7.k <> x4.k - 3 and
x7.k <> x3.k + 4 and x7.k <> x3.k - 4 and
x7.k <> x2.k + 5 and x7.k <> x2.k - 5 and
x7.k <> x1.k + 6 and x7.k <> x1.k - 6
join tx1 as x8 on
x8.k <> x1.k and x8.k <> x2.k and x8.k <> x3.k and x8.k <> x4.k and x8.k <> x5.k and x8.k <> x6.k and x8.k <> x7.k and
x8.k <> x7.k + 1 and x8.k <> x7.k - 1 and
x8.k <> x6.k + 2 and x8.k <> x6.k - 2 and
x8.k <> x5.k + 3 and x8.k <> x5.k - 3 and
x8.k <> x4.k + 4 and x8.k <> x4.k - 4 and
x8.k <> x3.k + 5 and x8.k <> x3.k - 5 and
x8.k <> x2.k + 6 and x8.k <> x2.k - 6 and
x8.k <> x1.k + 7 and x8.k <> x1.k - 7
order by 1,2,3,4,5,6,7,8
![Interactive visualization of a graph in python [closed]](https://www.devze.com/res/2023/04-10/09/92d32fe8c0d22fb96bd6f6e8b7d1f457.gif)
加载中,请稍侯......
精彩评论