Hice muchas investigaciones, pero todas fueron recursivas o no lo que estoy buscando actualmente. Estoy tratando de crear un programa N-Queens usando LinkedStack en lugar de recursividad, LinkedStack tomará el objeto NQueen, no solo un montón de enteros. Esta es mi primera experiencia haciendo esto, aunque entiendo el algoritmo, pero no tengo ni idea de cómo implementarlo. Por ejemplo, ¿cómo puedo comparar una reina con la última reina de la pila y cómo almacenan cada posición que encaja para que 2 reinas no se ataquen entre sí? Estoy tan perdido, si es posible, algunos códigos sobre cómo implementarlo serían geniales.
public class NQueen { private static int numSolutions; private int col; private int row; public int getCol() { return col; } public int getRow() { return row; } public void setCol(int num){ col= num; } public void setRow(int num) { row= num; } public NQueen(int newRow, int newColumn) { this.row = newRow; this.col = newColumn; } public void solve(NQueen Queen, int n ) { int current =0; LinkedStack<Object> stack = new LinkedStack<>(); stack.push(Queen); while(true) { while(current < n) { } } } public boolean conflict(NQueen Queen) { for(int i= 0; i < stack.size(); i++) { } //Check if same column or same diagonal return true; } }Este es mi artículo devuelto en (int n) que implemento en LinkedStack. Gracias por tu ayuda.
/** * * @precondition * 0 <= n and n < size( ). * @postcondition * The return value is the item that is n from the top (with the top at * n = 0, the next at n = 1, and so on). The stack is not changed * **/ public Object itemAt(int n) { int index = n; if ((n<0) && (n >= size())) { throw new EmptyStackException(); } int i = 0; while (i < n) { this.pop(); i++; } this.peek(); return peek(); }De su código, realmente no entiendo cuál es su pregunta aquí.Aquí he resuelto el problema de n-reina usando diferentes variaciones del algoritmo hill-climbing search . A partir de este código, puede tener una idea de cómo puede almacenar el estado del tablero y el estado de la reina .
Como desea resolver el problema utilizando la recursividad basada en pila, este es el proceso que debe seguir:
- initiate empty stack: st = {} - insert initial_board_state into stack: st.insert(initial_board_state) - initiate empty map to track the visited state: visited_map = {} - insert initial_board_state into the visited_map: visited_map.insert(initial_board_state) - while stack is not empty: - remove top element from the stack: current_board_state = stack.top() - if current_board_state is the goal_state: return found - generate all the next states from the current_board_state and loop over it: - if next_board_state is not in the visited_map: - insert next_board_state in the stack: st.insert(next_board_state) - insert next_board_state in the visited_map: visited_map.insert(next_board_state)Estos son solo los pasos que debe seguir para resolver el problema. Por favor comente si le resultó difícil seguir este proceso.