Imprima todas las combinaciones únicas de configuración de N piezas en un tablero NxN

Dado un número entero N , la tarea es imprimir todas las combinaciones únicas de poner N piezas en un tablero NxN .

Nota: Escriba (“*”) para piezas y (“-“) para un espacio vacío.

Ejemplo:

Entrada: N = 2
Salida:
* *
– –

*-
*-

* –
– *

– *
* –

– *
– *

– –
* *
Explicación: El número total de espacios vacíos es 2*2=4 y las piezas que se colocarán son 2, por lo que hay 4C2 combinaciones ((4!/(2!*2!))=6) posibles, lo cual es representado arriba.

Entrada: N = 1
Salida: *

Enfoque: este problema se puede resolver utilizando la recursividad para generar todas las soluciones posibles. Ahora, siga los pasos a continuación para resolver este problema:

Cree una función llamada allCombinations , que generará todas las soluciones posibles.
Tomará un entero piecesPlaced que denota el número total de piezas colocadas, un entero N que denota el número de piezas que se deben colocar, dos enteros fila y columna que denotan la fila y la columna donde se colocará la pieza actual y una string de caracteres para almacenar la array donde se colocan las piezas, como argumentos.
Ahora, la llamada inicial a allCombinations pasará 0 como piezas Colocadas , N , 0 y 0 como fila y columna y una string vacía como ans .
En cada llamada, verifique el caso base, es decir:
- Si la fila se convierte en N y se colocan todas las piezas, es decir, piezas colocadas = N. Luego imprima la respuesta y regrese. De lo contrario, si piecesPlaced no es N , simplemente regrese de esta llamada.
Ahora haz dos llamadas:
- Uno para agregar un ‘*’ en la posición actual y otro para dejar esa posición y agregar ‘-‘ .
Después de esto, las llamadas recursivas imprimirán todas las posibles soluciones.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all
// combinations of setting N
// pieces in N x N board
void allCombinations(int piecesPlaced, int N, int row,
                     int col, string ans)
{
   
    // If the total 2d array's space
    // is exhausted then backtrack.
    if (row == N) {
 
        // If all the pieces are
        // placed then print the answer.
        if (piecesPlaced == N) {
            cout << ans;
        }
        return;
    }
    int nr = 0;
    int nc = 0;
 
    // Declare one string
    // that will set the piece.
    string x = "";
 
    // Declare one string that
    // will leave the space blank.
    string y = "";
 
    // If the current column
    // is out of bounds then
    // increase the row
    // and set col to 0.
    if (col == N - 1) {
        nr = row + 1;
        nc = 0;
        x = ans + "*\n";
        y = ans + "-\n";
    }
 
    // Else increase the col
    else {
        nr = row;
        nc = col + 1;
        x = ans + "*\t";
        y = ans + "-\t";
    }
   
    // Set the piece in the
    // box and move ahead
    allCombinations(piecesPlaced + 1, N, nr, nc, x);
 
    // Leave the space blank
    // and move forward
    allCombinations(piecesPlaced, N, nr, nc, y);
}
 
// Driver Code
int main()
{
    int N = 2;
    allCombinations(0, N, 0, 0, "");
    return 0;
}
 
    // This code is contributed by rakeshsahni.

Java

// Java Program for the above approach
 
import java.io.*;
import java.util.*;
 
public class main {
 
    // Function to print all
    // combinations of setting N
    // pieces in N x N board
    public static void allCombinations(
        int piecesPlaced,
        int N, int row,
        int col, String ans)
    {
        // If the total 2d array's space
        // is exhausted then backtrack.
        if (row == N) {
 
            // If all the pieces are
            // placed then print the answer.
            if (piecesPlaced == N) {
                System.out.println(ans);
            }
            return;
        }
        int nr = 0;
        int nc = 0;
 
        // Declare one string
        // that will set the piece.
        String x = "";
 
        // Declare one string that
        // will leave the space blank.
        String y = "";
 
        // If the current column
        // is out of bounds then
        // increase the row
        // and set col to 0.
        if (col == N - 1) {
            nr = row + 1;
            nc = 0;
            x = ans + "*\n";
            y = ans + "-\n";
        }
 
        // Else increase the col
        else {
            nr = row;
            nc = col + 1;
            x = ans + "*\t";
            y = ans + "-\t";
        }
        // Set the piece in the
        // box and move ahead
        allCombinations(
            piecesPlaced + 1, N,
            nr, nc, x);
 
        // Leave the space blank
        // and move forward
        allCombinations(piecesPlaced, N,
                        nr, nc, y);
    }
 
