12 доминирующих рыцарей головоломка (backtracking)

Ответ 1

Как указано @gnasher729, попытка разместить всех 12 рыцарей будет очень неэффективной, поэтому мы можем попытаться разместить 6 рыцарей на white blocks вместо этого, но используя этот подход, мы можем атаковать максимум 30 black blocks out of 32.

Итак, из вышеизложенного можно взять 2 подхода:

1) Мы можем исправить 2 рыцаря на оставшихся двух черных блоках, а затем попытаться поместить оставшихся 4 рыцарей на оставшиеся 30 черных блоков, теперь обратите внимание, что нам нужно атаковать оставшиеся 26 белых блоков.

@gnasher729 сказал, что мы могли бы отразить решение, но я не смог придумать логику фиксации 2-х мест, а затем найти зеркало, потому что на него нападали только 30 блоков, а рыцарей не было 14, то все 32 блока были бы атакованы, и найти зеркало, возможно, было бы возможно.

2) Во-вторых, нужно было перевести остальных 6 рыцарей всякий раз, когда мы найдем решение для первых 6 рыцарей, атаковавших более 26 black blocks, которые я реализовал, но это еще не нашло решения.

Так как @n.m. сказал, что мы можем попытаться найти решения из центра, чтобы уменьшить пространство для поиска, поэтому я попытался найти решение, разместив рыцарей в центральном квадрате 6 X 6 и, кроме того, искал решения, когда 30 из 32 черных блоков были атакован вместо 26, и, наконец, смог найти 2 решения проблемы, которые были симметричными, может быть больше решений, доступных для решения с лучшим подходом.

Код в С++:

#include <iostream>
#include <ctime>

using namespace std;

#define N 8

int board[N][N], mark[N][N];

void placeOnBoard(int i, int j){
    int count = 0;
    if(mark[i][j] == 0) mark[i][j] = 1;
    if(i+2 < N && j+1 < N && mark[i+2][j+1] == 0) mark[i+2][j+1] = 1;
    if(i+2 < N && j-1 >= 0 && mark[i+2][j-1] == 0) mark[i+2][j-1] = 1;
    if(i-2 >= 0 && j+1 < N && mark[i-2][j+1] == 0) mark[i-2][j+1] = 1;
    if(i-2 >= 0 && j-1 >= 0 && mark[i-2][j-1] == 0) mark[i-2][j-1] = 1;

    if(j+2 < N && i+1 < N && mark[i+1][j+2] == 0) mark[i+1][j+2] = 1;
    if(j+2 < N && i-1 >= 0 && mark[i-1][j+2] == 0) mark[i-1][j+2] = 1;
    if(j-2 >= 0 && i+1 < N && mark[i+1][j-2] == 0) mark[i+1][j-2] = 1;
    if(j-2 >= 0 && i-1 >= 0 && mark[i-1][j-2] == 0) mark[i-1][j-2] = 1;
}

void printBoard(){
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            if(board[i][j] != 0) cout << "K ";
            else cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void backtrackBlack(int knightNum, int currX, int currY){
    if(knightNum == 7){
        int count = 0;
        for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) mark[i][j] = 0;
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++) if(board[i][j] != 0) placeOnBoard(i, j);
        }
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++) if(mark[i][j] != 0) count++;
        }
        if(count == 64) printBoard();
        return;
    }
    if(currX == N-1 && currY == N) return;
    int newX, newY;     //new place in the board to move to
    if(currY == N) newY = 0,newX = currX + 1;
    else newY = currY + 1,newX = currX;

    //do not place the current knight at (currX, currY)
    backtrackBlack(knightNum, newX, newY);
    //try to place the current knight at (currX, currY)
    if((currX + currY) % 2 == 1 && currX > 0 && currX < N-1 && currY > 0 && currY < N-1){
        board[currX][currY] = knightNum;
        backtrackBlack(knightNum+1, newX, newY);
        board[currX][currY] = 0;
    }
}

