c++ - fuente - 12 rompecabezas dominantes de caballeros(retroceso)

codigo fuente del 8 puzzle en java (5)

Aquí hay un enfoque bastante eficiente; su tablero es una matriz de [8] [8] o una única matriz de [64]. Tienes 12 piezas para colocar. Antes de comenzar a escribir cualquier código para implementar un programa para resolver este problema, primero evaluemos la situación y diseñemos un algoritmo.

Hay dos cosas que podemos hacer primero, podemos omitir o eliminar celdas que ya sabemos que son lugares que un caballero no puede ser para satisfacer las soluciones a este problema. Estas son las celdas externas o internas del tablero, las cuatro esquinas interiores diagonalmente adyacentes y las 4 celdas o mosaicos que forman el centro muerto del tablero. Si se coloca un caballero en cualquiera de estos cuadrados, la solución no funcionará. También podemos ver el mínimo común denominador que es 4 y con esto podemos dividir el tablero en 4 cuadrantes y trabajar con solo 3 piezas en ese cuadrante.

Esto hace dos cosas; uno hace que el algoritmo sea más fácil de definir y más eficiente, y también satisface otra condición. Las otras condiciones son las siguientes: debemos tener 3 caballeros en cada cuadrante para que la solución sea válida. Si hay 4 o más en un cuadrante y hay menos de 3 en cualquier cuadrante, la solución nuevamente fallará.

Si miramos cada Cuadrante podemos ver esto:

Cuadrante superior izquierdo - Celda inferior derecha es una de las celdas centrales.
Cuadrante superior derecho - Celda inferior izquierda es una de las celdas centrales.
Cuadrante inferior izquierdo - Celda superior derecha es una de las celdas centrales.
Cuadrante inferior derecho: celda superior izquierda es una de las celdas centrales.

¿Qué hace que esto sea vital? Sabemos que al colocar un caballero en el tablero para que se fije una célula abierta para atacar, estos 4 casillas en el centro del tablero que une estos 4 cuadrantes no pueden tener un Caballero en sus ubicaciones y que al menos uno de los casilleros Células adyacentes hacia afuera, ya sea en la dirección horizontal o vertical, deben tener un Caballero. Sabiendo esto, podemos trabajar en 1 Cuadrante para colocar 3 Caballeros con la exclusión inmediata de la celda que acabamos de marcar y la otra celda que está adyacente a la misma celda central.

Si resuelves uno de estos cuadrantes, los otros tres son solo traducciones de ellos. Entonces con este enfoque solo tomaría muchos cálculos para resolver una cuadrícula 4x4 con su esquina interna listada como punto de partida y su vecino horizontal o vertical tendrá un caballero colocado, y cualquiera que tenga un caballero colocado el otro adyacente lo hará ser dejado vacío Aquí hay un diagrama para ver visualmente este proceso de eliminación de antemano, para que sepa cómo construir o implementar correctamente sus algoritmos de comprobación, búsqueda y ubicación.

Entonces, una vez que es capaz de ver esto y saber qué está pasando con el problema. Estos son los pasos a seguir en su algoritmo.

Divide - 4 cuadrantes - 3 caballeros por cuadrante
Elimine u omita las celdas no válidas (borde, esquinas interiores y celdas centrales)
Coloque adyacente desde el centro de la celda ya sea en posición vertical u horizontal.
Había 7 celdas posibles para elegir para la colocación, pero dado que una está seleccionada y la otra adyacente no tendrá una ubicación, ahora tenemos 5 celdas para colocar 2 caballeros más.
Resuelve el resto del tablero para este cuadrante.
Realice la simetría en la solución anterior. Si este es el cuadrante 1, entonces no necesitamos resolver el cuadrante 4, podemos tomar todas las soluciones y realizar una simetría + diagonal. Si este es el cuadrante 2, entonces no necesitamos resolver para el cuadrante 3, podemos realizar la simetría diagonal.
Ahora unir los 4 cuadrantes nuevamente para todas las soluciones y enviar cada solución a su comprobador para verificar si satisface la condición atacable. Esto debería ser una búsqueda lineal a través de una matriz de [64] con algunas comparaciones, bastante rápido.
Elimine cualquier solución que no cumpla con los requisitos.
Imprimir los resultados.

Editar

Aquí hay un programa de ejemplo que demuestra cómo configurar una placa predefinida que está preparada antes de comenzar a resolver el problema y verificar si las soluciones son correctas.

#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

