Головоломка "12 доминирующих рыцарей"

Question

Apr 10, 2016, 09:57 AM

Головоломка "12 доминирующих рыцарей"

Я искал несколько часов и пока не нашел полностью работающего решения для такого рода головоломки. Таким образом, я следовал за подобной проблемой с епископами.

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

Конечный результат должен выглядеть так:

Проблема в что моя программа пробует разные комбинации только с двумя последними частями, а затем как-то вылетает. РЕДАКТИРОВАНИЕ

Что я сделал до сих пор:

#include <iostream>
using namespace std;
#define N 8

void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);

int main()
{
    int chessBoard[N][N];

    fillChessBoard(chessBoard, 0);
    backtracking(chessBoard, 0);

    return 0;
}

bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
    if(knightNum==12)
    {
        if(allSpaceDominated(chessBoard))
        {
            printChessBoard(chessBoard);
            return true;
        }
        else return false;
    }
    else
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(chessBoard[i][j]!=2)
                {
                    placeKnight(chessBoard, i, j);
                    printChessBoard(chessBoard); //step by step

                    if(backtracking(chessBoard, knightNum+1)) return true;
                    removeKnight(chessBoard, i, j);
                }
            }
        }
    }
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            chessBoard[i][j]=num;
        }
    }
}
void printChessBoard(int (&chessBoard)[N][N])
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cout<<chessBoard[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    cout<<endl;
    cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
    int num=0;
    chessBoard[i][j]=num;

    if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
    if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;

    if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
    if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;

    if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
    if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;

    if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
    if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;

    for(int k=0; k<N; k++) //correct overlapping dominations
    {
        for(int x=0; x<N; x++)
        {
            if(chessBoard[k][x]==2)
            {
                placeKnight(chessBoard, k, x);
            }
        }
    }
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
    int num=1;
    chessBoard[i][j]=2;

    if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
    if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;

    if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
    if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;

    if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
    if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;

    if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
    if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(chessBoard[i][j]==0) return false;
        }
    }
    return true;
}

Редактировать:

Исправлены границы массива вplaceKnight а такжеremoveKnight (например, j + 2 <N вместо j + 2 <= N)добавленнойreturn false; вbacktracking

Проблема: Теперь это зацикливается навсегда. Пробует множество комбинаций, но никогда не находит ту, которая мне нужна (перебор?)

#include <iostream>
using namespace std;
#define N 8

void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);

int main()
{
    int chessBoard[N][N];

    fillChessBoard(chessBoard, 0);
    backtracking(chessBoard, 0);
    printChessBoard(chessBoard);

    return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
    if(knightNum==12)
    {
        if(allSpaceDominated(chessBoard))
        {
            printChessBoard(chessBoard);
            return true;
        }
        else return false;
    }
    else
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(chessBoard[i][j]!=2)
                {
                    placeKnight(chessBoard, i, j);
                    printChessBoard(chessBoard);// step by step
                    if(backtracking(chessBoard, knightNum+1)) return true;

                    removeKnight(chessBoard, i, j);
                }
            }
        }
        return false; //ADDED LINE
    }
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            chessBoard[i][j]=num;
        }
    }
}
void printChessBoard(int (&chessBoard)[N][N])
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cout<<chessBoard[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    cout<<endl;
    //cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
    int num=0;
    chessBoard[i][j]=num;

    if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
    if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;

    if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
    if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;

    if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
    if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;

    if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
    if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;

    for(int k=0; k<N; k++)
    {
        for(int x=0; x<N; x++)
        {
            if(chessBoard[k][x]==2)
            {
                placeKnight(chessBoard, k, x);
            }
        }
    }
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
    int num=1;
    chessBoard[i][j]=2;

    if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
    if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;

    if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
    if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;

    if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
    if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;

    if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
    if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(chessBoard[i][j]==0) return false;
        }
    }
    return true;
}

Головоломка "12 доминирующих рыцарей"

Ответы на вопрос(5)

Ваш ответ на вопрос

Популярные вопросы

Вы очень активны! Это здорово!

Головоломка &quot;12 доминирующих рыцарей&quot;

Ответы на вопрос(5)

Ваш ответ на вопрос

Популярные вопросы

Головоломка "12 доминирующих рыцарей"