void backtrackWhite(int knightNum, int currX, int currY){
    if(knightNum == 7){
        int count = 0;
        for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) mark[i][j] = 0;
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++) if(board[i][j] != 0) placeOnBoard(i, j);
        }
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++) if(mark[i][j] != 0) count++;
        }
        if(count >= 32){
            backtrackBlack(1, 0, 0);
            //printBoard();
        }
        return;
    }
    if(currX == N-1 && currY == N) return;
    int newX, newY;     //new place in the board to move to
    if(currY == N) newY = 0,newX = currX + 1;
    else newY = currY + 1,newX = currX;

    //do not place the current knight at (currX, currY)
    backtrackWhite(knightNum, newX, newY);
    //try to place the current knight at (currX, currY)
    if((currX + currY) % 2 == 0 && currX > 0 && currX < N-1 && currY > 0 && currY < N-1){
        board[currX][currY] = knightNum;
        backtrackWhite(knightNum+1, newX, newY);
        board[currX][currY] = 0;
    }
}

int main(){
    time_t t = clock();
    backtrackWhite(1, 0, 0);
    t = clock() - t;
        double time_taken = ((double)t)/CLOCKS_PER_SEC;
        cout << "Time Taken : " << time_taken<< endl;
    return 0;
}

Он находит всего 2 решения за 89 секунд.

Выход:

0 0 0 0 0 0 0 0
0 0 K 0 0 0 0 0
0 0 K K 0 K K 0
0 0 0 0 0 K 0 0
0 0 K 0 0 0 0 0
0 K K 0 K K 0 0
0 0 0 0 0 K 0 0
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 K 0 0
0 K K 0 K K 0 0
0 0 K 0 0 0 0 0
0 0 0 0 0 K 0 0
0 0 K K 0 K K 0
0 0 K 0 0 0 0 0
0 0 0 0 0 0 0 0

Time Taken : 89.2418

Ответ 2

Ваша попытка очень неэффективна, поэтому может быть только из-за неэффективности, которую вы не можете найти.

Во-первых, бессмысленно пытаться поставить 12 рыцарей. Поместите 6 рыцарей на белые поля. Найдите все решения. Тогда любое решение с 6 рыцарями на белых полях может быть отражено и дает 6 рыцарей на черных полях, и вы это объединяете.

Во-вторых, вы пытаетесь поместить рыцарей в любом порядке. Но порядок произволен. Поэтому разместите их в некотором упорядоченном порядке, например a1, c1, e1, g1, b2, d2, f2, h2, a3... и т.д. Это уменьшает количество вариантов в 6 раз! или 720 (в вашем исходном случае 12!= миллиарды).

Быть эффективным: число белых полей от 0 до 31. Введите черные поля от 0 до 31. Для каждого черного поля найдите индексы белых полей, которые могут быть достигнуты рыцарем в этом поле, и создайте 32-битная битовая карта, представляющая эти поля.

Тогда:

for (int k1 = 0; k1 < 27; ++k1)
    for (int k2 = k1+1, k2 < 28; ++k2)
        for (int k3 = k2+1; k3 < 29; ++k3)
            for (int k4 = k3+1; k4 < 30; ++k4)
                for (int k5 = k4+1; k5 < 31; ++k5)
                   for (int k6 = k5+1; k6 < 32; ++k6)
                       if ((bits [k1] | bits [k2] | bits [k3] | bits [k4] | bits [k5] | bits [k6]) == 0xffffffff)
                           // got a solution!!!

Это менее миллиона проверок, поэтому потребуется несколько миллисекунд.

PS. Ваша комбинация placeKnight/removeKnight не работает. Например, c3 покрывается как рыцарем на b1, так и на a2. Если вы поместите рыцаря на a2, затем на b1, затем удалите рыцаря на b1, вы установите c3 на "не покрытый".

PS. Если у вас была большая шахматная доска, вы бы использовали ярлыки, чтобы уменьшить количество возможностей. Например, поле a1 должно быть покрыто рыцарем в первой строке, второй строке или b3 в третьей строке. Поэтому, если вы попытаетесь поставить рыцаря в поле c3 или новее, а a1 не будет покрываться, нет необходимости пытаться помещать рыцаря в это поле или в более позднее поле.

