Dados los números enteros M, N y K , la tarea es colocar K caballos en un tablero de ajedrez M*N de modo que no se ataquen entre sí. Se espera que los caballos se coloquen en diferentes casillas del tablero. Un caballo puede moverse dos cuadrados verticalmente y un cuadrado horizontalmente o dos cuadrados horizontalmente y un cuadrado verticalmente. Los caballeros se atacan entre sí si uno de ellos puede alcanzar al otro en un solo movimiento. Hay varias formas de colocar caballos K en un tablero M*N o, a veces, no hay forma de colocarlos. Se espera que enumeremos todas las soluciones posibles.
Ejemplos:
Entrada: M = 3, N = 3, K = 5 Salida: KAKAKAKAKAKAKKKAKA Número total de soluciones: 2
Entrada: M = 5, N = 5, K = 13 Salida: KAKAKAKAKAKAKAKAKAKAK AKAK Número total de soluciones: 1
Acercarse:Este problema se puede resolver usando backtracking. La idea es colocar los caballos uno por uno comenzando desde la primera fila y la primera columna y avanzando hacia la primera fila y la segunda columna de manera que no se ataquen entre sí. Cuando termina una fila, pasamos a la siguiente fila. Antes de colocar un caballo, siempre verificamos si el bloqueo es seguro, es decir, no es una posición de ataque de algún otro caballo. Si es seguro, colocamos el caballo y marcamos su posición de ataque en el tablero; de lo contrario, avanzamos y buscamos otros bloques. Mientras seguimos este procedimiento, creamos un nuevo tablero cada vez que insertamos un nuevo caballo en nuestro tablero. Esto se hace porque si obtenemos una solución y necesitamos otras soluciones, entonces podemos retroceder a nuestro tablero anterior con la configuración anterior de los caballeros que luego se pueden verificar para otras soluciones posibles. El proceso de retroceder continúa hasta que obtenemos todas nuestras soluciones posibles. A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the above approach
#include <iostream>
using namespace std;
/* m*n is the board dimension
k is the number of knights to be placed on board
count is the number of possible solutions */
int m, n, k;
int count = 0;
/* This function is used to create an empty m*n board */
void makeBoard(char** board)
{
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '_';
}
}
}
/* This function displays our board */
void displayBoard(char** board)
{
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << " " << board[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/* This function marks all the attacking
position of a knight placed at board[i][j]
position */
void attack(int i, int j, char a, char** board)
{
/* conditions to ensure that the
block to be checked is inside the board */
if ((i + 2) < m && (j - 1) >= 0) {
board[i + 2][j - 1] = a;
}
if ((i - 2) >= 0 && (j - 1) >= 0) {
board[i - 2][j - 1] = a;
}
if ((i + 2) < m && (j + 1) < n) {
board[i + 2][j + 1] = a;
}
if ((i - 2) >= 0 && (j + 1) < n) {
board[i - 2][j + 1] = a;
}
if ((i + 1) < m && (j + 2) < n) {
board[i + 1][j + 2] = a;
}
if ((i - 1) >= 0 && (j + 2) < n) {
board[i - 1][j + 2] = a;
}
if ((i + 1) < m && (j - 2) >= 0) {
board[i + 1][j - 2] = a;
}
if ((i - 1) >= 0 && (j - 2) >= 0) {
board[i - 1][j - 2] = a;
}
}
/* If the position is empty,
place the knight */
bool canPlace(int i, int j, char** board)
{
if (board[i][j] == '_')
return true;
else
return false;
}
/* Place the knight at [i][j] position
on board */
void place(int i, int j, char k, char a, char** board,
char** new_board)
{
/* Copy the configurations of
old board to new board */
for (int y = 0; y < m; y++) {
for (int z = 0; z < n; z++) {
new_board[y][z] = board[y][z];
}
}
/* Place the knight at [i][j]
position on new board */
new_board[i][j] = k;
/* Mark all the attacking positions
of newly placed knight on the new board */
attack(i, j, a, new_board);
}
/* Function for placing knights on board
such that they don't attack each other */
void kkn(int k, int sti, int stj, char** board)
{
/* If there are no knights left to be placed,
display the board and increment the count */
if (k == 0) {
displayBoard(board);
count++;
}
else {
/* Loop for checking all the
positions on m*n board */
for (int i = sti; i < m; i++) {
for (int j = stj; j < n; j++) {
/* Is it possible to place knight at
[i][j] position on board? */
if (canPlace(i, j, board)) {
/* Create a new board and place the
new knight on it */
char** new_board = new char*[m];
for (int x = 0; x < m; x++) {
new_board[x] = new char[n];
}
place(i, j, 'K', 'A', board, new_board);
/* Call the function recursively for
(k-1) leftover knights */
kkn(k - 1, i, j, new_board);
/* Delete the new board
to free up the memory */
for (int x = 0; x < m; x++) {
delete[] new_board[x];
}
delete[] new_board;
}
}
stj = 0;
}
}
}
// Driver code
int main()
{
m = 4, n = 3, k = 6;
/* Creation of a m*n board */
char** board = new char*[m];
for (int i = 0; i < m; i++) {
board[i] = new char[n];
}
/* Make all the places are empty */
makeBoard(board);
kkn(k, 0, 0, board);
cout << endl << "Total number of solutions : " << count;
return 0;
}
Java
// Java implementation of the above approach
class GFG {
/* m*n is the board dimension
k is the number of knights to be placed on board
count is the number of possible solutions */
static int m, n, k;
static int count = 0;
/* This function is used to create an empty m*n board */
static void makeBoard(char[][] board)
{
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '_';
}
}
}
/* This function displays our board */
static void displayBoard(char[][] board)
{
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(" " + board[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
/* This function marks all the attacking
position of a knight placed at board[i][j]
position */
static void attack(int i, int j, char a, char[][] board)
{
/* conditions to ensure that the
block to be checked is inside the board */
if ((i + 2) < m && (j - 1) >= 0) {
board[i + 2][j - 1] = a;
}
if ((i - 2) >= 0 && (j - 1) >= 0) {
board[i - 2][j - 1] = a;
}
if ((i + 2) < m && (j + 1) < n) {
board[i + 2][j + 1] = a;
}
if ((i - 2) >= 0 && (j + 1) < n) {
board[i - 2][j + 1] = a;
}
if ((i + 1) < m && (j + 2) < n) {
board[i + 1][j + 2] = a;
}
if ((i - 1) >= 0 && (j + 2) < n) {
board[i - 1][j + 2] = a;
}
if ((i + 1) < m && (j - 2) >= 0) {
board[i + 1][j - 2] = a;
}
if ((i - 1) >= 0 && (j - 2) >= 0) {
board[i - 1][j - 2] = a;
}
}
/* If the position is empty,
place the knight */
static boolean canPlace(int i, int j, char[][] board)
{
if (board[i][j] == '_')
return true;
else
return false;
}
/* Place the knight at [i][j] position
on board */
static void place(int i, int j, char k, char a,
char[][] board, char[][] new_board)
{
/* Copy the configurations of
old board to new board */
for (int y = 0; y < m; y++) {
for (int z = 0; z < n; z++) {
new_board[y][z] = board[y][z];
}
}
/* Place the knight at [i][j]
position on new board */
new_board[i][j] = k;
/* Mark all the attacking positions
of newly placed knight on the new board */
attack(i, j, a, new_board);
}
/* Function for placing knights on board
such that they don't attack each other */
static void kkn(int k, int sti, int stj, char[][] board)
{
/* If there are no knights left to be placed,
display the board and increment the count */
if (k == 0) {
displayBoard(board);
count++;
}
else {
/* Loop for checking all the
positions on m*n board */
for (int i = sti; i < m; i++) {
for (int j = stj; j < n; j++) {
/* Is it possible to place knight at
[i][j] position on board? */
if (canPlace(i, j, board)) {
/* Create a new board and place
the new knight on it */
char[][] new_board = new char[m][];
for (int x = 0; x < m; x++) {
new_board[x] = new char[n];
}
place(i, j, 'K', 'A', board,
new_board);
/* Call the function recursively for
(k-1) leftover knights */
kkn(k - 1, i, j, new_board);
}
}
stj = 0;
}
}
}
// Driver code
public static void main(String[] args)
{
m = 4;
n = 3;
k = 6;
count = 0;
/* Creation of a m*n board */
char[][] board = new char[m][];
for (int i = 0; i < m; i++) {
board[i] = new char[n];
}
/* Make all the places are empty */
makeBoard(board);
kkn(k, 0, 0, board);
System.out.println("\n Total number of solutions : "
+ count);
}
}
// This code is contributed by jainlovely450
K K K A A A A A A K K K K A K A K A K A K A K A A K A K A K A K A K A K Total number of solutions : 3
Publicación traducida automáticamente
Artículo escrito por KumariPoojaMandal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA