Skip to Content
CTRL K

Búsqueda completa con recursión

Subconjuntos

HechoFuenteNombreDificultadTagsSolución
CSESApple DivisionFácilComplete Search, Recursion, Subsetsen el módulo

Recursos

Recursos
FuenteRecursoNotas
CPH5.1 - Generating Subsets

buena explicación + código, no hace falta repetir

Solución - Apple Division

Como n≤20n \le 20, podemos resolverlo probando todas las divisiones posibles de nn manzanas en dos conjuntos y quedándonos con la de menor diferencia de pesos. Hay dos formas de hacerlo.

Generar subconjuntos de forma recursiva

El primer método es escribir una función recursiva que recorra todas las posibilidades.

En algún índice, o bien sumamos weighti\texttt{weight}_i al primer conjunto o al segundo, guardando dos sumas sum1\texttt{sum}_1 y sum2\texttt{sum}_2 con la suma de los valores de cada conjunto.

Luego devolvemos la diferencia entre las dos sumas cuando llegamos al final del arreglo.

32741

Manzana 3: la colocamos en el platillo A o en el B.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int n;
vector<long long> weights;
 
ll recurse_apples(int index, ll sum1, ll sum2) {
	// Ya agregamos todas las manzanas: devolvemos la diferencia absoluta
	if (index == n) { return abs(sum1 - sum2); }
 
	// Probamos agregar la manzana actual al primer conjunto o al segundo
	return min(recurse_apples(index + 1, sum1 + weights[index], sum2),
	           recurse_apples(index + 1, sum1, sum2 + weights[index]));
}
 
int main() {
	cin >> n;
	weights.resize(n);
	for (int i = 0; i < n; i++) { cin >> weights[i]; }
 
	// Resolvemos empezando en la manzana 0 con ambos conjuntos vacíos
	cout << recurse_apples(0, 0, 0) << endl;
}
import java.io.*;
import java.util.*;
 
public class AppleDivision {
	static int n;
	static int[] weights;
 
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio();
 
		n = io.nextInt();
		weights = new int[n];
		for (int i = 0; i < n; i++) { weights[i] = io.nextInt(); }
 
		// Resolvemos empezando en la manzana 0 con ambos conjuntos vacíos
		io.println(recurseApples(0, 0, 0));
		io.close();
	}
 
	static long recurseApples(int index, long sum1, long sum2) {
		// Ya agregamos todas las manzanas: devolvemos la diferencia absoluta
		if (index == n) { return Math.abs(sum1 - sum2); }
 
		// Probamos agregar la manzana actual al primer conjunto o al segundo
		return Math.min(recurseApples(index + 1, sum1 + weights[index], sum2),
		                recurseApples(index + 1, sum1, sum2 + weights[index]));
	}
 
	// CodeSnip{Kattio}
}
n = int(input())
weights = list(map(int, input().split()))
 
 
def recurse_apples(i: int, sum1: int, sum2: int) -> int:
	# Ya agregamos todas las manzanas: devolvemos la diferencia absoluta
	if i == n:
		return abs(sum2 - sum1)
 
	# Probamos agregar la manzana actual al primer conjunto o al segundo
	return min(
		recurse_apples(i + 1, sum1 + weights[i], sum2),
		recurse_apples(i + 1, sum1, sum2 + weights[i]),
	)
 
 
# Resolvemos empezando en la manzana 0 con ambos conjuntos vacíos
print(recurse_apples(0, 0, 0))

Generar subconjuntos con máscaras de bits

Una máscara de bits (bitmask) es un entero cuya representación binaria se usa para representar un subconjunto. En el contexto de este problema, si el ii-ésimo bit vale 11 en una máscara concreta, decimos que la ii-ésima manzana está en s1s_1. Si no, diremos que está en s2s_2. Podemos iterar sobre todos los subconjuntos s1s_1 si recorremos todas las máscaras de 00 a 2N−12^N-1.