    // Driver Code
    public static void main(String[] args)
        throws Exception
    {
        int N = 2;
 
        allCombinations(0, N, 0, 0, "");
    }
}

Python3

# Python Program for the above approach
 
# Function to print all
# combinations of setting N
# pieces in N x N board
def allCombinations(piecesPlaced, N, row, col, ans):
   
    # If the total 2d array's space
    # is exhausted then backtrack.
    if row == N:
       
        # If all the pieces are
        # placed then print the answer.
        if piecesPlaced == N:
            print(ans)
        return;
     
    nr = 0
    nc = 0
     
    # Declare one string
    # that will set the piece.
    x = ""
     
    # Declare one string that
    # will leave the space blank.
    y = ""
     
    # If the current column
    # is out of bounds then
    # increase the row
    # and set col to 0.
     
    if col == N - 1:
        nr = row + 1
        nc = 0
        x = ans + "*\n"
        y = ans + "-\n"
         
    # Else increase the col
    else:
        nr = row
        nc = col + 1
        x = ans + "*    "
        y = ans + "-    "
     
    # Set the piece in the
    # box and move ahead
    allCombinations(piecesPlaced + 1, N, nr, nc, x);
     
    # Leave the space blank
    # and move forward
    allCombinations(piecesPlaced, N, nr, nc, y);
 
# Driver Code
N = 2
allCombinations(0, N, 0, 0, "")
 
# This code is contributed by rdtank.

C#

// C# Program for the above approach
using System;
public class main {
 
    // Function to print all
    // combinations of setting N
    // pieces in N x N board
    public static void allCombinations(int piecesPlaced,
                                       int N, int row,
                                       int col, String ans)
    {
        // If the total 2d array's space
        // is exhausted then backtrack.
        if (row == N) {
 
            // If all the pieces are
            // placed then print the answer.
            if (piecesPlaced == N) {
                Console.WriteLine(ans);
            }
            return;
        }
        int nr = 0;
        int nc = 0;
 
        // Declare one string
        // that will set the piece.
        String x = "";
 
        // Declare one string that
        // will leave the space blank.
        String y = "";
 
        // If the current column
        // is out of bounds then
        // increase the row
        // and set col to 0.
        if (col == N - 1) {
            nr = row + 1;
            nc = 0;
            x = ans + "*\n";
            y = ans + "-\n";
        }
 
        // Else increase the col
        else {
            nr = row;
            nc = col + 1;
            x = ans + "*\t";
            y = ans + "-\t";
        }
       
        // Set the piece in the
        // box and move ahead
        allCombinations(piecesPlaced + 1, N, nr, nc, x);
 
        // Leave the space blank
        // and move forward
        allCombinations(piecesPlaced, N, nr, nc, y);
    }
 
    // Driver Code
    public static void Main(string[] args)
 
    {
        int N = 2;
 
        allCombinations(0, N, 0, 0, "");
    }
}
 
// This code is contributed by ukasp.

Javascript

// Javascript Program for the above approach
 
// Function to print all
// combinations of setting N
// pieces in N x N board
function allCombinations(piecesPlaced, N, row, col, ans) {
 
  // If the total 2d array's space
  // is exhausted then backtrack.
  if (row == N) {
 
    // If all the pieces are
    // placed then print the answer.
    if (piecesPlaced == N) {
      document.write(ans);
    }
    return;
  }
  let nr = 0;
  let nc = 0;
 
  // Declare one string
  // that will set the piece.
  let x = "";
 
  // Declare one string that
  // will leave the space blank.
  let y = "";
 
  // If the current column
  // is out of bounds then
  // increase the row
  // and set col to 0.
  if (col == N - 1) {
    nr = row + 1;
    nc = 0;
    x = ans + "*<br>";
    y = ans + "-<br>";
  }
 
  // Else increase the col
  else {
    nr = row;
    nc = col + 1;
    x = ans + "*     ";
    y = ans + "-     ";
  }
 
  // Set the piece in the
  // box and move ahead
  allCombinations(piecesPlaced + 1, N, nr, nc, x);
 
  // Leave the space blank
  // and move forward
  allCombinations(piecesPlaced, N, nr, nc, y);
}
 
// Driver Code
let N = 2;
allCombinations(0, N, 0, 0, "");
 
// This code is contributed by Saurabh Jaiswal

Producción:

*    *
-    -

*    -
*    -

*    -
-    *

-    *
*    -

-    *
-    *

-    -
*    *

Complejidad de tiempo: O(2^M), donde M=N*N
Espacio auxiliar: $O(1)$

Publicación traducida automáticamente

Artículo escrito por shrayansh95 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta