Пример алгоритма 8-Queens?

Question

Кто-нибудь знает хорошие/краткие примеры алгоритмов для ? Я сделал поиск в Интернете и не нашел хорошего примера.

Answer 1

От Wikipedia:

Этой эвристика решает п матки для любых пп ≥ 4 или п = 1:

1. Разделить п на 12. Помните остаток (п 8 для восемь королевская головоломка).
2. Напишите список четных чисел от 2 до n по порядку.
3. Если остаток 3 или 9, переместите 2 в конец списка.
4. Прилагайте нечетные числа от 1 до n по порядку, , но если остаток равен 8, то пары (т. Е. 3, 1, 7, 5, 11, 9, ...).
5. Если остаток равен 2, переключите места 1 и 3, затем переместите 5 в в конец списка.
6. Если остаток составляет 3 или 9, переместите 1 и 3 в в конец списка.
7. Поместите первого столбца Королева в строке с первым номером в списке, поместите второй столбец Королева в строке со вторым номером в списке, т.д.

Answer 2

Точка проблемы 8-queens часто просто иллюстрирует силу поиска в сочетании с обрезкой. Вы можете в значительной степени выполнять поиск грубой силы в поисковом пространстве, но исключать любое частичное решение, когда оно нарушает ограничения решения (т. Е. Одна королева проверяет другое).

Просто используя эту обрезку, 8-фермы легко разрешимы.

Если вам нужны более эффективные решения, которые были бы полезными, например, 100 или 1000 королевы, это совсем другая история, и вы можете посмотреть на материал в Википедии. Но для 8-царей достаточно грубой силы и обрезки. (т. е. выполнить глубину первого поиска в поисковом пространстве, исключая любой промежуточный узел, который включает проверенную королеву).

Answer 3

разместить ферзя на строке г:

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) является безопасным, если для каждой строки [г + 1 .. 8]:

• (строка, с) не отмечен
• с - (строка - г) < 1 или (строка, с - (строка - г)) не отмечен
• с + (строки - г)> 8 или (строка, C + (строка - r)) не обозначен

Answer 4

Вот простая реализация 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. Есть много вопросов уже о stackoverflow о том, как писать 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-й элемент массива обозначает позицию строки i-й королевы, помещенной в i-й столбец (все индексы основаны на 0). Таким образом, первое решение выглядит, как это на борту:

[0,2,4,1,3] 

Q · · · · 
· · · Q · 
· Q · · · 
· · · · Q 
· · Q · · 

Я оставлю его в качестве упражнения, чтобы понять, почему isSafe работает, и как напечатать макет платы, и как реализовать быстрее, но более сложные рекурсивные алгоритмы ,

Счастливое обучение.

Answer 5

Вот простой 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; 

     } 
    } 

Answer 6

В EWD316 Дейкстра выводит решение проблемы восемь ферзей достаточно формально. Попробуйте, вам может понравиться!

Answer 7

// 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); 
       } 
      }  
     } 
    } 
} 

Answer 8

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); 
} 

Answer 9

В TheWalnut.io есть визуализация N-Queens: считается проблемой удовлетворения ограничений и использует алгоритм локального поиска (с мин- конфликты эвристические), чтобы решить эту проблему. The code (in Javascript) is also there.

визуализации для конкретного случая N == 8, но он может быть изменен на любой N.

Answer 10

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(); 
    } 

Answer 11

Это простое решение в 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; 
} 

https://yadiragarnica.wordpress.com/2015/10/15/n-queens-problem/ От

Answer 12

Я написал detailed, commented example of the N Queens problem in Python, и положил его на GitHub. Взглянуть!