Rompecabezas de 12 caballeros dominantes (retroceso)

Question

Apr 10, 2016, 09:57 AM

Rompecabezas de 12 caballeros dominantes (retroceso)

He estado buscando durante horas y todavía no he encontrado una solución completamente funcional para este tipo de rompecabezas. Entonces seguí un problema similar con los obispos.

Lo que necesito hacer es colocar 12 caballeros en el tablero de ajedrez de tal manera que todos los cuadrados libres del tablero sean atacados por al menos una pieza.

El resultado final debería verse así:

El problema es que mi programa solo prueba diferentes combinaciones con dos últimas piezas y luego de alguna manera se bloquea. EDITADO

Lo que he hecho hasta ahora:

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

Editar:

Se arreglaron los límites de la matriz enplaceKnight yremoveKnight (como, j + 2 <N en lugar de j + 2 <= N)Adicionalreturn false; enbacktracking

Problema: Ahora se repite para siempre. Intenta toneladas de combinaciones, pero nunca encuentra la que necesito (¿Fuerza bruta?)

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