Ответ 3

Вот довольно эффективный подход; ваша доска представляет собой массив из [8] [8] или один массив из [64]. У вас есть 12 штук. Прежде чем мы начнем писать любой код для реализации программы для решения этой проблемы, позвольте сначала оценить ситуацию и разработать алгоритм.

Есть две вещи, которые мы можем сделать в первую очередь, мы можем опустить или исключить ячейки, которые мы уже знаем, - это места, которые рыцарь не может удовлетворить решению/с этой проблеме. Это внешние ячейки или борт платы, четыре соседних по диагонали внутренние углы и 4 ячейки или плитки, которые составляют мертвую точку доски. Если какой-либо один рыцарь помещается на любой из этих квадратов, то решение не будет работать. Мы также можем посмотреть на самый низкий общий знаменатель, который равен 4, и с этим мы можем разделить плату на 4 квадранта и работать только с тремя частями в этом квадранте.

Это делает две вещи; один из них упрощает определение и более эффективный алгоритм, а также удовлетворяет другому условию. Другими условиями являются: у нас должно быть 3 рыцаря в каждом квадранте, чтобы решение было действительным. Если в любом квадранте есть 4 или более, а в любом квадранте меньше 3, решение снова потерпит неудачу.

Если мы посмотрим на каждый квадрант, мы увидим это:

• Верхний левый квадрант - нижняя правая ячейка - одна из центральных ячеек.
• Верхний правый квадрант - нижняя левая ячейка - одна из центральных ячеек.
• Нижний левый квадрант - верхняя правая ячейка - одна из центральных ячеек.
• Нижний правый квадрант - верхняя левая ячейка - одна из центральных ячеек.

Что делает это жизненно важным? Мы знаем, что при размещении рыцаря на доске для любой открытой ячейки, которая должна быть атакована, эти 4 квадрата в самом центре доски, которые соединяют эти 4 квадранта, не могут иметь Рыцаря в своих местах и ​​что по крайней мере один из внешние смежные ячейки либо в горизонтальном, либо в вертикальном направлении должны иметь рыцаря. Зная это, мы можем работать над 1 квадрантом, чтобы разместить 3 Рыцарей с немедленным исключением ячейки, которую мы только что отметили, и другой ячейки, которая находится рядом с той же центральной ячейкой.

Если вы решаете один из этих квадрантов, тогда остальные три являются их переводами. Таким образом, при таком подходе потребовалось бы столько вычислений для решения сетки 4x4 с ее внутренним углом, указанным в качестве отправной точки, и либо его горизонтальный, либо вертикальный сосед будет располагать рыцарем, а когда-либо один рыцарь, останутся пустыми. Ниже приведена диаграмма, чтобы визуально увидеть этот процесс устранения перед раздачей, чтобы вы знали, как правильно построить или реализовать алгоритмы проверки, поиска и размещения.

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

• Разделить - 4 квадранта - 3 рыцаря на квадрант
• Устранить или пропустить недопустимые ячейки (границы, внутренние углы и центральные ячейки)
• Поместите соседнюю центральную ячейку либо в вертикальном, либо в горизонтальном положении.
• Было найдено 7 возможных ячеек для размещения, но поскольку один из них выбран, а другой соседний не имеет места, у нас теперь осталось 5 ячеек, чтобы разместить еще 2 рыцарей.
• Решите остальную часть платы для этого квадранта.
• Выполнение симметрии над решением выше. Если это квадрант 1, то нам не нужно решать квадрант 4, мы можем взять все решения и выполнить диагональную + симметрию. Если это квадрант 2, то нам не нужно решать для квадранта 3, мы можем выполнить диагональную симметрию.
• Теперь соедините все 4 квадранта вместе для всех решений и отправьте каждое решение вашей проверки, чтобы проверить, удовлетворяет ли оно атакуемому состоянию. Это должен быть линейный поиск через массив из [64] с несколькими сравнениями, довольно быстрый.
• Удалите любое решение, которое не соответствует требованиям.
• Распечатайте результаты.