Hagamos una demostración rápida con N=3N=3. Estos son los enteros de 00 a 23−12^3-1 junto con sus representaciones binarias y los elementos correspondientes incluidos en s1s_1. Como se ve, están todos los subconjuntos posibles.

NúmeroBinarioManzanas en s1s_1
0000{}\{\}
1001{0}\{0\}
2010{1}\{1\}
3011{0,1}\{0,1\}
4100{2}\{2\}
5101{0,2}\{0,2\}
6110{1,2}\{1,2\}
7111{0,1,2}\{0,1,2\}

Con esta idea podemos implementar la solución.

El código usa algunas operaciones bit a bit un poco más elaboradas:

  • 1 << x para un entero xx es otra forma de escribir 2x2^x, que en binario tiene encendido solo el xx-ésimo bit.
  • El operador & (AND) toma dos enteros y devuelve un entero nuevo. a & b para enteros aa y b‘devolveraˊunenteronuevocuyob` devolverá un entero nuevo cuyoi−eˊsimobitestaˊencendidosiysolosiel-ésimo bit está encendido si y solo si eli−eˊsimobitestaˊencendidotantoen-ésimo bit está encendido tanto enacomoencomo enbundefinedx−eˊsimobitestaˊencendidoen-ésimo bit está encendido enmask$.

Para aprender más sobre ellas, hay un módulo dedicado a las operaciones bit a bit.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	int n;
	cin >> n;
	vector<ll> weights(n);
	for (ll &w : weights) { cin >> w; }
 
	ll ans = INT64_MAX;
	for (int mask = 0; mask < (1 << n); mask++) {
		ll sum1 = 0;
		ll sum2 = 0;
		for (int i = 0; i < n; i++) {
			// Comprobar si el i-ésimo bit está encendido
			if (mask & (1 << i)) {
				// Si lo está, la manzana se incluye en sum1
				sum1 += weights[i];
			} else {
				sum2 += weights[i];
			}
		}
		ans = min(ans, abs(sum1 - sum2));
	}
 
	cout << ans << endl;
}
import java.io.*;
import java.util.*;
 
public class AppleDivision {
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int[] weights = new int[n];
		for (int i = 0; i < n; i++) { weights[i] = io.nextInt(); }
 
		long ans = Long.MAX_VALUE;
		for (int mask = 0; mask < (1 << n); mask++) {
			long sum1 = 0;
			long sum2 = 0;
			for (int i = 0; i < n; i++) {
				// Comprobar si el i-ésimo bit está encendido
				if ((mask & (1 << i)) > 0) {
					// Si lo está, la manzana se incluye en sum1
					sum1 += weights[i];
				} else {
					sum2 += weights[i];
				}
			}
			ans = Math.min(ans, Math.abs(sum1 - sum2));
		}
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n = int(input())
weights = list(map(int, input().split()))
 
ans = float("inf")
for mask in range(1 << n):
	sum1 = 0
	sum2 = 0
	for i in range(n):
		# Comprueba si el i-ésimo bit está encendido
		if mask & (1 << i):
			# Si lo está, la manzana se incluye en sum1
			sum1 += weights[i]
		else:
			sum2 += weights[i]
 
	ans = min(ans, abs(sum1 - sum2))
 
print(ans)

Opcionalmente, como los dos conjuntos son idénticos, podemos fijar que el último número siempre esté en el segundo conjunto. Eso equivale a iterar las máscaras de 00 a 2n−1−12^{n-1}-1, en lugar de 2n−12^{n}-1.

Permutaciones

Una permutación es un reordenamiento de una lista de elementos.

HechoFuenteNombreDificultadTagsSolución
CSESCreating Strings IFácilComplete Search, Recursion, Permutationen el módulo

Orden lexicográfico

Este término aparece con bastante frecuencia, p. ej. en USACO Bronze - Photoshoot .

Pensemos cómo están ordenadas las palabras en un diccionario. (De hecho, de ahí viene el término “lexicográfico”.)

En los diccionarios, las palabras que empiezan con la letra a aparecen al principio, seguidas de las que empiezan con b, y así sucesivamente. Si dos palabras tienen la misma letra inicial, se usa la segunda letra para compararlas; si la primera y la segunda son iguales, se usa la tercera, y así hasta que o bien llegamos a una letra distinta, o bien llegamos al final de alguna palabra (en ese caso, va primero la más corta).

Las permutaciones se pueden ordenar lexicográficamente de forma casi igual. Primero las agrupamos por su primer elemento; si el primer elemento de dos permutaciones es igual, las comparamos por el segundo; si el segundo también es igual, comparamos por el tercero, y así.

Por ejemplo, las permutaciones de 3 elementos, en orden lexicográfico, son

[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]. [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

Nótese que la lista empieza con las permutaciones que empiezan con 1 (igual que un diccionario empieza con las palabras que empiezan con a), seguidas de las que empiezan con 2 y las que empiezan con 3. Con el mismo elemento inicial, se usa el segundo elemento para comparar.

En general, salvo que se pida de forma explícita la solución lexicográficamente más chica/más grande, no hace falta preocuparse de si las permutaciones se generan en orden lexicográfico. Sin embargo, la idea de orden lexicográfico aparece bastante a menudo en problemas de concursos, y en contextos variados, así que se recomienda mucho familiarizarse con su definición.

Algunos problemas piden un ordenamiento de elementos que cumpla ciertas condiciones. En esos problemas, si N≤10N \leq 10, podemos simplemente iterar sobre las N!=N⋅(N−1)⋅(N−2)⋯1N!=N\cdot (N-1)\cdot (N-2)\cdots 1 permutaciones y comprobar la validez de cada una.

Solución - Creating Strings I

Recursos
FuenteRecursoNotas
CPH5.2 - Generating Permutations

explicación breve + código de los dos métodos de abajo

Generar permutaciones de forma recursiva

Esto es solo una modificación leve del método 1 de CPH.

Usamos la función recursiva search\texttt{search} para encontrar todas las permutaciones del string ss. Primero, llevamos la cuenta de cuántas veces aparece cada carácter en ss. En cada llamada a la función, agregamos un carácter disponible al string actual y llamamos a search\texttt{search} con ese string. Cuando el string actual tiene el mismo tamaño que ss, encontramos una permutación y la podemos agregar a la lista de perms\texttt{perms}.

#include <bits/stdc++.h>
using namespace std;
 
string s;
vector<string> perms;
int char_count[26];
 
void search(const string &curr = "") {
	// Terminamos de crear una permutación
	if (curr.size() == s.size()) {
		perms.push_back(curr);
		return;
	}
	for (int i = 0; i < 26; i++) {
		// Para todos los caracteres disponibles
		if (char_count[i] > 0) {
			// Lo agregamos al string actual y seguimos la búsqueda
			char_count[i]--;
			search(curr + (char)('a' + i));
			char_count[i]++;
		}
	}
}
 
int main() {
	cin >> s;
	for (char c : s) { char_count[c - 'a']++; }
 
	search();
 
	cout << perms.size() << '\n';
	for (const string &perm : perms) { cout << perm << '\n'; }
}
import java.io.*;
import java.util.*;
 
public class CreatingStrings1 {
	static String s;
	static List<String> perms = new ArrayList<String>();
	static int[] charCount = new int[26];
 
	static void search(String curr) {
		// Terminamos de crear una permutación
		if (curr.length() == s.length()) {
			perms.add(curr);
			return;
		}
		for (int i = 0; i < 26; i++) {
			// Para todos los caracteres disponibles
			if (charCount[i] > 0) {
				// Lo agregamos al string actual y seguimos la búsqueda
				charCount[i]--;
				search(curr + (char)(i + 'a'));
				charCount[i]++;
			}
		}
	}
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		s = io.next();
 
		for (int i = 0; i < s.length(); i++) { charCount[s.charAt(i) - 'a']++; }
 
		search("");
 
		io.println(perms.size());
		for (String perm : perms) { io.println(perm); }
		io.close();
	}
 
	// CodeSnip{Kattio}
}
s = input()
perms = []
char_count = [0] * 26
 
 
def search(curr: str = ""):
	# terminamos de crear una permutación
	if len(curr) == len(s):
		perms.append(curr)
		return
	for i in range(26):
		# Para todos los caracteres disponibles
		if char_count[i] > 0:
			# Lo agregamos al string actual y seguimos la búsqueda
			char_count[i] -= 1
			search(curr + chr(ord("a") + i))
			char_count[i] += 1
 
 
for c in s:
	char_count[ord(c) - ord("a")] += 1
 
search()
 
print(len(perms))
for perm in perms:
	print(perm)

Generar permutaciones con next_permutation

Recursos
FuenteRecursoNotas
Mark NelsonNext Permutation

explicación con un ejemplo

Como alternativa, podemos usar la función next_permutation(). Esta función recibe un rango y lo modifica a la siguiente permutación mayor. Si no hay una permutación mayor, devuelve false. Para iterar sobre todas las permutaciones, la colocamos dentro de un bucle do-while. Usamos un do-while en lugar de un while típico porque un while modificaría la permutación más chica antes de que tuviéramos chance de procesarla.

Lo que vaya en la función check depende del problema, pero debería verificar si la permutación actual cumple las restricciones del enunciado.

do {
	check(v);  // procesar o comprobar si la permutación actual es válida
} while (next_permutation(v.begin(), v.end()));

Cada llamada a next_permutation hace, en promedio, una cantidad constante de intercambios si recorremos las N!N! permutaciones de tamaño NN.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	string s;
	cin >> s;
	sort(s.begin(), s.end());
 
	// perms es una lista ordenada de todas las permutaciones del string dado
	vector<string> perms;
	do { perms.push_back(s); } while (next_permutation(s.begin(), s.end()));
 
	cout << perms.size() << endl;
	for (const string &perm : perms) { cout << perm << endl; }
}

Generar permutaciones con itertools.permutations

Como itertools.permutations trata los elementos como únicos según la posición, no según el valor, devuelve todas las permutaciones, con repeticiones. Poner las tuplas devueltas en un conjunto filtra los duplicados, y como se devuelven tuplas, hay que unir los caracteres en un string.

from itertools import permutations
 
s = input()
 
# perms es una lista ordenada de todas las permutaciones del string dado
perms = sorted(set(permutations(s)))
 
print(len(perms))
for perm in perms:
	print("".join(perm))

Backtracking

HechoFuenteNombreDificultadTagsSolución
CSESChessboard & QueensNormalComplete Search, Recursion, Permutationen el módulo

Recursos

Recursos
FuenteRecursoNotas
CPH5.3 - Backtracking

código y explicación del problema foco

CP23.2 - Complete Search

búsqueda completa iterativa vs recursiva

Solución - Chessboard & Queens

Generando permutaciones

Una solución de fuerza bruta que compruebe las (648)\binom{64}{8} combinaciones posibles de reinas tendría más de 4 mil millones de arreglos que revisar, y sería demasiado lenta.

Hay que hacer fuerza bruta un poco más inteligente: observemos que podemos generar permutaciones de forma directa de modo que no haya dos reinas atacándose por estar en la misma fila o columna.

Como no puede haber dos reinas en la misma columna, tiene sentido colocar una en cada fila. Queda ver cómo variar las filas en las que está cada reina. Eso se puede hacer generando todas las permutaciones de 1⋯81 \cdots 8, donde los números indican en qué fila está cada reina.

Por ejemplo, la permutación [6,0,5,1,4,3,7,2][6, 0, 5, 1, 4, 3, 7, 2] produce este arreglo de reinas:

01234567
0Q
1Q
2Q
3Q
4Q
5Q
6Q
7Q

Hacer esto reduce la cantidad de arreglos que hay que revisar a un mucho más manejable 8!8!.

#include <bits/stdc++.h>
using namespace std;
 
const int DIM = 8;
 
int main() {
	vector<vector<bool>> blocked(DIM, vector<bool>(DIM));
	for (int r = 0; r < DIM; r++) {
		string row;
		cin >> row;
		for (int c = 0; c < DIM; c++) { blocked[r][c] = row[c] == '*'; }
	}
 
	vector<int> queens(DIM);
	// Valores iniciales 0, 1...7
	iota(queens.begin(), queens.end(), 0);
 
	int valid_num = 0;
	do {
		bool works = true;
		// Comprobar si alguna celda fue bloqueada por la entrada
		for (int c = 0; c < DIM; c++) {
			if (blocked[queens[c]][c]) {
				works = false;
				break;
			}
		}
 
		// Comprobar las diagonales de arriba-izquierda a abajo-derecha
		vector<bool> taken(DIM * 2 - 1);
		for (int c = 0; c < DIM; c++) {
			// Comprobar si la diagonal con esa suma ya está ocupada
			if (taken[c + queens[c]]) {
				works = false;
				break;
			}
			taken[c + queens[c]] = true;
		}
 
		// Comprobar las diagonales de arriba-derecha a abajo-izquierda
		taken = vector<bool>(DIM * 2 - 1);
		for (int c = 0; c < DIM; c++) {
			// queens[c] - c puede ser negativo; DIM - 1 lo desplaza
			if (taken[queens[c] - c + DIM - 1]) {
				works = false;
				break;
			}
			taken[queens[c] - c + DIM - 1] = true;
		}
 
		if (works) { valid_num++; }
	} while (next_permutation(queens.begin(), queens.end()));
 
	cout << valid_num << endl;
}
import java.io.*;
import java.util.*;
 
public class ChessboardQueens {
	private static final int DIM = 8;
 
	private static boolean[][] blocked = new boolean[DIM][DIM];
 
	private static final List<Integer> queens = new ArrayList<>();
	private static final boolean[] chosen = new boolean[DIM];
 
	private static int validNum = 0;
 
	public static void main(String[] args) throws Exception {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		for (int r = 0; r < DIM; r++) {
			String row = read.readLine();
			for (int c = 0; c < DIM; c++) {
				if (row.charAt(c) == '*') { blocked[r][c] = true; }
			}
		}
 
		genQueens();
 
		System.out.println(validNum);
	}
 
	private static void genQueens() {
		if (queens.size() == DIM) {
			boolean works = true;
 
			// Comprobar si alguna celda fue bloqueada por la entrada
			for (int c = 0; c < DIM; c++) {
				if (blocked[queens.get(c)][c]) {
					works = false;
					break;
				}
			}
 
			// Comprobar las diagonales de arriba-izquierda a abajo-derecha
			boolean[] taken = new boolean[DIM * 2 - 1];
			for (int c = 0; c < DIM; c++) {
				// Comprobar si la diagonal con esta suma ya está ocupada
				if (taken[c + queens.get(c)]) {
					works = false;
					break;
				}
				taken[c + queens.get(c)] = true;
			}
 
			// Comprobar las diagonales de arriba-derecha a abajo-izquierda
			taken = new boolean[DIM * 2 - 1];
			for (int c = 0; c < DIM; c++) {
				// queens.get(c) - c puede ser negativo; DIM - 1 lo desplaza
				if (taken[queens.get(c) - c + DIM - 1]) {
					works = false;
					break;
				}
				taken[queens.get(c) - c + DIM - 1] = true;
			}
 
			if (works) { validNum++; }
		} else {
			for (int c = 0; c < DIM; c++) {
				if (chosen[c]) { continue; }
				chosen[c] = true;
				queens.add(c);
				genQueens();
				chosen[c] = false;
				queens.remove(queens.size() - 1);
			}
		}
	}
}
from itertools import permutations
 
DIM = 8
 
blocked = [[False] * DIM for _ in range(DIM)]
for r in range(DIM):
	row = input()
	for c in range(DIM):
		blocked[r][c] = row[c] == "*"
 
valid_num = 0
for queens in permutations(range(DIM)):
	works = True
 
	# Comprobar si alguna celda fue bloqueada por la entrada
	for c in range(DIM):
		if blocked[queens[c]][c]:
			works = False
			break
 
	# Comprobar las diagonales de arriba-izquierda a abajo-derecha
	taken = [False] * (DIM * 2 - 1)
	for c in range(DIM):
		# Comprobar si la diagonal con esa suma ya está ocupada
		if taken[c + queens[c]]:
			works = False
			break
		taken[c + queens[c]] = True
 
	# Comprobar las diagonales de arriba-derecha a abajo-izquierda
	taken = [False] * (DIM * 2 - 1)
	for c in range(DIM):
		# queens[c] - c puede ser negativo; DIM - 1 lo desplaza
		if taken[queens[c] - c + DIM - 1]:
			works = False
			break
		taken[queens[c] - c + DIM - 1] = True
 
	if works:
		valid_num += 1
 
print(valid_num)

Usando backtracking

Según CPH:

Un algoritmo de backtracking empieza con una solución vacía y la extiende paso a paso. La búsqueda recorre de forma recursiva todas las formas distintas en que se puede construir una solución.

Como las cotas son chicas, podemos hacer backtracking recursivo sobre todas las formas de colocar las reinas, guardando el estado actual del tablero.

En cada nivel, intentamos colocar una reina en todas las casillas que no estén bloqueadas ni atacadas por otras reinas. Después recursamos, sacamos esta reina y hacemos backtracking.

Por último, incrementamos la respuesta cuando colocamos las ocho reinas.

#include <bits/stdc++.h>
using namespace std;
 
const int DIM = 8;
 
vector<vector<bool>> blocked(DIM, vector<bool>(DIM));
vector<bool> rows_taken(DIM);
// Indicadores de las diagonales de abajo-izquierda a arriba-derecha
vector<bool> diag1(DIM * 2 - 1);
// Indicadores de las diagonales de abajo-derecha a arriba-izquierda
vector<bool> diag2(DIM * 2 - 1);
 
int valid_num = 0;
 
void search_queens(int c = 0) {
	if (c == DIM) {
		// Ya llenamos todas las filas: incrementamos y volvemos
		valid_num++;
		return;
	}
 
	for (int r = 0; r < DIM; r++) {
		bool row_open = !rows_taken[r];
		bool diag_open = !diag1[r + c] && !diag2[r - c + DIM - 1];
		if (!blocked[r][c] && row_open && diag_open) {
			// Se ocuparon una fila y dos diagonales
			rows_taken[r] = diag1[r + c] = diag2[r - c + DIM - 1] = true;
			search_queens(c + 1);
			// Y ahora ya no lo están
			rows_taken[r] = diag1[r + c] = diag2[r - c + DIM - 1] = false;
		}
	}
}
 
int main() {
	for (int r = 0; r < DIM; r++) {
		string row;
		cin >> row;
		for (int c = 0; c < DIM; c++) { blocked[r][c] = row[c] == '*'; }
	}
 
	search_queens();
 
	cout << valid_num << endl;
}
import java.io.*;
 
public class ChessboardQueens {
	private static final int DIM = 8;
 
	private static boolean[][] blocked = new boolean[DIM][DIM];
 
	private static final boolean[] rowsTaken = new boolean[DIM];
	// Indicadores de las diagonales de abajo-izquierda a arriba-derecha
	private static final boolean[] diag1 = new boolean[DIM * 2 - 1];
	// Indicadores de las diagonales de abajo-derecha a arriba-izquierda
	private static final boolean[] diag2 = new boolean[DIM * 2 - 1];
 
	private static int validNum = 0;
 
	public static void main(String[] args) throws Exception {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		for (int r = 0; r < DIM; r++) {
			String row = read.readLine();
			for (int c = 0; c < DIM; c++) {
				if (row.charAt(c) == '*') { blocked[r][c] = true; }
			}
		}
 
		searchQueens(0);
 
		System.out.println(validNum);
	}
 
	private static void searchQueens(int c) {
		if (c == DIM) {
			// Ya llenamos todas las filas: incrementamos y volvemos
			validNum++;
			return;
		}
 
		for (int r = 0; r < DIM; r++) {
			boolean row_open = !rowsTaken[r];
			boolean diag_open = !diag1[r + c] && !diag2[r - c + DIM - 1];
			if (!blocked[r][c] && row_open && diag_open) {
				// Se ocuparon una fila y dos diagonales
				rowsTaken[r] = diag1[r + c] = diag2[r - c + DIM - 1] = true;
				searchQueens(c + 1);
				// Y ahora ya no lo están
				rowsTaken[r] = diag1[r + c] = diag2[r - c + DIM - 1] = false;
			}
		}
	}
}
DIM = 8
 
blocked = [[False for _ in range(DIM)] for _ in range(DIM)]
for r in range(DIM):
	row = input()
	for c in range(DIM):
		blocked[r][c] = row[c] == "*"
 
rows_taken = [False] * DIM
# Indicadores de las diagonales de abajo-izquierda a arriba-derecha
diag1 = [False] * (DIM * 2 - 1)
# Indicadores de las diagonales de abajo-derecha a arriba-izquierda
diag2 = [False] * (DIM * 2 - 1)
 
valid_num = 0
 
 
def search_queens(c: int = 0):
	global valid_num
 
	if c == DIM:
		# Ya llenamos todas las filas: incrementamos y volvemos
		valid_num += 1
		return
 
	for r in range(DIM):
		row_open = not rows_taken[r]
		diag_open = not diag1[r + c] and not diag2[r - c + DIM - 1]
		if not blocked[r][c] and row_open and diag_open:
			# Se ocuparon una fila y dos diagonales
			rows_taken[r] = diag1[r + c] = diag2[r - c + DIM - 1] = True
			search_queens(c + 1)
			# Y ahora ya no lo están
			rows_taken[r] = diag1[r + c] = diag2[r - c + DIM - 1] = False
 
 
search_queens()
print(valid_num)

Problemas

HechoFuenteNombreDificultadTagsSolución
Bronze★ Air Cownditioning IINormalComplete Search, Recursion, SubsetsSolución
Bronze★ Livestock LineupNormalComplete Search, Recursion, PermutationSolución
BronzeBack and ForthNormalComplete Search, RecursionSolución
CCCTwenty-fourNormalComplete Search, PermutationSolución
CSESBeautiful Permutation IINormalComplete Search, PermutationSolución
CF★ Three LogosDifícilComplete Search, Permutation, SubsetsSolución
BronzePrinting SequencesMuy difícilComplete Search—

Hay más problemas en el enlace de CP2 de arriba o en USACO Training . Sin embargo, este tipo de problemas aparece mucho menos que antes.

Pregunta 1/1

¿Para qué tamaño de nn podríamos esperar una solución que recorra todos los subconjuntos de un arreglo de longitud nn en un tiempo razonable?

Pregunta 1/1

¿Para qué tamaño de nn podríamos esperar una solución que recorra todos los subconjuntos de un arreglo de longitud nn en un tiempo razonable?

Pregunta 1/4

¿Cuál es la complejidad temporal del siguiente código?vector<int> perm(n); iota(begin(perm), end(perm), 1); do { // procesar perm } while (next_permutation(begin(perm), end(perm)));
Búsqueda completa básicaIntroducción al ordenamiento