tablero solucion reinas reglas recursividad que programa problemas problema paralelo mil las jugar iterativo geneticos genetico explicacion dev cuatro consiste con algoritmos algoritmo java language-agnostic recursion n-queens

java - solucion - Problema de 8 reinas usando recurrencia de retroceso



programa en c 8 reinas (5)

He estado trabajando en el problema de las 8 reinas pero me he quedado atascado. No quiero codigo Me encantaría la orientación y las instrucciones para comprender cómo resolver este problema utilizando la recursividad de retroceso.

El programa debe enumerar todas las soluciones al problema de N-queens dibujando la ubicación de las reinas en ASCII como las dos soluciones aquí .

Mi pseudocódigo hasta ahora es:

void queen(int n){ for( int i = 0; i < n; i++){ place queen[ i ] on row i; for(int j = 0 ; j < n ; j++){ if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] && queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] && queen[ i ] is not on the same minor diagonal with queen[0] through queen[ i -1 ] ) { print ''Q ''; } else{ print ''* ''; } System.out.println(); } System.out.println(); } }

No hay ninguna recursividad de retroceso en mi pseudocódigo porque no sé cómo hacerlo.

Cualquier ayuda es muy apreciada. Sin código, por favor.

(Actualización en respuesta a Nemo):

solver(int n, Board b){ for(int i = 0; i < b.length; i++){ place queen in column i; for(int j = 0; j < b.length; j++){ change b; solver(n+1,changed b); } } }

¿Es correcto?

(Actualización 2):

solver8(board /* with queens presented in first 7 columns */){ // place a queen in the 8th column; for(each possible placement of the queen in column 8 or in other words int i = 0; i < board.length; i++ ){ place the queen and print the board } } solver7(board /* with queens presented in first 6 columns */){ // place a queen in the 7th column; for(each possible placement of the queen in column 7 or in other words int i = 0; i < board.length; i++ ){ solver8(board with queens placed in first 7 columns); } } solver6(board /* with queens presented in first 5 columns */ ){ // place a queen in the 6th column; for(each possible placement of the queen in column 6 or in other words int i = 0; i < board.length; i++ ){ solver7(board with queens presented in first 6 columns); } }

y así sucesivamente hasta

solver1(1, empty board){ for(int i = 0; i < board.length; i++){ place queen in row[i] of column 1; solver2(board with queen in row[i] of column 1); } }

Actualización 3 (Editado):

private int numberOfQueens = 8; solver(int n, Board b){ for(int r = 0; r < b.length; r++){ place queen in row[r] of column[n]; if(n == numberOfQueens){ print the board; return; } else{ solver(n+1, board with queen in row[r] of column[n]); } } } }

El propósito de usar recursión para este tipo de problemas es que te permiten pensar en términos de "ahora he colocado k reinas; ¿cómo puedo colocar las restantes si el número total de reinas es n ?" Entonces, la función recursiva debería tomar dos parámetros: el número objetivo de reinas y el número de reinas colocadas hasta el momento. Al escribir la función, su objetivo es, ante todo, probar diferentes formas de colocar la k- ésima reina. Pero cuando ha seleccionado una posible ubicación y la ha encontrado válida, debe colocar las reinas n - k - 1 restantes. ¿Cómo podemos hacer esto? La respuesta: recursión! Llame a la función (desde dentro) con el parámetro k - 1 para indicar que desea colocar las reinas K - 1 restantes. Siempre que agote todas las posibilidades (o descubra que ninguna es posible), simplemente regrese de la función; luego volverá a la llamada a la función anterior (por ejemplo, la que intenta colocar la k- ésima reina).

Edición: también necesitará crear una matriz bidimensional para representar el estado actual de su placa; esta matriz debe enviarse como un parámetro adicional a la función recursiva o mantenerse como un campo de la clase que contiene el método.

En cuanto al retroceso, esto se logra simplemente asegurándose de que la función a la que se llama con k + 1 elimine la k + 1ra reina del tablero antes de regresar; esto esencialmente dice "Ahora hemos (sin éxito) probado todas las formas de colocar el resto de las reinas, en función de las posiciones de las k queens que ya se han colocado . Ninguna de ellas tuvo éxito, así que ajuste las posiciones de la primera k reinas (que se realizarán con la función que se llamó con k , y la función que llamó a esa función, y así sucesivamente) e intente nuevamente ".

