Алгоритм Н*королева Н


Я просто играл вокруг С Н проблемы королевы означает любезны n ферзей на N*настольная сыр такой, что никто не может убить друг друга. Я попробовал простой алгоритм, который использует поиск с возвратом.Программа работает нормально до 29 ферзей, но после 29 это просто идет дальше и дальше..я не в состоянии решить ее из-за некоторых логических ошибок или из-за слишком много вычислений нужно было сделать выше 29*29..

Я оклейки мой код здесь.Это консольное приложение для Win32. Если кто-то может сказать мне, какая логическая ошибка или какой-то способ оптимизации его..это будет полезно для меня..

Код..

    // Queen_Game.cpp : Defines the entry point for the console application.
    #include <iostream>
    using namespace std;
    class chess_block
    {
    public:
        bool bQueen;
        chess_block()
        {
            bQueen=false;
        }
    };
    bool IsSafeToPutQueen(int nRow, int nCol,chess_block **Chess_Board,int n )
    {
        // We need to check for three directions upper left diagonal, lower left diagonal, and left horizontally;
        int nTempColLeft=nCol-1; int nTempBelowRow=nRow+1;int nTempAboveRow=nRow-1;
        bool bSafe=true;
        //
        while(nTempColLeft>=0 || nTempBelowRow<n || nTempAboveRow>=0)
        {
            if( ((nTempAboveRow>=0)&&(nTempColLeft>=0)&&(Chess_Board[nTempAboveRow][nTempColLeft].bQueen==true))    /*Left Upper Diagonal*/
                ||((nTempBelowRow<n)&&(nTempColLeft>=0)&&(Chess_Board[nTempBelowRow][nTempColLeft].bQueen==true))/*Left Lower Diagonal*/
                ||((nTempColLeft>=0)&&(Chess_Board[nRow][nTempColLeft].bQueen==true)))      /*Left Block*/
            {

                bSafe=false;
                break;

            }
            else
            {

                nTempColLeft--;
                nTempAboveRow--;
                nTempBelowRow++;
            }
        }
        return bSafe;
    }

    chess_block **PrepareTheChessBoard(int n)//Allocate memory for n*n blocks
    {
        //chess_block **Chess_Board= (chess_block **)malloc(n*sizeof(chess_block *));

        chess_block **Chess_Board= new chess_block *[n];

        for(int i=0;i<n;i++)
        {

            Chess_Board[i]=new chess_block[n];

        }
        for(int nColumn=0;nColumn<n;nColumn++)
        {
            for(int nRow=0;nRow<n; nRow++)
            {

                Chess_Board[nRow][nColumn].bQueen=false;
            }
        }
        return Chess_Board;
    }
    void DestroyTheChessBoard(chess_block **Chess_Board,int n)
    {
        for(int i=0;i<n;i++)
        {
            delete [](Chess_Board[i]);

        }
        delete [](Chess_Board);
    }

    void PrintPositionsOfQueens(chess_block **Chess_Board,int n)
    {

        for(int nColumn=0;nColumn<n;nColumn++)
        {
            for(int nRow=0;nRow<n; nRow++)
            {
                if(Chess_Board[nRow][nColumn].bQueen==true)//Put The Queen Here
                {

                    cout<<"Column No.:   "<<nColumn   <<"               "<<"Row Number:   "<<nRow<<"\n";
                }

            }
        }    

    }
    void ArrangeQueensOnBoard(chess_block **Chess_Board,int n)
    {
        bool bBackTrack=false;
        int nRow=0;
        for(int nColumn=0;nColumn<n;nColumn++)
        {
            for(nRow=0;nRow<n; nRow++)
            {

                if(IsSafeToPutQueen(nRow,nColumn,Chess_Board,n))
                {
                    if(bBackTrack && Chess_Board[nRow][nColumn].bQueen==true)
                    {
                        Chess_Board[nRow][nColumn].bQueen=false;
                        bBackTrack=false;
                        continue;
                    }
                    else if(!bBackTrack)
                    {
                        Chess_Board[nRow][nColumn].bQueen=true;
                        break;//Now Move to Next Col
                    }
                }
            }
            if(nRow ==n && Chess_Board[n-1][nColumn].bQueen==false)//means we need to backtrack
            {
                nColumn--;
                if(nColumn<0)
                {
                    cout<<"THis combination can't place the queen ";
                    break;
                }
                nColumn--;
                bBackTrack=true;
            }

        }

    }
    int _tmain(int argc, _TCHAR* argv[])
    {
        while(1)//Don't be offended for this while loop it is only for keeping the command prompt window on the screen always
        {
            int n=0;
            cout<<"Enter the value of N"<<"\n";
            cin>>n;
            chess_block **Chess_Board=NULL;
            Chess_Board=PrepareTheChessBoard(n);
            if(Chess_Board == NULL)
            {
                return 0;

            }
            ArrangeQueensOnBoard(Chess_Board,n);
            PrintPositionsOfQueens(Chess_Board,n);
            DestroyTheChessBoard(Chess_Board,n);
            Chess_Board=NULL;
        } 

        return 0;
    }


