快速启发式算法（n> 1000） [英] fast heuristic algorithm for n queens (n > 1000)

问题描述

我写了两个程序：

1. 将棋子放在棋盘上，没有任何威胁的回溯算法。但是对于大n非常重。


2. 在棋盘上组合n个皇后，而不会受到爬山算法的任何威胁。这个算法优于过去的解决方案，但它需要2分钟为300皇后，这次增加指数！

但我没有任何的想法这么快！我想要更快的算法。

But I didn't have any idea for doing that fast! I want algorithm for doing that faster .

我想要更快的方式解决问题，尽快为1000皇后。

I want faster manner to solve problem fast as possible for 1000 queens.

这是我的登山代码：

// N queen - Reset Repair Hill Climbing.cpp
// open-mind.ir

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
#include <time.h>
#include <iomanip>


using namespace std;

//print solution in console
void printBoardinTerminal(int *board, int len)
{
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            if (j == board[i])
            {
                cout << 1 << " ";
            }
            else
            {
                cout << 0 << " ";
            }
        }
        cout << endl;
    }
}

//print solution in File
void printBoardinFile(int *board, int len)
{
    ofstream fp("output.txt", ios::out);

    fp << "Answer for " << len << " queen: \n \n";

    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            fp << "----";
        }
        fp << "\n|";

        for (int j = 0; j < len; j++)
        {
            if (j == board[i])
            {
                fp << setw(4) << "* |" ;
            }
            else
            {
                fp << setw(4) << "  |";
            }
        }
        fp << "\n";
    }
}

//The number of queens couples who are threatened themself
int evaluate(int *board, int len)
{
    int score = 0;
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = i + 1; j < len; j++)
        {
            if (board[i] == board[j])
            {
                score++;
                continue;
            }
            if (board[i] - board[j] == i - j)
            {
                score++;
                continue;
            }
            if (board[i] - board[j] ==  j - i)
            {
                score++;
                continue;
            }
        }
    }
    return score;
}

//generate new state from current state 
int* generateBoard(int *board,int len)
{
    vector <int> choice;

    int temp;
    int score;
    int eval = evaluate(board, len);
    int k;

    int *boardOut;
    boardOut = new int [len];


    for (int i = 0; i < len; i++)
    {
            boardOut[i] = board[i];
    }

    for (int i = 0; i < len; i++)
    {
        choice.clear();

        choice.push_back(boardOut[i]);
        temp = boardOut[i];

        for (int j = 0; j < len; j++)
        {
            boardOut[i] = j;

            k = evaluate(boardOut, len);

            if (k == eval)
            {
                choice.push_back(j);
            }

            if (k < eval)
            {
                choice.clear();
                choice.push_back(j);
                eval = k;
            }
        }
        boardOut[i] = choice[rand() % choice.size()];
    }

    return boardOut;
}

//in this function , genarate new state by pervious function and if it has better value then replaces that by current state
bool findNextState(int *board, int len)
{
    int maineval = evaluate(board, len);

    int *tempBoard;

    tempBoard = generateBoard(board, len);

    if (evaluate(tempBoard, len) < maineval)
    {
        for (int p = 0; p < len; p++)
        {
            board[p] = tempBoard[p];
        }

        return  true;
    }

    return false;
}

// make random initial state , put one queen in each row
void initialRandomBoard(int * board, int len)
{
    bool access;
    int col;

    for (int i = 0; i < len; i++)
    {
        board[i] = rand() % len;
    }
}

//this function include a loop that call findNextState function , and do that until reach solution
//if findNextState function return NULL then we reset current state
void SolveNQueen(int len)
{
    cout << "The program is under process! wait!" << endl;

    int *board;
    board = new int[len];


    initialRandomBoard(board, len);

    while (evaluate(board, len) != 0)
    {
        if (!findNextState(board, len))
        {
            initialRandomBoard(board, len);
        }
    }


    //
    cout << endl << "Anwser for " << len << " queens: "<< endl << endl;
    printBoardinTerminal(board, len);
    printBoardinFile(board, len);
    //
}


