Answers.Body: <p>In general, the process of modelling a problem as a search problem consists in creating a graph which contains nodes, which represent the possible states in your problem, and edges, which represent the relations between these states (that is, you will have an edge between nodes <span class="math-container">$A$</span> and <span class="math-container">$B$</span> if it is possible to go from state <span class="math-container">$A$</span> to state <span class="math-container">$B$</span>, and vice-versa, in your problem).</p>
  
  <p>In the case of the 8 (or, in general, N) queens problem (or blocked 8 queens problem), the states are all possible configurations of the board (that is, all possible combinations of the positions of all the 8 queens). In the graph that represents this problem, you will have a node for all possible valid configurations, where a valid configuration is one that is allowed by the rules of the game. You will also have an edge between configurations (or states) <span class="math-container">$A$</span> and <span class="math-container">$B$</span> if you can go from state <span class="math-container">$A$</span> to state <span class="math-container">$B$</span>. For example, configurations where you have two queens on the same square or where you have a queen in a blocked area will not be represented in your graph as a node (or state).</p>
  
  <p>In the case of the 8 queens problem, you actually have more than one solution, so you will have more than one goal state (or configuration of the board). </p>
  
  <p>When using the BFS, the goal will then be to find a path from the initial configuration of the queens (that is, the initial state) to one of these <a href="https://en.wikipedia.org/wiki/Eight_queens_puzzle" rel="nofollow noreferrer">18 (or 12) goal states</a>.</p>
  
  <p>In the case of the 8 queens problem, there are <a href="https://en.wikipedia.org/wiki/Eight_queens_puzzle" rel="nofollow noreferrer">4,426,165,368 possible configurations</a> (so you will likely not be able to draw this graph).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-24T19:23:03.537Z
Answers.LastActivityDate: 2019-02-24T22:36:32.657Z
Answers.LastEditDate: 2019-02-24T22:36:32.657Z
Answers.UserDisplayName: nbro
Body: <p>The blocked N-queens is a variant of the N-queens problem. In the blocked N-queens problem, we also have a NxN chess board and N queens. Each square can hold at most one queen. Some squares on the board are blocked and can not hold any queens. Conditionality is that queens do not dare to attack each other. At the entrance to this problem are the queues and blocked areas. </p>
  
  <p>How do I model the blocked N queens problem as a search problem, so that I can apply search algorithms like BFS?</p>
  
Tags: <search><problem-solving><breadth-first-search>
Title: How do I model the blocked N queens problem as a search problem?
UserDisplayName: Tim
ThreadText: # How do I model the blocked N queens problem as a search problem?
  
  (Asked by: username_0 on 2019-02-24)
  
  The blocked N-queens is a variant of the N-queens problem. In the blocked N-queens problem, we also have a NxN chess board and N queens. Each square can hold at most one queen. Some squares on the board are blocked and can not hold any queens. Conditionality is that queens do not dare to attack each other. At the entrance to this problem are the queues and blocked areas.
  
  How do I model the blocked N queens problem as a search problem, so that I can apply search algorithms like BFS?
  
  **Tags:** search, problem-solving, breadth-first-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-24. Score: 1
  
  In general, the process of modelling a problem as a search problem consists in creating a graph which contains nodes, which represent the possible states in your problem, and edges, which represent the relations between these states (that is, you will have an edge between nodes $A$ and $B$ if it is possible to go from state $A$ to state $B$, and vice-versa, in your problem).
  
  In the case of the 8 (or, in general, N) queens problem (or blocked 8 queens problem), the states are all possible configurations of the board (that is, all possible combinations of the positions of all the 8 queens). In the graph that represents this problem, you will have a node for all possible valid configurations, where a valid configuration is one that is allowed by the rules of the game. You will also have an edge between configurations (or states) $A$ and $B$ if you can go from state $A$ to state $B$. For example, configurations where you have two queens on the same square or where you have a queen in a blocked area will not be represented in your graph as a node (or state).
  
  In the case of the 8 queens problem, you actually have more than one solution, so you will have more than one goal state (or configuration of the board).
  
  When using the BFS, the goal will then be to find a path from the initial configuration of the queens (that is, the initial state) to one of these [18 (or 12) goal states](https://en.wikipedia.org/wiki/Eight_queens_puzzle).
  
  In the case of the 8 queens problem, there are [4,426,165,368 possible configurations](https://en.wikipedia.org/wiki/Eight_queens_puzzle) (so you will likely not be able to draw this graph).
  
  
  ---
  
  