9866
5
задан 10 декабря 2011 в 08:12 Источник Поделиться
Комментарии
6 ответов

Вы не ждать достаточно долго. Код работает.

Ваш стиль программирования очень сильно ориентированы на "С". Вы должны работать ваш путь через хорошую книгу по c++. Но даже если вы не, есть много вы могли бы сделать, чтобы улучшить его даже в стиле, как написано.


  • Идиоматически, вы не должны проверить логические переменные в отношении истинного и ложного. Это законно, и наличие собственного логического типа значит, это не опасно, как это было в C. Но вместо if (условие == true)в вы можете просто сказать, если (условие), и вместо if (условие == ложные) вы можете сказать, если (!состоянии) или если (не состояния). "Не" ключевое слово только в C++ и реже, но есть и другие многословные термины, как "и" вместо &&...а также "или" вместо || с самого начала. Они стандартные и я их найду более приятный, и легче увидеть, как я могу редактировать код в пропорциональный шрифт. Если вы используете bool и истина/ложь у вас уже есть на c++ бай-ин, почему бы не использовать их?

  • Венгерская нотация префиксы ужасно неправильно. Их правильное применение зависит от создания новых абстрактных типов...не робототехнических кодирование низкого уровня реализации видов. Поэтому вместо того, чтобы nRowMax инт; инт nColumnFirst; вы хотели что-то сказать, как тип int строк; тип int столбец; а затем объявить строку rowMax; столбец columnFirst; находите ли вы, что ходульные против "значения maxrow" и "firstColumn" или короткие имена переменных, такие как "Р" и "С" - это вопрос личных предпочтений...и можно дискутировать, что с людьми весь день. Но никто не должен ставить н перед каждой переменной, это глупо и не правильно Венгрии с самого начала.

(Примечание: Я предпочитаю такие вещи, как rowMax до значения maxrow. Если я окажусь в рутину с одной переменной строки, я могу начать называть его просто "подряд" и тогда я беспокоюсь только, чтобы дать ему дифференцировать суффиксы основано ли это необходимо по контексту. Этот процесс более простой трансформации: сказать, что я начинаю с Ряд ряд и то, что работает для некоторое время, пока я понял, что мне нужен "дистанционный" и "местные" подряд. Я просто добавляю "местных" и rowLocal и не нужно recase как localRow. Что-то насчет сдачи это "rowness" первая привлекает меня эстетически...вроде как, я предпочитаю путь испанского ставит существительные в прилагательные.)


  • В соответствии с предыдущим пунктом, не предварив логические переменные с б. То, что я хотел сделать, это иметь логические переменные начинаются со стеблями, такие как "есть", "есть", "было", "следует" и т. д. Это приводит к английском-как читаемость условную логику, как если (shouldDeleteFile) { ... } я думаю, что в Qt API для руководства есть некоторые интересные общие соображения на этот и другие вопросы: http://doc.qt.nokia.com/qq/qq13-apis.html#theartofnaming

  • У вас конструктор для вашего chess_block , которые устанавливают bQueen значение false. Но ваш код все равно пришлось перебрать массивы динамически выделяемые для установки bQueen значение false. Это только одна из многих причин, чтобы использовать новый и удалить в C++ (и их различными формами новый[] и удалить[]).

  • Не скрыть свои алгоритмы. Например, вы использовали цикл for, который всегда увеличивается счетчик, а затем попробовать и "отменить" эффект грядущего приращения путем вычитания. Есть и другие виды петель...while и Do/а. Если вы не всегда хотите увеличить счетчик (и иногда хотят вычесть из него), то сделать эту логику более ясным путем отделения части приращения.

  • При размещении кода на StackOverflow, попытаться сделать это, так что нет горизонтальной полосы прокрутки. Это очень неприятно читать в интернете. Если это возможно, изолировать вашу проблему образцов, которые могут поместиться без вертикальной полосы прокрутки.