Edit

Вот пример программы, демонстрирующей, как настроить предопределенную плату, которая подготовлена ​​до того, как вы начнете решать проблему и проверить правильность решений.

#include <conio.h>
#include <iostream>
#include <iomanip>

// These Enums Are Only A Visual Reference And Are Not Used
enum CellPlacement {
    EMPTY_CELL     = 0, 
    BLOCKED_BORDER = 1, 
    BLOCKED_CENTER = 2,
    KNIGHT_PLACED  = 3, 
};

enum CellColor {
    WHITE = 0,
    WHITE = 1,
};

enum IsAttacked {
    NO = 0,
    YES = 1,
};

struct Cell {
    unsigned char row : 3;      // [0x00, 0x07] 
    unsigned char col : 3;      // [0x00, 0x07]
    unsigned char color : 1;    // [0x00, 0x01] - Refer to CellColor
    unsigned char attacked : 1; // [0x00, 0x01] - Refer to IsAttacked
    unsigned char quad : 3;     // [0x01, 0x04] 
    unsigned char state : 3;    // [0x00, 0x03] - Refer to CellPlacement    
};

struct Board {
    Cell cell[8][8];    
};

struct Quad {
    Cell cell[4][4];
};

struct DividedBoard {
    Quad quad[4];
};


int main() {
    Board board;
    DividedBoard divBoard;

    // Temporary
    unsigned char state = 0x00;
    unsigned char quad  = 0x00;

    for ( unsigned char row = 0; row < 8; row++ ) {
        for ( unsigned char col = 0; col < 8; col++ ) {
            // Place Coords
            board.cell[row][col].row = row;
            board.cell[row][col].col = col;

            // Mark Borders, Inner Corners & Center
            if ( row == 0x00 || row == 0x07 || col == 0x00 || col == 0x07 ) {  // Outer Boarders
                state = 0x01;
                board.cell[row][col].state = state;

            } else if ( (row == 0x01 && col == 0x01) || (row == 0x01 && col == 0x06) ||   // Top Left & Right Inner Adjacent Corners
                        (row == 0x06 && col == 0x01) || (row == 0x06 && col == 0x06) ) {  // Bottom Left & Right Inner Adjacent Corners
                state = 0x01;
                board.cell[row][col].state = state;
            } else if ( (row == 0x03 && col == 0x03) || (row == 0x03 && col == 0x04) ||   // Top Left & Right Centers
                        (row == 0x04 && col == 0x03) || (row == 0x04 && col == 0x04) ) {  // Bottom Left & Right Centers
                state = 0x02;
                board.cell[row][col].state = state;
            } else {
                state = 0x00;
                board.cell[row][col].state = state;  // Empty Cells
            }

            // Mark Wich Quadrant They Belong To And Populate Our Divided Board
            if ( (row >= 0x00 && row < 0x04) && (col >= 0x00 && col < 0x04) ) {
                quad = 0x01;
                board.cell[row][col].quad = quad;

                // Set Divided Board To This Quads State
                divBoard.quad[0].cell[row][col].row   = row;
                divBoard.quad[0].cell[row][col].col   = col;                
                divBoard.quad[0].cell[row][col].state = state;
                divBoard.quad[0].cell[row][col].quad  = quad;
            }
            if ( (row >= 0x00 && row < 0x04) && (col >= 0x04) ) {
                quad = 0x02;
                board.cell[row][col].quad = quad;

                // Set Divided Board To This Quads State
                divBoard.quad[1].cell[row][col-4].row   = row;
                divBoard.quad[1].cell[row][col-4].col   = col;          
                divBoard.quad[1].cell[row][col-4].state = state;
                divBoard.quad[1].cell[row][col-4].quad  = quad;
            }
            if ( (row >= 0x04) && (col >= 0x00 && col < 0x04) ) {
                quad = 0x03;
                board.cell[row][col].quad = quad;

                // Set Divided Board To This Quads State
                divBoard.quad[2].cell[row-4][col].row   = row;
                divBoard.quad[2].cell[row-4][col].col   = col;      
                divBoard.quad[2].cell[row-4][col].state = state;
                divBoard.quad[2].cell[row-4][col].quad  = quad;
            }
            if ( row >= 0x04 && col >= 0x04 ) {
                quad = 0x04;
                board.cell[row][col].quad = quad;

                // Set Divided Board To This Quads State
                divBoard.quad[3].cell[row-4][col-4].row   = row;
                divBoard.quad[3].cell[row-4][col-4].col   = col;            
                divBoard.quad[3].cell[row-4][col-4].state = state;
                divBoard.quad[3].cell[row-4][col-4].quad  = quad;
            }       
        }
    }

    // Display Board With Blocked & Empty Squares
    std::cout << std::setw(19) << std::setfill('\0') << "Full Board:\n";
    std::cout << std::setw(20) << std::setfill('\0') << "-----------\n\n";
    for ( unsigned char row = 0x00; row < 0x08; row++ ) {
        for ( unsigned char col = 0x00; col < 0x08; col++ ) {
            std::cout << std::setw(2) << +board.cell[row][col].state << " ";
        }
        std::cout << "\n\n";
    }
    std::cout << "\n";


    // Now Print Our Divided Board By Each Quadrant
    for ( unsigned quad = 0; quad < 4; quad++ ) {
        std::cout << std::setw(6) << "Quad" << quad << ":\n\n";
        for ( unsigned row = 0; row < 4; row++ ) {
            for ( unsigned col = 0; col < 4; col++ ) {
                std::cout << std::setw(2) << +divBoard.quad[quad].cell[row][col].state << " ";
            }
            std::cout << "\n\n";
        }
        std::cout << "\n";
    }   

    std::cout << "\nPress any key to quit.\n" << std::endl;
    _getch();
    return 0;
} // main

