suppose we want to solve the n-queens problem by uninformed search(either depth-
ID: 3617350 • Letter: S
Question
suppose we want to solve the n-queens problem by uninformed search(either depth-first , or breadth-first , or depth-limited with1<= cutoff <= n , or iterative deepening ). remember,uninformed search methods cannot employ any constraint violationtest.a) formulate the problem as a search problem by specifying the: 1- the data structure for a state . 2- the initial state(must be an instantiation of theabove). 3- the successor function . 4-the goal test. 5-the path cost.
b) argue why (or why not ) you would want to use each of theabove 4 uninformed search algorithms in thisproblem ?
c) which of these algorithms would you most prefer to use?
d) suppose that we want to solve the above formulation of then-queens problem by A* searchprecisely define the cost function g(n) and the heuristic functionh(n) , such that A* expands thesame set of nodes as backtracking search would . notice that as an informed search algorithms, A* can perform constraint violation tests.
************ Thanks****************
a) formulate the problem as a search problem by specifying the: 1- the data structure for a state . 2- the initial state(must be an instantiation of theabove). 3- the successor function . 4-the goal test. 5-the path cost.
b) argue why (or why not ) you would want to use each of theabove 4 uninformed search algorithms in thisproblem ?
c) which of these algorithms would you most prefer to use?
d) suppose that we want to solve the above formulation of then-queens problem by A* searchprecisely define the cost function g(n) and the heuristic functionh(n) , such that A* expands thesame set of nodes as backtracking search would . notice that as an informed search algorithms, A* can perform constraint violation tests.
************ Thanks****************
Explanation / Answer
Abstract
The purpose of this research is to explore thecomplexities of the N-Queens problem using uninformed searchesincluding the average branching factor, the size of the maximumsolvable puzzle, and to find interesting patterns for furtherresearch. Methods used included continued expressions,breadth-first search, and depth-first search. It was found that themodels differed from the actual result by a constant factor andthat there is probably no limit to the maximum-size N-Queenspuzzle. Possible areas for further research are the relationshipbetween the first lexicographic solution and the totient of n andthe existence of greedy solutions other than n = 1 and n =5.
Problem
The n-Queens problem is a classic puzzle where nqueens are to be placed on an n by n "chessboard" such that noqueen can attack any other queen. The goal of this research is towrite a program to find solutions to the n-Queens problem, andtheoretically and experimentally compute the branching factor andlimits on the size of the problem.
Hypothesis
Solution Validation
The general algorithm used in my programs is to determine allplaces on each column where a queen could be placed then try eachone in turn and repeat the procedure for the next column. This canfind all possible solutions to the n-Queens problem in a finiteamount of time for the following reasons:
• No two queens could ever be placed in the samecolumn.
• The order in which the queens are placed is notimportant.
• The maximum depth of the problem is limited to n. Inother words, after placing n queens, there are definitely no moreways to place a queen on the board. The same would be true forrooks.
• There are no cycles in the solution set. Placing a queenwill never change the position of other previously placedqueens.
To prove to yourself that these criteria are sufficient toprove that all solutions are found by such an algorithm, imagine asolution that was missed. This solution must have one queen in eachcolumn and the queens could have been placed in anyorder.
Therefore, the queens could have been placed from left to rightby column and would have been found by the algorithm.
Calculating the Average Branching Factor from theResults
First, it is important to note that the average branchingfactor is not the same as the average of the branching factors foreach node. This can be shown with a simplecounterexample.
• Take for example the n = 4 solution to the n-Queensproblem. 17 nodes are generated in 4 generations, including theinitial state.
Generation
0
1
2
3
4
1
0
2
0
1
1
1
0
4
1
1
1
0
2
0
1
0
Generation
0
1
2
3
4
1
0
2
0
1
1
1
0
4
1
1
1
0
2
0
1
0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.