Si ejecuta este programa a través de la consola, básicamente imprimirá el diagrama de la imagen que había mostrado previamente. Como puede ver, la estructura aquí ya está creada. En el código marqué el tablero exterior con un valor de 1, las 4 celdas internas con 2 y las celdas vacías con 0. Desde este punto ahora es cuestión de tomar su primer quad y comenzar eligiendo uno de los dos puntos que están adyacente al centro, que es la celda que tiene un valor de 2. Esta ubicación de cuadrícula en nuestro [8] [8] es [3] [3] por lo que puede usar la ubicación 2 [3] o la ubicación 3 para comenzar y si configura un Knight allí un valor de 3, entonces el otro seguirá siendo un 0 para esta posible solución. Como puedes ver, solo hay 7 celdas vacías y, después de hacer tu primera elección, solo quedan 5 celdas para elegir para colocar tu 2nd Knight, luego quedan 4 ubicaciones para colocar tu tercer y último caballero.

Una vez hecho este paso, puede hacer el reflejo de la simetría + para tener el mismo patrón de solución para Quad 4. Una vez que genere todas estas soluciones para Quad 1 Quad 4 también se completará. Entonces tienes que hacer lo mismo para Quad 2 y 3.

Entonces, si hacemos los cálculos donde 1 Caballero se coloca dejando 2 caballeros para colocar y 5 ubicaciones Eso significa que hay 10 soluciones posibles para la colocación de los primeros caballeros. Si tomamos en cuenta que el primero fue colocado en la otra ubicación, eso nos da un total de 20 soluciones posibles para 1 cuadrante. Sabemos que hay 4 cuadrantes así que cuando tienes tu contenedor que contiene todos los cuádriceps hay un total de 20 ^ 4 posibles soluciones diferentes para elegir. Que es 160,000 permutaciones totales que cuentan para todas las diferentes ubicaciones posibles.

De hecho, mencioné que las soluciones de Quad1 son el reflejo de Qaud4 y que las soluciones de Qaud2 son el reflejo de Quad3. Esto es cierto cuando se prueban todas las soluciones debido a que el cuadrado se marca como negro o blanco. Sin embargo, cuando se trata de ubicar a los caballeros para encontrar posibles soluciones, nada de eso es relevante, así que en lugar de hacer simetría en esta etapa, podemos encontrar todas las permutaciones para 1 cuadrante y rotarlas desde su celda central marcada para poder mapear esas soluciones a los otros 3 cuadrantes. Entonces, una vez que encontramos los 20 diseños posibles para el Cuadrante 1, solo se trata de realizar 3 rotaciones en los 20 diseños para darnos nuestros 80 diseños diferentes.

Luego, se trata de mezclar y combinar cada uno de estos diseños y probarlo contra nuestro tablero de reglas.

Ahora esto no resuelve el problema; pero esta es una forma eficiente de descomponer este problema para minimizar la cantidad de permutaciones de configuración de los caracteres en el tablero. Y puede usar este enfoque para diseñar su algoritmo y probar todas las respuestas posibles para encontrar todas las soluciones correctas. Ahora estas estructuras que he mostrado son un buen comienzo, pero también pueden agregarse a la estructura de la celda. Puede agregar un identificador de qué color es el cuadrado, y otro identificador que si su posición está bajo ataque. Utilicé caracteres sin signo porque la huella de memoria es mucho más pequeña cuando se trabaja con un byte que con un int, o incluso un short, y como el rango de valores para lo que se necesita va solo de 0 a 7, también decidí usar un campo de bit dentro de la estructura de mi Celda. Así que en lugar de 1 celda que es de 6 bytes, una sola celda ahora solo tiene 2 bytes y le quedan un par de bits. Debe tener precaución al usar campos de bits debido a endianess, sin embargo, dado que todos los valores son de char sin signo, esto no debería ser un problema. Esto ayuda a conservar y ahorrar espacio en la memoria al construir las matrices de estas celdas en los resultados del cuadrante cuando comenzamos a hacer todas las permutaciones de las posibles soluciones para encontrar una solución funcional. Además, al establecer los valores de las celdas con números en oposición a una letra real, permite que los cálculos matemáticos sean mucho más fáciles.

Una cosa que no mencioné es esta: no estoy 100% seguro de esto, pero al mirar el tablero lo suficiente porque soy un jugador de ajedrez, cuando vas a hacer el proceso de generar todas las soluciones posibles, puede eliminar la mayoría de ellos incluso antes de enviarlos a la función para verificar si satisfacen la condición final, y es decir, creo que los 3 Caballeros en un cuadrante dentro de su arreglo también tendrían que estar en la misma forma en que ellos atacan. En otras palabras, formarán una L en el tablero. Lo que significa que si uno de estos tres caballeros no tiene otro caballero adyacente tanto en posición horizontal como vertical, podemos concluir que este diseño no será válido. Podrías incorporar este paso cuando realices la colocación de tus caballeros en un solo cuadrante y luego de esta manera cuando hagas las rotaciones para los otros 3 cuadrantes tendrás una fracción de la cantidad total de permutaciones para resolver.