Если вы запустите эту программу через консоль, она в основном распечатает диаграмму изображения, которую я ранее отображал. Как видите, структура здесь уже создана. В коде я обозначил внешнюю плату значением 1, 4 внутренних ячеек с 2 и пустые ячейки с 0. От этого момента сейчас речь идет о том, чтобы взять ваш первый квад и начать, выбрав одну из двух точек, которые рядом с центром, который является ячейкой, которая имеет значение 2. Это место сетки в нашем [8] [8] является [3] [3], поэтому вы можете использовать либо местоположение 2 [3] или местоположение 3, и если вы установите рыцаря там значение 3, то остальное останется 0 для этого возможного решения. Как вы можете видеть, есть только 7 пустых ячеек, и после того, как вы сделали свой первый выбор, осталось только 5 ячеек, чтобы выбрать вашего второго рыцаря, а затем осталось 4 места, чтобы разместить вашего третьего и последнего рыцаря.

Как только этот шаг будет выполнен, вы можете сделать отражение симметрии +, чтобы иметь тот же шаблон решения для Quad 4. После создания всех этих решений для Quad 1 Quad 4 также завершено. Тогда вы должны сделать то же самое для Quad 2 и 3.

Итак, если мы выполним математику, где находится 1 Рыцарь, оставляя 2 рыцаря на место и 5 мест. Это означает, что есть 10 возможных решений для первого размещения рыцарей. Если принять во внимание, что первый хороший был помещен в другое место, то это дает нам в общей сложности 20 возможных решений для 1 квадранта. Мы знаем, что есть 4 квадранта, поэтому, когда у вас есть свой контейнер, на котором хранятся все квадроциклы, есть всего 20 ^ 4 различных возможных решения на выбор. Что составляет 160 000 перестановок, которые учитываются для всех возможных возможных мест размещения.

