Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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?
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.
In the case of the 8 queens problem, there are 4,426,165,368 possible configurations (so you will likely not be able to draw this graph).