Y debido a la aplicación de esa regla adyacente a una celda central y la condición adicional de que creo que los tres caballeros que están ubicados tienen que adoptar la forma de cómo ataca, aquí hay una imagen que muestra todas las ubicaciones válidas en las que puede estar un caballero.

Debido a la regla de colocación adyacente al centro, si eliges la celda vertical, se vaciará la celda horizontal del centro, entonces eso me hace creer que hay al menos 8 soluciones posibles, de las cuales solo 2 o 4 son válidas. . Así que incluso redujimos nuestra búsqueda y permutaciones aún más. Una cosa que también podemos concluir para reducir nuestra búsqueda debido a la regla anterior es que aquí también podemos aplicar la Regla del "Bingo". Al igual que en Bingo, la celda del centro es "Gratis", bueno para nosotros aquí, porque en cada cuadrante no hay centro celular, sin embargo, por el golpeteo de la cruz de todas las ubicaciones posibles ahora sabemos que el centro de esta cruz siempre tendrá un caballero. Usando las coordenadas que utilicé e yendo por la fila col en el tablero completo, estos serían [2,2], [2,5], [5,2] y [5,5]. Entonces, durante la fase de ubicación, estos pueden agregarse automáticamente primero, luego puede elegir el adyacente al centro, y finalmente le quedan dos opciones con su última pieza que no será la otra celda que también está adyacente a su celda central de ese Cuadrante.

Y con este caso adicional, hemos reducido nuestras permutaciones totales de 160,000 a 4 por cuadrante para 4 ^ 4 permutaciones totales en todo el tablero. Por lo tanto, si tiene una tabla de búsqueda previamente poblada de todas estas soluciones posibles, la función para verificar la validez solo tendrá que llamarse 256 veces, en lugar de 160,000 o miles de millones si la ejecuta para todas las ubicaciones de la placa. La eliminación previa es uno de los pasos que muchas personas no toman en cuenta antes de resolver un problema complejo. Lo bueno de esto es que si hay 256 permutaciones posibles totales que pueden generar una respuesta válida para probarse si cumple los requisitos es que cada uno de estos puede tener un índice de 0-255. La indexación para todas estas soluciones usando un char sin signo en valores hexadecimales primero en 1 byte de memoria.

Ahora, en cuanto a su función para comprobar estas 256 permutaciones de posibles soluciones, esto se puede hacer en un simple ciclo de entrada y salida en un proceso lineal simplemente comprobando cada celda para ver si es atacado realizando un proceso de detección de colisión básico y si alguien es estos errores, podemos salir de la iteración de ese ciclo while y descartar esta solución, luego pasar a la siguiente iteración de nuestro ciclo for y continuar ese proceso. Si un contenedor de una solución lo satisface, entonces desea marcar la ocurrencia de esa solución y guardarla en otro contenedor que contenga todas las soluciones válidas para cada iteración de los bucles. Esto también puede eliminar la necesidad o el uso para la recursión.

Sé que esto es bastante largo, pero se necesita mucho para explicarlo en detalle y me tomó varias horas examinar el problema, elaborar los gráficos, escribir el pequeño programa y explicar lo que hice y por qué lo hice , por favor siéntase libre de dejar un comentario y dejarme saber lo que piensa de este enfoque.

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

Lo que tengo que 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 de alguna manera se cuelga.~~ 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 placeKnight límites de la matriz en lugar de la placeKnight y se removeKnight (como, j + 2 <N en lugar de j + 2 <= N)
El return false; agregado es return false; en backtracking

Problema: ahora se repite para siempre. Prueba 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; }

Como señaló @ gnasher729, tratar de ubicar a los 12 caballeros sería muy ineficiente, por lo que podemos intentar colocar 6 caballeros en white blocks , pero usando este enfoque solo podemos atacar un máximo de 30 black blocks out of 32 .

Entonces de lo anterior podemos tomar 2 enfoques:

1) Podemos reparar 2 caballeros en los 2 bloques negros restantes, y luego tratar de colocar los 4 caballeros restantes en los 30 bloques negros restantes, fíjate ahora que solo tenemos que atacar los 26 bloques blancos restantes.

@ gnasher729 dijo que podíamos reflejar la solución, pero no fui capaz de encontrar la lógica de arreglar 2 lugares y luego encontrar el espejo, porque solo 30 bloques estaban siendo atacados, si el no de caballeros había sido 14, entonces todo el Se habrían atacado 32 bloques, y tal vez hubiera sido posible encontrar un espejo.

2) El segundo sería forzar la fuerza bruta de los 6 caballeros restantes cada vez que encontremos una solución para los primeros 6 caballeros que atacaron más de 26 black blocks , que implementé pero que aún no encontraba una solución.