Я на самом деле упомянул, что решения Quad1 являются отражением Qaud4 и что решения Qaud2 являются отражением Quad3. Это верно при тестировании всех решений из-за того, что квадрат отмечен как черный или белый. Однако, когда дело доходит до размещения рыцарей, чтобы найти возможные решения, ничто из этого не имеет значения, поэтому вместо того, чтобы делать симметрию на этом этапе, мы можем просто найти все перестановки для 1 квадранта и просто повернуть их из отмеченной центральной ячейки, чтобы иметь возможность отображать эти решения для остальных трех квадрантов. Поэтому, как только мы найдем 20 возможных макетов для квадранта 1, это всего лишь вопрос выполнения 3 поворотов на всех 20 макетах, чтобы дать нам наши 80 различных макетов.

Тогда это вопрос смешивания и сопоставления каждого из этих макетов и тестирования его против нашей правящей доски.

Теперь это не решает проблему; но это эффективный способ разбить эту проблему, чтобы свести к минимуму количество перестановок установки символов на доске. И вы можете использовать этот подход для разработки своего алгоритма для проверки всех возможных ответов, чтобы найти все правильные решения. Теперь эти структуры, которые я показал, являются хорошим началом, но вы также можете добавить к структуре ячейки. Вы можете добавить идентификатор, для какого цвета - квадрат, и другой идентификатор, который, если он находится, находится под атакой. Я использовал unsigned char, потому что при работе с байтом в сравнении с int или даже коротким печать печати намного меньше, а так как диапазон значений для того, что нужно, только от 0-7, я также решил используйте поле бит в моей структуре Ячейка. Таким образом, вместо 1 ячейки, имеющей 6 байтов, одна ячейка теперь имеет всего 2 байта с оставшейся парой бит. Однако вам нужно проявлять осторожность при использовании битовых полей из-за энтерианства, поскольку все значения имеют unsigned char, это не должно быть проблемой. Это помогает сэкономить и сэкономить на пространстве памяти при построении массивов этих ячеек в четырехзначных результатах, когда мы начнем делать все перестановки возможных решений, чтобы найти рабочее решение. Кроме того, путем установки значений ячеек с числами в отличие от фактической буквы, математические вычисления могут быть намного проще.

Одна вещь, о которой я не упоминал, заключается в следующем: я не уверен на 100%, но, глядя на доску достаточно долго, потому что я шахматный игрок, когда вы идете, чтобы сделать процесс создания всего возможного решения, вы можете устранить большинство из них, прежде чем отправлять их функции, чтобы проверить, удовлетворяют ли они окончательному условию, и, я думаю, что 3 рыцаря в одном квадранте в рамках их расположения также должны были быть в том же в которой они атакуют. Другими словами, они образуют форму L на доске. Это означает, что если один из этих трех рыцарей не имеет другого рыцаря, который смежен как в горизонтальном, так и в вертикальном положении, мы можем заключить, что этот макет не будет действительным макетом. Вы можете включить этот шаг, когда вы делаете размещение своих рыцарей в одном квадранте, а затем таким образом, когда вы делаете вращения для остальных трех квадрантов, вы будете иметь долю от общего количества перестановок, которые нужно решить.

И из-за применения этого смежного правила к центральной ячейке и дополнительного условия, в котором я считаю, что три рыцаря, которые были помещены, должны иметь форму того, как он атакует, вот изображение, показывающее все допустимые местоположения, которые рыцарь может быть в.

Из-за смежного с центральным правилом места размещения, где, если вы выберете вертикальную ячейку, то центральная горизонтальная ячейка будет опустошена, и это оставляет мне поверить, что это как минимум 8 возможных решений, которые могут быть только 2 или 4 из они действительны. Таким образом, мы даже сузили наш поиск и перестановки еще больше. Мы можем также заключить, что сужение нашего поиска из-за предыдущего правила заключается в том, что мы также можем применить правило "Бинго". Так же, как в Бинго, центральная ячейка "Свободная", ну для нас здесь, в каждом квадранте нет центральной ячейки, однако от креста от всех возможных мест размещения мы теперь знаем, что центр этого креста всегда будет иметь рыцарь. Используя координаты, которые я использовал и переходил по строке col на полный пансион, это были бы [2,2], [2,5], [5,2] и [5,5]. Таким образом, во время фазы размещения они могут быть автоматически добавлены сначала, тогда у вас есть выбор смежного центра, тогда, наконец, у вас есть два варианта, оставшихся с вашей последней частью, которая не будет другой ячейкой, которая также находится рядом с вашей центральной ячейкой что квадрант.