Есть много больше вы можете сделать. C++ предоставляет векторов, которые являются более безопасными и проще работать, чем динамические аллокации массивов. Если вы начинаете инкапсуляция внутри классной доски, то вы можете передать объекты вокруг и они будут нести их размер с ними. Зная c++ - хорошая вещь. А вот пример очень простой изменения я говорю о без хирургического вмешательства переделать код:

#include <iostream>

using namespace std;

struct Square {
bool hasQueen;
Square () {
hasQueen = false;
}
};

void PrintChessBoard(Square** board, int n) {
for (int row = 0; row < n; row++) {
for (int column = 0; column < n; column++) {
if (board[row][column].hasQueen) {
cout << "Q";
} else {
cout << ".";
}
}
cout << "\n";
}
}

bool IsSafeToPutQueen(int row, int column, Square** board, int n) {
int columnLeft = column - 1;
int rowBelow = row + 1;
int rowAbove = row - 1;

while ((columnLeft >= 0) or (rowBelow < n) or (rowAbove >= 0)) {
bool leftUpperDiagonalAttack = (rowAbove >= 0)
and (columnLeft >= 0)
and board[rowAbove][columnLeft].hasQueen;

bool leftLowerDiagonalAttack = (rowBelow < n)
and (columnLeft >= 0)
and board[rowBelow][columnLeft].hasQueen;

bool leftAttack = (columnLeft >= 0)
and board[row][columnLeft].hasQueen;

if (leftUpperDiagonalAttack or leftLowerDiagonalAttack or leftAttack) {
return false;
} else {
columnLeft--;
rowAbove--;
rowBelow++;
}
}
return true;
}

bool CanSolveWithBackTrack(Square** board, int n) {
bool inBacktrack = false;
int column = 0;
while (column < n) {
bool wasQueenPlaced = false;
for (int row = 0; row < n; row++) {
if (IsSafeToPutQueen(row, column, board, n)) {
if (inBacktrack) {
if (board[row][column].hasQueen) {
board[row][column].hasQueen = false;
inBacktrack = false;
// now Move to Next Row
continue;
}
} else {
board[row][column].hasQueen = true;
wasQueenPlaced = true;
break;
}
}
}

if ((not wasQueenPlaced) and (not board[n-1][column].hasQueen)) {
column--;
if (column < 0) {
// can't solve it
return false;
}
inBacktrack = true;
} else {
column++;
}
}
return true;
}

int main(int argc, char* argv[]) {
// Read board size from user
int n = 0;
cout << "Enter the value of N" << "\n";
cin >> n;

// Dynamically allocate array of arrays for chess board
Square** board = new Square*[n];
for (int i = 0; i < n; i++) {
board[i] = new Square[n];
}

// Print out the board if solvable, or an error message
if (CanSolveWithBackTrack(board, n)) {
cout << "This combination CAN place the queens!" << "\n";
PrintChessBoard(board, n);
} else {
cout << "This combination CAN'T place the queens." << "\n";
}

// Free chess board arrays...MUST use array form "delete[]"!
for (int i = 0; i < n; i++) {
delete[] board[i];
}
delete[] board;

return 0;
}

