N皇后问题的算法方法比较

Question

我想评估各种解决N皇后问题的方法的性能比较。主要是基于AI metaheuristics的算法，如模拟退火，禁忌搜索和遗传算法等与精确方法（如回溯）相比较。有没有可供学习的代码？许多现实世界的优化问题，例如它考虑精确方法和metaheuristics之间的合作方案。

Answer 1

我不得不在几年前的大学里为一个班的Java编写n皇后解答。我不确定你正在寻找什么类型的源代码，但如果这里有任何帮助，那么这个程序的代码。它没有以任何方式进行真正的优化，只是一个非常简单的递归算法。我在大学的第一个学期写了这篇文章，所以原谅了初学者的错误:-)我把大部分块注释掉了，但是希望你能用我留下的注释来理解它。如果你想要一些专业的源代码而不是也许做一个谷歌搜索？我知道维基百科有一些体面的文章和伪代码。希望这可以帮助！

import java.util.Scanner; 
public class QueensSolver 
{ 
public static void main(String args[]) 
{ 
    System.out.println("Please enter the size of the chessboard: "); 
    Scanner stdin = new Scanner(System.in); 
    int sizeOfBoard = stdin.nextInt(); 
    //Create the board to the given size. 
    char[][] board = new char[sizeOfBoard][sizeOfBoard]; 

    //fill board with hyphens 
    for(int row=0; row<sizeOfBoard; row++) 
    { 
     for(int col=0; col<sizeOfBoard; col++) 
     { 
      board[row][col] = '-'; 
     } 
    } 

    //Call the method which attempts to solve the problem 
    if(solve(sizeOfBoard, board, 0)) 
    { //if true, we know that the board array contains a solution 
     printBoard(sizeOfBoard, board); 
    } 
    else 
    { //if false, we know that no solutions exist on this size of board 
     System.out.println("No solutions are possible with this board size."); 
    } 
} 

public static boolean solve(int sizeOfBoard, char[][] board, int row) 
{ 
    //If all rows have been filled, we have a solution 
    if(row>=sizeOfBoard) 
    { 
     return true; 
    } 
    //For each column(space) on the given row 
    for(int col=0; col<sizeOfBoard; col++) 
    { 
     //If placing a queen in this column(space) does not cause a conflict 
     if(!checkConflict(sizeOfBoard, board, row, col)) 
     { 
      //place a queen here 
      board[row][col]='Q'; 
      //then call this same function on the next row 
      boolean success = solve(sizeOfBoard, board, row+1); 
      //if every function in this recursive path returns true 
      if(success) 
      { 
       //then we return true also 
       return true; 
      } 
      //If there is no possible solution with this queen placement, 
      //then we replace the queen with an empty and attempt 
      //to place a queen in the next column(space). 
      else 
      { 
       board[row][col]='-'; 
      } 
     } 
    } 
    return false; 
} 

public static boolean checkConflict(int sizeOfBoard, char[][] board, int rowCheck, int colCheck) 
{ 
    //Check for queens placed directly above this position 
    for(int row = rowCheck-1; row>=0; row--) 
    { 
     if(board[row][colCheck]=='Q') 
     { 
      return true; 
     } 
    } 

    //Check for queens placed on the diagonal 
    //above and to the right of this position 
    int col = colCheck+1; 
    for(int row = rowCheck-1; row>=0; row--) 
    { 

     if(col>=sizeOfBoard) 
     { 
      break; 
     } 
     if(board[row][col]=='Q') 
     { 
      return true; 
     } 
     col++; 
    } 

    //Check for queens placed on the diagonal 
    //above and to the left of this position 
    col = colCheck-1; 
    for(int row = rowCheck-1; row>=0; row--) 
    { 

     if(col<0) 
     { 
      break; 
     } 

     if(board[row][col]=='Q') 
     { 
      return true; 
     } 
     col--; 
    } 
    //We know that no conflicts are caused by this position, so return false 
    return false; 
} 

public static void printBoard(int sizeOfBoard, char[][] board) 
{ 
    for(int row=0; row<sizeOfBoard; row++) 
    { 
     for(int col=0; col<sizeOfBoard; col++) 
     { 
      System.out.print(board[row][col]); 
     } 
     System.out.print("\n"); 
    } 
} 
} 

Answer 2

我真的不明白你的问题（你想知道算法的理论呢？所以，你想看到的代码吗？），但我愿意分享我的代码改编自野外。这是蟒蛇，它非常酷。我改变它使用迭代器，奇迹般地，它仍然有效。

# I can't really claim much credit for this implementation. 
# I found this on the web and I converted it to use python generators. 
# Adapted from: 
#  http://en.wikibooks.org/wiki/Algorithm_implementation/Miscellaneous/N-Queens 

def queensproblem(solution, rows, columns): 
    def add_one_queen(new_row, columns, solution): 
     for new_column in range(columns): 
      if not conflict(new_row, new_column, solution): 
       yield new_column 

    def conflict(new_row, new_column, solution): 
     return any(solution[row]  == new_column or 
        solution[row] + row == new_column + new_row or 
        solution[row] - row == new_column - new_row 
        for row in range(new_row)) 

    if len(solution) == rows: 
     yield solution 
    else : 
     for row in range(len(solution), rows): 
      for col in add_one_queen(row, columns, solution): 
       for x in queensproblem(solution + [col], rows, columns): 
        yield x 
      else: 
       break 

if __name__ == '__main__': 
    for i,solution in enumerate(queensproblem([], 8, 8)): 
     print i, solution 

Answer 3

Python标准库文件test/test_generators.py中存在一个很好的方法。检查女王课程。

如果您的计算机中没有安装Python，则可以在线浏览文件here。

Answer 4

解答者Drools对您而言可能是件有趣的事。特别是chapter 1 of the documentation。

Answer 5

这不是最快的方案实现可能，但它非常简洁。我确实独立了，但我怀疑它是独一无二的。它在PLT方案中，因此需要更改一些函数名称以使其在R6RS中运行。解决方案和每个解决方案的列表均以cons为基础构建，因此它们被颠倒过来。最后的反转和贴图重新排列所有内容，并向解决方案添加行以获得漂亮的输出。大多数语言具有折叠式功能，请参阅：
http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

#lang scheme/base 
(define (N-Queens N) 

    (define (attacks? delta-row column solution) 
    (and (not (null? solution)) 
     (or (= delta-row (abs (- column (car solution)))) 
      (attacks? (add1 delta-row) column (cdr solution))))) 

    (define (next-queen safe-columns solution solutions) 
    (if (null? safe-columns) 
     (cons solution solutions) 
     (let move-queen ((columns safe-columns) (new-solutions solutions)) 
      (if (null? columns) new-solutions 
       (move-queen 
       (cdr columns) 
       (if (attacks? 1 (car columns) solution) new-solutions 
        (next-queen (remq (car columns) safe-columns) 
           (cons (car columns) solution) 
           new-solutions))))))) 

    (unless (exact-positive-integer? N) 
    (raise-type-error 'N-Queens "exact-positive-integer" N)) 
    (let ((rows (build-list N (λ (row) (add1 row))))) 
    (reverse (map (λ (columns) (map cons rows (reverse columns))) 
        (next-queen (build-list N (λ (i) (add1 i))) null null)))))