Saber todas las combinaciones posibles de un tablero

[xKuZz]

Para resolver problemas de este tipo hay muchas técnicas variadas de búsqueda en espacio de estados que dan solución al problema (búsquedas en anchura, profundidad, algoritmos genéticos) o técnicas algorítmicas de backtracking o branch & bound suelen ser útiles. Probablemente backtracking sea la más apropiada para el problema.

No obstante, el número de tableros posibles para 4 fichas si consideramos una representación con un vector de 4 enteros en el que el índice es la fila y el valor es la columna y en los valores aparece cada valor del 1 al 4 una única vez se reduce a comprobar todas las permutaciones de esos cuatro números y determinar cuáles son factibles, y 4! = 4 * 3 * 2 = 24 tableros se comprueba en un momentillo. Por tanto hacerlo por fuerza bruta no es ningún problema. En C++:

Código C++:

#include <algorithm>
#include <iostream>
#include <set>
#include <tuple>
#include <vector>
 
using namespace std;
 
bool esFactible(const vector<int>& fichas) {
    set<int> diagonal_descendente;
    set<int> diagonal_ascendente;
    bool unico = true;
    for (unsigned i = 0; i < fichas.size(); ++i) {
        // Si dos valores fila - columna coinciden indican que estamos en
        // la misma diagonal descendente
        tie(ignore, unico) =diagonal_descendente.insert(i-fichas[i]);
        if (!unico)
            return false;
 
        // Si dos valores fila + columna coinciden indican que estamos en
        // la misma diagonal ascendente
        tie(ignore, unico) = diagonal_ascendente.insert(i+fichas[i]);
        if (!unico)
            return false;
    }
 
    // Si no ocurre nada de eso es una solución porque no hay encuentros
    // diagonales y la modelización del espacio de estados evita que haya
    // columnas o filas iguales
    return true;
}
 
int main() {
    // Representación del tablero
    // Índice -> Filas -1
    // Valor -> Columnas
    vector<int> fichas {1, 2, 3, 4};
 
    // A permutar
    do {
        if (esFactible(fichas)) {
            cout << "SOLUCION" << endl;
            for (unsigned i = 0; i < fichas.size(); ++i)
                cout << "Fila " << i+1 << "\t Columna" << fichas[i] << endl;
            cout << endl << endl;
        }
    } while (next_permutation(fichas.begin(),fichas.end()));
 
}
 

Que me devuelve como solución dos únicos tableros que cumplen eso si no lo he hecho mal que creo que no.

Fila 1 Columna2
Fila 2 Columna4
Fila 3 Columna1
Fila 4 Columna3


SOLUCION
Fila 1 Columna3
Fila 2 Columna1
Fila 3 Columna4
Fila 4 Columna2

Hay un problema muy similar a este que es el problema de las 8 reinas y que se resolvería de la misma manera (eso sí la fuerza bruta cuanto más grande es el tablero menos recomendable). Infórmate sobre éstos que te he comentado y te dará para rato y una manera de encontrar la solución más apropiada que comprobarlo todo y aunque este problema haya sido resuelto aquí con esta fuerza bruta cutre la búsqueda en el espacio de estados en un tema denso e interesante si te gustan este tipo de problemas.