Please help with this artificial intelligence problem. Any coding should be on p
ID: 3744741 • Letter: P
Question
Please help with this artificial intelligence problem. Any coding should be on pseudocode and the graph a search tree. Thank you.
The goal of the 4-queens problem is to place 4 queens on a 4 rows 4 columns chessboard, such that no two queens attack each other. One solution to the 4 queens problem is shown in Figure 3. Please design a search based solution to solve the 4-queens problem. Your solution must include following four components a. Define state [0.5 pt] b. Define successor function [0.5 pt] c. Show state graph [0.5 pt] d. Show how to find solutions from state graph [0.5 pt] 01 Q2 Q3 Q4 Figure 3Explanation / Answer
Dear Student,
The problem is to place 4 queens on a chessboard so that no two queens are in the same row, column or diagonal ( ie attack each other).
How do we formulate this in terms of a state space search problem? The problem formulation involves deciding the representation of the states, selecting the initial state representation, the description of the operators, and the successor states. We will now show that we can formulate the search problem in several different ways for this problem
N queens problem formulation 1
States: Any arrangement of 0 to 8 queens on the board
Initial state: 0 queens on the board
Successor function: Add a queen in any square
Goal test: 4 queens on the board, none are attacked
The initial state has 16 successors. Each of the states at the next level have 15 successors, and so on. We can restrict the search tree somewhat by considering only those successors where no queen is attacking each other. To do that we have to check the new queen against all existing queens on the board. The solutions are found at a depth of 4.
N queens problem formulation 2
States: Any arrangement of 4 queens on the board
Initial state: All queens are at column 1
Successor function: Change the position of any one queen
Goal test: 4 queens on the board, none are attacked
If we consider moving the queen at column 1, it may move to any of the three remaining columns.
N queens problem formulation 3
States: Any arrangement of k queens in the first k rows such that none are attacked
Initial state: 0 queens on the board
Successor function: Add a queen to the (k+1)th row so that none are attacked.
Goal test : 4 queens on the board, none are attacked
Please give a thumbs up if you like this answer ! Happy Learning :)