COMP-424: Artificial intelligence, Fall 2023 Homework 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP-424: Artificial intelligence, Fall 2023
Homework 1
Due on myCourses Thursday Oct 5, 9:00pm.
General instructions.
• This is an individual assignment. You can discuss solutions with your classmates, but should only exchange
information orally, or else if in writing through the discussion board on Ed. All other forms of written exchange are prohibited.
• Unless otherwise mentioned, the only sources you should need to answer these questions are your course notes, the textbook, and the links provided. Any other source used should be acknowledged with proper referencing style in your submitted solution.
• For each problem, you can solve manually, or write a program to help you. You can use a programming language of your choice. You can modify code from other sources if you provide adequate citation; this cannot be code from other students in the class.
• Submit a single pdf of your responses through myCourses. You can scan-in hand-written pages (recommend to learn your phone’s scanning feature). If necessary, learn how to combine many pdf files into one.
Question 1: Search algorithm properties [30]
(Adapted from Russell & Norvig)
For all of the following, answer the analytical question using a similar level of rigor as was provided in the class
slides. Always assume positive costs for every operation. Reason about the most general case you can imagine, but if you require them, write out your assumptions at the top of your solution.
a) Describe a state space in which iterative deepening search performs much worse than depth-first search (for example, 0(n2) vs 0(n)).
Prove each of the following statements, or give a counterexample:
b) Breadth-first search is a special case of uniform-cost search.
c) Best-first search is optimal in the case where we have a perfect heuristic (i.e., ℎ(n) = ℎ∗ (n), the true cost to the closest goal state).
d) Suppose there is a unique optimal solution. Then, A* search with a perfect heuristic will never expand nodes that are not in the path of the optimal solution.
e) A* search with aheuristic which is admissible but not consistent is complete.
Question 2: Constraint satisfaction [30]
Consider the following problem:
You want to solve a simplified 4x4 version of the Sudoku game with the following grid configuration:
Each row, column and 2x2 square rooted in one of the 4 corners should contain the digits “1”, “2”, “3”, “4” exactly once.
a) Formulate this problem as a CSP. List the variables, their domains, and the constraints. Draw the constraint graph of a general 2x2 Sudoku game (that is, do not consider the pattern of filled in numbers in the example).
b) Show the first ten steps of backtracking search on the sample provided, where you order the variables in increasing order first by row, then by column (in English reading-order), and the values from lowest to highest (1 to 4). Recall that backtracking search uses a depth-first strategy to expand the search tree.
c) Show the first ten steps of backtracking search on this problem with one-step forward checking, with the same variable ordering.
Question 3: Code N-Queens [40]
Write a program, in a language of your choice, that solves the N-Queens constraint-satisfaction problem using a Local
Search method (Problem Definition PDF notes). You can use helper functions from the language you pick, and
libraries if you find them helpful for the problem setup, but you must code the core AI solution logic yourself. Submit your code as one file and write about your findings in max 1 page of typed report in your PDF submission file. We
will read your code but not run it - readability and commenting are important.
Use your code to answer the following required elements of the report:
a) Describe your solution in detail, using the language of Local Search. Do not copy your code in whole or in part. Rather give a concise intuitive explanation.
b) Print the solution of the largest N you managed as a list of N integers, zero-indexed and comma separated. Cth
entry having value R means the queen in col C is in row R. (e.g., the solution for N=4 shown on slide 88 is [2, 0, 3, 1]). If you manage the normal chessboard size, N=8, there will be no further impact on grades (but whoever
solves max N has the honor!)
c) What is the run-time complexity of your method, as a function of N? You can answer this by showing a table of N vs run-times or by attempting to write a big-oh expression. In either case, give an explanation referencing
elements of your code solution.
d) Did you encounter any local optima? Describe that situation and how you overcame it.
Hint: Our sample solution in Python is about 50 lines without comments. There are 4 kinds of constraints (rows, cols, diags parallel toy=x and diags parallel toy=-x). To code these:
• Use an array-like data structure with one int for each column, representing the row of each queen. This ensures we can never have two queens in the same column.
• Row constraints rule out duplicates in your array
• y=x diag constraints rule out pairs of queens sharing the same (row-col)
• y=-x diag constraints rule out pairs of queens sharing the same (row+col)
2023-11-24