N-Queens program using LinkedStack instead of using recursion

user_14635410 0
Viewed 203

I have done a lot of researches but all of them were either recursion or not what I'm currently looking for. I'm trying to create an N-Queens program using LinkedStack instead of recursion, LinkedStack will take object NQueen, not just a bunch of integer. This is my first time experience doing this, even though I understand the algorithm but I just have no clue how to implement it. Like how can I compare a queen to the last queen in the stack, and how do they store each position that fit that 2 queens don't attack each other. I'm so lost, if possible some codes how to implement it would be great.

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;
   }     
   
}

This is my return itemAt(int n) that I implement in LinkedStack. Thank you for your help.

/**
   *
   * @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();
  }
data-structures java
1 Answers

From your code I really do not understand what is your question here. Here I have solved the n-queen problem by using different variations of hill-climbing search algorithm. From this code you might get the idea about how you can store the board state and the queen state.

As you want to solve the problem using stack based recursion, here is the process you should follow:

- 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)

This is just the steps that you need to follow to solve the problem. Please comment if you found it hard to follow this process.

user_13798170
Related