И с этим дополнительным случаем мы сократили наши полные перестановки с 160 000 до 4 на квадрант для 4 ^ 4 полных перестановок по всей доске. Поэтому, если у вас есть предварительно заполненная таблица поиска всех этих возможных решений, тогда функция проверки достоверности будет требоваться только 256 раз, а не 160 000 или миллиарды, если вы запустите ее для всех мест размещения на доске. Предварительное устранение является одним из шагов, которые многие люди не принимают во внимание до решения сложной проблемы. Что так приятно в этом, так это то, что если есть 256 полных возможных перестановок, которые могут генерировать действительный ответ для тестирования, если он удовлетворяет требованиям, каждый из них может быть индексом от 0 до 255. Индексирование для всех этих решений с использованием unsigned char в шестнадцатеричных значениях сначала в 1 байт памяти.

Теперь, когда ваша функция проверяет эти 256 перестановок возможных решений, это можно сделать в простом цикле for и while в линейном процессе, просто проверяя каждую ячейку, чтобы увидеть, если она атакована, выполнив базовый процесс обнаружения столкновений, и если любой из них терпит неудачу, мы можем вырваться из итерации этого цикла while и отказаться от этого решения, а затем перейти к следующей итерации цикла for и продолжить этот процесс. Если контейнер решения удовлетворяет его, то вы хотите отметить появление этого решения и сохранить его в другом контейнере, который содержит все допустимые решения для каждой итерации циклов. Это также может исключить необходимость или использование для рекурсии.

Я знаю, что это довольно долго, но это требует многого, чтобы объяснить это подробно, и мне потребовалось несколько часов, чтобы изучить проблему, составить графику, написать небольшую программу и объяснить, что я сделал и почему Я сделал это, поэтому, пожалуйста, не стесняйтесь оставлять комментарии и дайте мне знать, что вы думаете об этом подходе.

Ответ 4

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

Пример: Угловые клетки могут атаковать только два рыцаря, поэтому способность атаки равна двум. Атака-способность средней ячейки равна 8.

Атака-способность клеток

| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |

| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |

| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |

| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |

| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |

| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |

| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |

| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |

Расчет атакуемости

AttackingNodes::AttackingNodes(int x, int y)
{
    target = new Element(x, y);
    CreateAtackList();
}

void AttackingNodes::CreateAtackList()
{
    for(int diffx = -2; diffx <=2; ++diffx)
    {

        for(int diffy = -2; diffy <=2; ++diffy)
        {
            if((diffx*diffx + diffy* diffy) == 5)
            {
                AddAttack(target->_X + diffx, target->_Y + diffy);
            }
        }
    }
}

void AttackingNodes::AddAttack( int x, int y )
{
    if(x >= 0 && y >= 0 && x < BOARD_SIZE && y < BOARD_SIZE)
    {
        Element* element = new Element(x, y);
        attackers.push_back(element);
    }
}

размер атакующих в атакующих узлах равен атакуемости.

Затем создается многоадресная атака против attackingNodes

for(int x = 0; x < BOARD_SIZE; ++x)
{
    for(int y = 0; y < BOARD_SIZE; ++y)
    {
        AttackingNodes* nodes = new AttackingNodes(x, y);
        attackNodes[x][y] = nodes;
        mapAttackPriority.insert(std::make_pair(nodes->attackers.size(), nodes));
    }
}

Если атакуемость низка, тогда есть меньше вариантов атаки данной ячейки.

