Problema de las Reinas

El siguiente programa muestra como resolver el problema de las 8 reinas, generalizado para cualquier tamaño de tablero. El problema en sí trata de encontrar una forma de posicionar n reinas en un tablero de ajedrez de tamaño n x n, de tal manera que ninguna de las reinas ataque a ninguna de las otras. Una reina ataca todas las casillas que se encuentren en la misma fila, en la misma columna, o en las diagonales de la casilla en que está ubicada.

Este problema utiliza un esquema igual al utilizado en la solución del problema del salto del caballo, modelando el tablero como una matriz de n x n y utilizando un enfoque de backtracking para marcar una casilla, generar una lista de las siguientes casillas que no están amenazadas y revisar dicha lista en forma recursiva; si no se llega a la respuesta correcta, se devuelve el proceso para continuar con las siguiente casillas de la lista.

public class ProblemaReinas {
    final int numFilas;
    final int numColumnas;
    int[][] tablero;
    int     contador;

    public ProblemaReinas(int nf) {
        numFilas    = nf;
        numColumnas = nf;
        tablero     = new int[nf][nf];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                if(tablero[i][j]>0) System.out.printf("  %2d  |", tablero[i][j]);
                else System.out.printf("      |", tablero[i][j]);
            }
            System.out.println();
            for(int j=0; j<tablero[i].length; j++) System.out.print("------+");
            System.out.println();
        }
    }

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas) return true;
            int[][] posibles = buscarPosibles();
            for(int i=0; i<posibles.length; i++) {
                if(resolverProblema(posibles[i][0], posibles[i][1], num+1)) return true;
            }
            tablero[f][c]=0;
            return false;
    }

    int[][] buscarPosibles() {
        int[][] resp = new int[numFilas*numColumnas][2];
        int[] sumaFilas = new int[numColumnas];
        int[] sumaColumnas = new int[numFilas];
        int     pos  = 0;
        for(int i=0; i<numFilas; i++) {
            for(int j=0; j<numColumnas; j++) {
                if(tablero[i][j]>0) {
                    sumaFilas[i]++;
                    sumaColumnas[j]++;
                }
            }
        }
        for(int i=0; i<numFilas; i++) {
            if(sumaFilas[i]>0) continue;
            for(int j=0; j<numColumnas; j++) {
                if(sumaColumnas[j]>0) continue;
                if(i>0 && j>0             && tablero[i-1][j-1] > 0) continue;
                if(i>0 && j<numColumnas-1 && tablero[i-1][j+1] > 0) continue;
                if(i<numFilas-1 && j>0    && tablero[i+1][j-1] > 0) continue;
                if(i<numFilas-1 && j<numColumnas-1 && tablero[i+1][j+1] > 0) continue;
                resp[pos][0]=i;
                resp[pos][1]=j;
                pos++;
            }
        }
        int[][] tmp = new int[pos][2];
        for(int i=0; i<pos; i++) { tmp[i][0] = resp[i][0]; tmp[i][1]=resp[i][1]; }
        return tmp;
    }

    boolean esValido(int f, int c) {
        if(f<0 || f>numFilas-1 || c<0 || c>numColumnas-1) return false;
        if(tablero[f][c]!=0) return false;
        return true;
    }

    public static void main(String[] args) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas pr = new ProblemaReinas(8);
        pr.resolverProblema(filaInicial, colInicial,1);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}