Entonces, como @nm dijo que podemos tratar de encontrar soluciones desde el centro para reducir el espacio de búsqueda, intenté encontrar una solución colocando a los caballeros en el cuadrado central de 6 X 6 , y además solo busqué soluciones cuando 30 de los 32 se atacaron bloques negros en lugar de 26, y finalmente fue posible encontrar 2 soluciones para el problema que eran simétricas, podría haber más soluciones disponibles para el problema con un mejor enfoque.

Código en c ++:

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

Solo encuentra 2 soluciones en unos 89 segundos.

Salida:

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

Primero defino mi concepto básico de habilidad de ataque. La capacidad de ataque es cuántos caballeros pueden atacar una celda determinada.

Ejemplo: las celdas de esquina solo pueden ser atacadas por dos caballeros, por lo que la capacidad de ataque es dos. La capacidad de ataque de la célula media es 8.

Capacidad de ataque de las células

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

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

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

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

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

Cálculo de la capacidad de ataque

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

el tamaño de los atacantes en los nodos atacantes es igual a la capacidad de ataque.

Entonces multimap se crea capacidad de ataque contra atacarNodos

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

Si la capacidad de ataque es baja, entonces hay menos opciones para atacar una celda dada.

De modo que se elige el primer nodo de multimap que tiene menos opciones de ataque.

Primera celda será 0, 0. Hay dos opciones para atacar a 0, 0

1, 2 or 2, 1

Vamos a elegir 1, 2 y atacar a las células si están vacíos. Puede atacar 6 células.

ataque (..) está poniendo caballero de célula dada. Atackers y objetivos están relacionados misma manera. Así que los datos generados al calcular la capacidad de ataque se utiliza aquí.

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 |

A continuación, el algoritmo de búsqueda para la próxima celda vacía (sin K noche, hay un ttacked) con el menor ataque attackability con las opciones disponibles.

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

Será un nodo de otra esquina para segundas opciones y que se prolongará hasta el recuento caballero es mayor que 12, o no hay celdas vacías.

caballero recuento es mayor que 12 se trata de un intento de fallar y respaldado seguimiento. Si no hay ninguna celda vacía, entonces es una solución.

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

Y tengo la respuesta en menos de 500 ms en modo de lanzamiento de Visual Studio 2008. He utilizado para Knight 2 y 1 para el atacado.

Su intento es muy ineficiente, por lo que podría ser solo por la ineficiencia que no pueda encontrar una solución.

En primer lugar, no tiene sentido tratar de colocar 12 caballeros. Coloca 6 caballeros en campos blancos. Encuentra todas las soluciones Entonces cualquier solución con 6 caballeros en campos blancos se puede duplicar y le da 6 caballeros en campos negros, y usted combina eso.

Segundo, estás tratando de ubicar a los caballeros en cualquier orden. Pero el orden es arbitrario. Así que colóquelos en un orden ordenado, como a1, c1, e1, g1, b2, d2, f2, h2, a3 ... etc. ¡Eso reduce el número de elecciones por un factor 6! o 720 (en su caso original 12! = miles de millones).

Para ser eficiente: numere los campos blancos de 0 a 31. Numere los campos negros de 0 a 31. Para cada campo negro, encuentre los índices de los campos blancos a los que puede llegar un caballero en ese campo y cree un bit de 32 mapa de bits que representa esos campos.

Entonces:

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!!!

Eso es menos de un millón de cheques, por lo que tomaría unos pocos milisegundos.

PD. Tu combinación de placeKnight / removeKnight no funciona. Por ejemplo, c3 está cubierto por un caballero en b1 o en a2. Si coloca un caballo en a2, luego en b1, luego retire el caballo en b1, configure c3 en "no cubierto".

PD. Si tuviera un tablero de ajedrez más grande, tomaría atajos para reducir el número de posibilidades. Por ejemplo, el campo a1 debe estar cubierto por un caballero en la primera fila, segunda fila o b3 en la tercera fila. Por lo tanto, si intenta colocar un caballo en un campo c3 o posterior, y a1 no está cubierto, no hay necesidad de intentar colocar un caballero en ese campo o en otro campo posterior.

Mucho trabajo se ha hecho sobre el problema que limita la dominación caballeros de diversos tamaños del tablero. Aquí está un artículo que parece resumir todo el trabajo anterior y añade algunos nuevos giros. Y aquí es un artículo que pretende demostrar un algoritmo de tiempo lineal para caballeros dominación. Incluso he encontrado referencias a un algoritmo de caballeros dominio constante en el tiempo , pero no veo donde cualquier persona ha tomado la molestia de escribirlo. Participar cerebro primero, segundo escribir código.