Итак, выбирается первый node из multimap, который имеет более малые варианты атаки.

Первая ячейка будет 0, 0. Существует два варианта атаки 0, 0

1, 2 or 2, 1

Позволяет выбрать 1, 2 и атаковать ячейки, если они пусты. Он может атаковать 6 ячеек.

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

bool Solution::attack( Element* nodes )
{
    ++knightCount;
    AttackingNodes* attackList = PriorityTargets::inst->attackNodes[nodes->_X][nodes->_Y];
    std::list<Element*>::iterator itr;

    board[nodes->_X][nodes->_Y] = CC_KNIGHT;

    for(itr = attackList->attackers.begin(); itr != attackList->attackers.end(); ++itr)
    {
        Element* attackNode = *itr;

        if(board[attackNode->_X][attackNode->_Y] == CC_EMPTY)
        {
            board[attackNode->_X][attackNode->_Y] = CC_ATTACKED;
        }
    }

    return false;
}

| A | 0 | A | 0 | 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | A | 0 | 0 | 0 | 0 |

| 0 | K | 0 | 0 | 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | A | 0 | 0 | 0 | 0 |

| A | 0 | A | 0 | 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

Затем алгоритм ищет следующую пустую ячейку (без K ночь, нет A ttacked), с самой низкой атакой атакуйте ее доступными параметрами.

AttackingNodes* PriorityTargets::GetNextNode( Solution* solution )
{

    std::multimap<size_t, AttackingNodes*>::iterator priorityItr;
    for(priorityItr  = mapAttackPriority.begin(); priorityItr != mapAttackPriority.end(); ++priorityItr)
    {
        AttackingNodes* attackNodes = priorityItr->second;
        if(solution->board[attackNodes->target->_X][attackNodes->target->_Y] == CC_EMPTY)
        {
            return attackNodes;
        }
    }

    return NULL;
}

Это будет другой угол node для вторых опций, и он будет продолжаться, пока число рыцарей больше 12 или не будет пустых ячеек.

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

Solution::Solution()
{
    Clear();
}

void Solution::Print()
{

    std::cout << std::endl ;
    for(int x = 0; x < BOARD_SIZE; ++x)
    {
        for(int y = 0; y < BOARD_SIZE; ++y)
        {
            std::cout << (int)board[x][y] << " ";
        }
        std::cout << std::endl ;
    }


    std::cout << std::endl ;

}

bool Solution::Solve( Solution* solution )
{
    AttackingNodes* nextAttackingNode = PriorityTargets::inst->GetNextNode(solution);

    if(nextAttackingNode != NULL)
    {
        Solution* newSolutioon = new Solution();
        std::list<Element*>::iterator itr;
        for(itr = nextAttackingNode->attackers.begin(); itr != nextAttackingNode->attackers.end(); ++itr)
        {
            Element* attack = *itr;


                *newSolutioon = *solution;
                newSolutioon->attack(attack);
                if(newSolutioon->knightCount < 13)
                {
                    Solve(newSolutioon);
                }
                else
                {
                    //Fail
                    newSolutioon->Clear();
                }
        }

        delete newSolutioon;
    }
    else
    {
        std::cout << "Solved" << std::endl;
        solution->Print();
    }

    return false;
}


void Solution::Clear()
{
    memset(board, 0, BOARD_SIZE*BOARD_SIZE);
    knightCount = 0;
}

И я получил ответ менее чем за 500 мс в режиме выпуска Visual Studio 2008. Я использовал 2 для рыцаря и 1 для нападения.

Ответ 5

Проделана большая работа по ограничению проблемы доминирования рыцарей для разных размеров досок. Здесь - статья, которая, как представляется, суммирует все предыдущие работы и добавляет несколько новых поворотов. И здесь - статья, которая утверждает, что демонстрирует алгоритм линейного времени для доминирования рыцарей. Я даже нашел ссылки на постоянный алгоритм доминирования рыцарей, но я не вижу, где кто-то взял на себя труд написать его, Сначала заведите мозг, напишите второй код.