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

Question

我想评估解决N皇后问题的各种方法的性能比较与精确方法（如回溯）相比，主要是基于人工智能的元启发式算法，如模拟退火、禁忌搜索和遗传算法等。有学习的代码吗许多现实世界中的优化问题都考虑精确方法和元启发式方法之间的合作方案。

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