int main()
{
    int n;
    srand(time(NULL));

    cout << "Enter  number \'N\', \'N\' indicate numbers of queens in \"N * N\" chess board: " << endl;
    cin >> n;

    if (n < 4)
    {
        cout << "\'n\' must be uper than 3!" << endl;
        exit(1);
    }

    SolveNQueen(n);

    cout << endl << "As well , you can see result in \"output.txt\"." << endl << endl;

    return 0;
}

推荐答案

有兴趣寻找一个有效解决方案。如果您需要查找所有解决方案，这将无济于事。

Note: This answer assumes you're interested in finding one valid solution. If you need to find all solutions, this won't help you.

人工智能：现代方法，第二版由Russell& Norvig在第5章：约束满足问题（第143页）中比较了各种任务的各种约束满足问题算法。 （最新版本是第三版，看起来约束满足问题现在是第6章。）

Artificial Intelligence: A Modern Approach, Second Edition by Russell & Norvig has a table in Chapter 5: Constraint Satisfaction Problems on page 143 comparing various constraint satisfaction problem algorithms for various tasks. (The latest edition is the Third Edition, and it looks like Constraint Satisfaction Problems is now Chapter 6.)

根据他们的结果，最小冲突局部搜索启发式得分最好在 n -Queens问题上测试的算法中，需要平均4K检查，与> 40,000K检查相比，用于回溯和前向检查。

According to their results, the minimum conflicts local search heuristic scored best out of the algorithms tested on the n-Queens problem, requiring an average of 4K checks compared with >40,000K checks for backtracking and forward-checking.

算法很简单：

• 选择初始）分配皇后


• ，当有威胁的皇后（或直到你厌倦了尝试...值得把它放在 loop以限制尝试次数）：
  
  
  
  • 选择随机受威胁的女王
  
  
  • 将所选女王移至最小化的平方冲突
  
  
  • select an initial (random or preselected) assignment of queens
  • while there are threatened queens (or until you get tired of trying... it's worthwhile to put this in a for loop to limit the number of tries):
    • select a random threatened queen
    • move the selected queen to the square that minimizes conflicts

    在最后一步，我假设每个女王到她的列，所以她只能更改列中的行。如果有几行最小化当前女王的冲突，你可以随机选择。

    In that last step, I'm assuming that each queen is constrained to her column, so she can only change rows within the column. If there are several rows that minimize conflicts for the current queen, you can choose randomly among them.

    就是这样。它是完全随机的，它的作品精美。

    That's it. It's completely random and it works beautifully.

    我在这里有一个注意到不记得我有多高n 当我实现这个算法，说我知道我有它超过100.我没有找到我的旧代码，但我决定投掷一些东西在一起。事实证明，这种方法比我记得的有效得多。以下是10个皇后的结果：

    I had a note here about not remembering how high I got n when I implemented this algorithm, saying I knew I had got it over 100. I didn't find my old code, but I decided to throw something together anyway. It turns out that this approach is far more effective than I remembered. Here are the results for 10 queens:

    Starting Configuration:
    14  0  2  13  12  17  10  14  14  2  9  8  11  10  6  16  0  7  10  8  
    Solution found
    Ending Configuration:
    17  2  6  12  19  5  0  14  16  7  9  3  1  15  11  18  4  13  8  10  
    Elapsed time (sec): 0.00167
    Number of moves: 227
    

    代码，这里是我得到不同的问题大小的大致时间：

    With no attempts at optimizing the code, here are the approximate timings I'm getting for different problem sizes:

    Queens      ~Time(sec)
    ======      ==========
      100           0.03
      200           0.12
      500           1.42
     1000           9.76
     2000          72.32
     5000        1062.39
    

    我只运行最后一个5000皇后一次， 18分钟比我预想的快。

    I only ran the last one for 5000 queens once, but to find a solution in under 18 minutes is quicker than I had expected.

    这篇关于快速启发式算法（n> 1000）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！