10
ответ дан 10 декабря 2011 в 11:12 Источник Поделиться

Второй для(инт nColumn... является уменьшение nColumn внутри цикла. Что открывает перед вами бесконечные циклы. Если вы распечатываете в состав совета по должности пробуются в этот цикл, вы должны быть в состоянии видеть повторения и разберемся.

6
ответ дан 10 декабря 2011 в 09:12 Источник Поделиться

Я заметил, но вот мои наблюдения вашего кода:

Это более эффективно представлять совет как массив из N целых чисел, где b[i] - это расположение королевы в столбце I-й. Это, естественно, исключает случай, когда есть две дамы в том же столбце.

Поиск с возвратом-это часто лучше всего делать, используя рекурсивный алгоритм, в противном случае вы в конечном итоге кодирования свой собственный стек для записи истории поиска.

Плохое правописание, и огромные функции делают его трудным для других, чтобы понять ваш код. Возможно, они делают их тяжелее для вас, чтобы отладить? Меньше функций позволяет тестировать части кода по отдельности, когда вы подозреваете, что что-то сломалось.

Палка для функций из C или C++ и попробовать, чтобы избежать смешивания двух (функции malloc в C, конструкторы struct, тип bool и Cin/cout вы сможете из C++). Старайтесь избегать кода, характерные для Windows, когда это не обязательно, и вместо того, чтобы придерживаться стандарта C или C++ (имя _tmain, файл stdafx).

5
ответ дан 10 декабря 2011 в 09:12 Источник Поделиться

Я не уверен, что это то, что вы ищете, но есть явное решение задачи n ферзей :) это из-за бумаги, я не могу совсем, кажется, не найти.

Во всяком случае, здесь-это реализация четкого решения. Он возвращает список целых чисел, представляющих позиции ферзей (по одному на каждую строку):

std::vector<int> solve(int n) {
std::vector<int> result;
if (n == 1) {
result.push_back(1);
return result;
}
if (n < 4) {
// Impossible, return empty vector.
return result;
}

if (n % 2 == 0) {
// Explicit solution according to paper.
if (n % 6 == 2) {
for (int j = 1; j <= n/2; j++) {
result.push_back(1 + ((2 * (j-1) + n/2 - 1) % n));
}
for (int j = n/2; j > 0; j--) {
result.push_back(n - ((2*(j-1) + n/2 - 1) % n));
}
}
else {
for (int j = 1; j <= n/2; j++) {
result.push_back(2 * j);
}
for (int j = 1; j <= n/2; j++) {
result.push_back(2 * j - 1);
}
}
}
else {
// If odd, place in corner and solve even.
result = solve(n - 1);
result.push_back(n);
}

return result;
}

2
ответ дан 10 декабря 2011 в 09:12 Источник Поделиться

Я могу подтвердить ваши программы делают работу за 30, но займет много времени. Пожалуйста, будьте терпеливы в ожидании результатов. (Я не проверял достоверность результата).

Сложность такого алгоритма является экспоненциальный (или, может быть, более показательной). Это означает, что затраченное время будет легко достичь терпимости пользователя.

К тому же предложения по другим, в C++, то лучше использовать новую , а не Танос, который будет вызывать конструктор. И вы можете использовать СТД::вектор вместо сырого указателя.

кстати, у меня/вывода, такие как печать на экране будет занимать много времени (гораздо больше, чем ваш реальный алгоритм в коде). Не печатать, что часто даже при отладке.

2
ответ дан 10 декабря 2011 в 10:12 Источник Поделиться

N ферзей есть о(п) детерминированные решения, который был опубликован в 1969 г. издание журнала математика Хоффман, Loessi, и Мур. Вот ссылка на апплет (www.apl.jhu.edu/~hall/java/NQueens.java), который реализует более поздняя версия такой же подход. В 2001 году я был студентом в одном из моих классов решит проблему 10,000,000 Королев через минуту на ПК той эпохи (300мгц Процессор Pentium).

0
ответ дан 11 декабря 2011 в 09:12 Источник Поделиться