Pon la primera dama en [0] [0], luego encuentra un lugar para la segunda. digamos que encontraste una ir a la siguiente, y así sucesivamente. Asumiendo que su quinta reina no puede colocarse en ningún lugar de la quinta columna o fila (lo que usted siga). Regrese al 4 y busque otro lugar para eso. Luego ve a la 5ª vez. Dicen que estás en la 8ª y no hay plazas disponibles. Ir al 7mo y todavía nada allí. Seguirás retrocediendo hasta el 2º y encontrarás un lugar para el 2º nuevamente, y pasarás al 3er. Tiene sentido...

En términos generales, una búsqueda recursiva de retroceso se parece a esto:

// On input, s represents a valid State up to depth d-1 sub do_it(int d, State s) if (d == MAX_DEPTH+1) // State s represents an answer! Print it and return. else (augment s to make it valid for depth d) for each augmented_s do_it(d+1, augmented_s) end for end if end sub // top level do_it(0, empty_state)

Tenga en cuenta que para un s válido válido hasta la profundidad d-1 , podría haber múltiples formas de aumentarlo a un estado válido hasta la profundidad d . La idea es llamarte a ti mismo con cada uno de ellos.

Para este problema, el "estado" es el tablero. La profundidad "d-1" podría significar que las primeras columnas d-1 están ocupadas. Los estados legalmente aumentados serían aquellos con una reina en la columna d tal que no pueda ser capturada.

[actualizar]

Aquí hay otra manera de verlo. Trabaja el problema al revés.

Supongamos que le pido que escriba una función simple llamada solver8() . Esta función toma como entrada un tablero con reinas ya presente en las primeras 7 columnas . Todo lo que tiene que hacer es tomar esa tabla, encontrar todas las formas de agregar una reina a la octava columna e imprimir esas tablas. ¿Crees que podrías escribir esta función? Bueno; Escribelo.

Ahora supongamos que le pido que escriba una función casi tan simple como solver7() . Esta función toma como entrada un tablero con reinas ya presentes en las primeras 6 columnas . Todo lo que tiene que hacer es tomar esa tabla, encontrar todas las formas de agregar una reina a la 7ma columna, y pasar cada una de esas tablas como un argumento para solver8() . ¿Podrías escribir esta función?

Ahora supongamos que le pido que escriba otra función llamada solver6() . Como entrada, se necesita un tablero con reinas presentes en las primeras 5 columnas. Todo lo que tiene que hacer es tomar esa tabla, encontrar todas las formas de agregar una dama a la sexta columna, y luego pasar cada una de esas tablas a solver7() .

Y así sucesivamente, hasta que lleguemos a solver1() . Éste toma un tablero vacío, encuentra todas las formas de colocar una reina en la primera columna, y pasa cada una de esas tablas a solver2() .

Acaba de escribir 8 funciones que juntas resuelven el problema de las 8 reinas. Si esto no tiene sentido, escríbalo como 8 funciones y mírelo hasta que lo haga.

Ahora, si observas todas estas funciones, verás que son bastante similares. Entonces, en lugar de escribir solver8, solver7, solver6, ..., solver1, escribes una sola función:

solver(int n, Board b)

... tal que el solucionador (1, b) es lo mismo que solver1 (b), el solucionador (2, b) es lo mismo que solver2 (b), ..., y el solucionador (8, b) es lo mismo que solucionador8 (b). Y en lugar de solver2 (...) llamando a solucionador3 (...), por ejemplo, solo tendrás solucionador (2, ...) de llamadas (3, ...). Una función en lugar de 8, pero haciendo lo mismo.

Descubrirá muy rápidamente que el código final es más limpio si comienza con un solver9() que solo toma una tabla completamente poblada y la imprime, y tiene que solver8() llamar eso.

Espero que esta solución ayude

Los puntos principales son

1. Recursion simple a bajo

2. IsValid position 2.1 cross Queen encontrada en la misma columna como

* *

2.2 cruz que la reina encontró diagonalmente como

*-- --- --*

o

--* --- *--

Código:

