n个皇后的快速启发式算法(n> 1000)

Question

我写了两个程序:

1. 在国际象棋棋盘上放置n个皇后,没有任何回溯算法的威胁.但这对于大n来说非常沉重.最后你可以为100个皇后运行.
2. 在国际象棋棋盘上放置n个皇后,没有任何威胁的爬山算法.这个算法比过去的解决方案更好,但是300个皇后需要2分钟,而且这个时间呈指数增长!

但我没有任何想法快速做到这一点!我想要算法更快地做到这一点.

我希望更快的方式尽快解决1000个皇后的问题.

这是我的登山代码:

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

Answer 1

注意:这个答案假设您有兴趣找到一个有效的解决方案.如果您需要找到所有解决方案,这对您没有帮助.

人工智能:一种现代方法,第二版由Russell和Norvig在第5章中提供了一个表:约束满足问题(第143页),比较各种约束满足问题算法的各种任务.(最新版本是第三版,看起来Constraint Satisfaction Problems现在是第6章.)

根据他们的结果,在n -Queens问题上测试的算法中,本地搜索启发式的最小冲突得分最高,需要平均4K检查与> 40,000K检查进行回溯和前向检查.

算法很简单:

• 选择一个初始(随机或预选)的皇后分配
• 虽然有受威胁的皇后(或者直到你厌倦了尝试......将它放在for循环中以限制尝试次数是值得的):
  • 选择一个随机威胁女王
  • 将选定的女王移动到最小化冲突的方块

在最后一步中,我假设每个女王都被约束到她的列,所以她只能更改列中的行.如果有多行可以最大限度地减少当前女王的冲突,您可以在其中随机选择.

而已.它完全随机,效果很好.

编辑:

我这里有一个备注不记得我是怎么高了ň当我实现了这个算法,他说我知道我已经超过100个.我没有找到我的旧代码得到它,但我决定扔东西在一起,反正.事实证明,这种方法远比我记忆中的有效.以下是10个皇后的结果:

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

没有尝试优化代码,这里是我得到的不同问题大小的大致时间:

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

我只运行了最后一次为5000个皇后,但是在18分钟内找到一个解决方案比我预期的要快.