package queenproblem; public class QueenProblem { int numQueens[];// hold columns postion int numQueen; QueenProblem(int noOfQueens) { this.numQueen = noOfQueens; numQueens = new int[noOfQueens]; } public static void main(String[] args) { new QueenProblem(8).solveProblem(); } public void solveProblem() { arrange(0); } // recursive Function void arrange(int rowIndex) { // 1.to check valid Postion of not. // 2. to check all Queens postion is found or not. for (int i = 0; i < numQueen; i++) { if (isValid(rowIndex, i)) { numQueens[rowIndex] = i;// save col index if (rowIndex == numQueen - 1) { printsBoard(); } else { arrange(rowIndex + 1); } } } } private void printsBoard() { for (int i = 0; i < numQueen; i++) { for (int j = 0; j < numQueen; j++) { if (numQueens[i] == j) { System.out.print(" * "); } else System.out.print(" - "); } System.out.println(); } System.out.println(); } boolean isValid(int rowIndex, int colIndex) { for (int i = 0; i < rowIndex; i++) { // on the save columns if (numQueens[i] == colIndex) return false; if ((i - rowIndex) == (numQueens[i] - colIndex)) return false; if ((i - rowIndex) == (colIndex - numQueens[i])) return false; } return true; } }

92 Posibles soluciones a 8 Queens Problema:

* - - - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - * - - - - - - - - - - - - * - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - - * - - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - * - - - - - - - - - - - * - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - * - - - - - - - - - - - * - - - - - - - - - * - - * - - - - - * - - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - * - - - - - - - - - - * - - - - - * - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - * - - - - - - - - - - - - - * - - - - - * - - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * * - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - - - - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - * - - - - - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - - * * - - - - - - - - - - - - - * - - - - * - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - * - - - - - - - - - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - - * - - - - - - - - - - - - - - * - - - * - - - - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - - * - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - * - - - - - - - - - * * - - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - * - - - - - - - - - - * - - - - - - - - - * * - - - - - - - - - - - * - - - - - - - - - * - - * - - - - - - - - - * - - - - - - * - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - * - - * - - - - - - - - - - - - - * - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - * - - - - * - - - - - - - - - - - * - - - - - - - - - - * - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - - * - - - - - * - - * - - - - - - - - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * * - - - - - - - - - - - * - - - - - - * - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - * - - - - - - - - - - * - - - - - * - - - - - - - - - - - - * - - - - - * - - - * - - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - - - * - - - - - - - - - * - - - - - - - - - * - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - * - - - - - - - - - - - - - - * - - - - * - - - - * - - - - - - - - - - - * - - - - * - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - - * * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - - - - - * - - - - - - - - - - - * * - - - - - - - - - - - * - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - * - - - - - - - - - - - * - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - - - * - - - * - - - - - - - - - * - - - * - - - - - - - - - - - - - - * - - - * - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - * - - - * - - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * * - - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - * - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - * - - * - - - - - - - - - * - - - - - - - - - - - * * - - - - - - - - - * - - - - - - - - - - * - - - - - - * - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - - - * - - - - * - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - - - - - * - - - * - - - - - - - - * - - - - - - - - - * - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - - - * - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - - * - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * - - - * - - - - * - - - - - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - - - - - * - - - * - - - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - * - - - * - - - - - - - - - - - - * - * - - - - - - - - - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - - - - - * - - - * - - - - - * - - - - - - - - - - - - * - - - - - * - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - - - - - * - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * * - - - - - - - - - - * - - - - - * - - - - - - - - - - - - * - - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - * - - - - - - - - - - - * * - - - - - - - - - - - * - - - - - - - - * - - - - * - - - - - - - - - - - * - - * - - - - - - - - - - - - - * - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - - - - - - * - - - - * - - - - * - - - - - - - - - - - - - - * - * - - - - - - - - - - * - - - - - - - - * - - - - - * - - - - * - - - - - - - - - - - * - - - - - - - - - - * - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - * - - - - - * - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - * - * - - - - - - - - - - - - - - * - * - - - - - - - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - * - - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - * - - * - - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - - - * - - - - * - - - - - - - - - * - - - * - - - - - * - - - - - - - - - - - - * - - - - - - - - - * - - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - - * * - - - - - - - - - * - - - - - - - - - - * - - - - - - - - * - - - - * - - - - - * - - - - - - - - - - - - - * - - - - - * - - * - - - - - - - - - * - - - - - - - - - * - - - - - - - - - * - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - * - - - - - - - - - - - * - * - - - - - - - - - * - - - - * - - - - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - * - - - - - - - - - * - * - - - - - - - - - - * - - - - - * - - - - - * - - - - - - - - - - - - - * - - - - * - - - - - - - - - * - - - - - - - - - * - - * - - - - - * - - - - - - - - - - - - * - - - * - - - - - - - - - - * - - - - - - - - - * - - - - * - - - - - - - - - - - * - - - * - - - - * - - - - - - - - - * - - - - - - - - - - * - - - * - - - - - - - - - - - - * - - - - - * - - -