ASSIGN In this assignment you will use the given code to solve the Map Coloring, and...

Transcribed Image Text:

ASSIGN In this assignment you will use the given code to solve the Map Coloring, and the n-Queens problems as discussed in the lectures. Please see the lecture slides and the Chapter-6 of the textbook for details on encoding and solving CSPs. To understand the assignment task and the installation of required libraries, please read the following sections carefully: 1) Overview of the CSP Solver Library For this assignment, we will be using a library called simpleai that is available at: https://github.com/simpleai-team/simpleai You can read the documentation on the CSP solver built into the library from this link: satisfaction_problems.html https://simpleai.readthedocs.io/en/latest/constraint Also, you have been given a python code file called backtracking.py that shows how to use the CSP solver of the library with a complete example. Please study the code and the example carefully to understand how to encode a problem as a CSP in this solver. You should also execute this code to make sure that all the library requirements are correctly installed on your system so that you can work on your assignment. The next section gives details on how to install and run this file at your PC. 2) Installation of simpleai Library 1. Make sure that Python is installed on your PC. For installation details for Windows, please follow the steps given in the following link: o https://www.liquidweb.com/kb/how-to-install-python-on-windows/ o If you use any Linux distro, then note that Python is installed by default on all Linux distros. For confirmation, see above link on how to verify python installation. 2. Make sure that pip is installed. For installation instructions for Windows, please see and follow steps given at: o https://www.liquidweb.com/kb/install-pip-windows/ o In Linux, you can invoke pip at the python prompt. See above link for details. 3. To install the simpleai library, open Command Prompt (Windows) or Terminal (Linux), and type: python This will start the Python prompt. At this prompt, type: pip install simpleai This will install the simpleai library and all prerequisites on your PC. 3) How to Use the simplear Library You have been given a file called backtracking.py. Study the code carefully as this code demonstrates how to call the backtracking search algorithm that uses the AC-3 algorithm for arc consistency and the MRV (Most Constrained Variable) and LCV (Least Constraining Value) heuristics to solve a given CSP problem. A simple example is already given to you that shows how to solve a three variable CSP problem. Please see the code for the details. Note carefully how variables, domain, and the constraints are defined in the problem. Also, note that constraints need to be defined as explicit constraints. In the example, three different constraints are defined that are to be applied on the three variables. To make sure that you have installed everything correctly, you should run and see the output of this code. 4) How to Write your Code Solution? As mentioned above, you will need to define explicit constraints in this library for solving your problems. Also note that to write the assignment solution, you will edit this code file and write your assignment solution. The lines of the code that you should not change are: a) The top two import statements. b) The last three lines that demonstrate how to call the backtracking search with all heuristics to solve the problem and print the CSP solution. 5) What Problems to Solve for this Assignment? You will need to solve two problems using the above code and the simpleai library: Map Coloring problem and the n-Queens problem. For a review of the formulation of these CSP problems, please see Chapter-6 and the lecture slides. a) Map Coloring Problem [15 Points] NT For the given map at the right, we need to assign a color to each variable so that no two neighboring variables have the same color. We have a total of seven variables, and the domain having {RED, GREEN, BLUE} values. WA NSW) b) n-Queens Problem [15 Points] For this problem, solve the n-Queens problem using n = 5. In this problem you would need to place a Queen in each row of a 5 x 5 table so that no two Queens attack each other. SA T ASSIGN In this assignment you will use the given code to solve the Map Coloring, and the n-Queens problems as discussed in the lectures. Please see the lecture slides and the Chapter-6 of the textbook for details on encoding and solving CSPs. To understand the assignment task and the installation of required libraries, please read the following sections carefully: 1) Overview of the CSP Solver Library For this assignment, we will be using a library called simpleai that is available at: https://github.com/simpleai-team/simpleai You can read the documentation on the CSP solver built into the library from this link: satisfaction_problems.html https://simpleai.readthedocs.io/en/latest/constraint Also, you have been given a python code file called backtracking.py that shows how to use the CSP solver of the library with a complete example. Please study the code and the example carefully to understand how to encode a problem as a CSP in this solver. You should also execute this code to make sure that all the library requirements are correctly installed on your system so that you can work on your assignment. The next section gives details on how to install and run this file at your PC. 2) Installation of simpleai Library 1. Make sure that Python is installed on your PC. For installation details for Windows, please follow the steps given in the following link: o https://www.liquidweb.com/kb/how-to-install-python-on-windows/ o If you use any Linux distro, then note that Python is installed by default on all Linux distros. For confirmation, see above link on how to verify python installation. 2. Make sure that pip is installed. For installation instructions for Windows, please see and follow steps given at: o https://www.liquidweb.com/kb/install-pip-windows/ o In Linux, you can invoke pip at the python prompt. See above link for details. 3. To install the simpleai library, open Command Prompt (Windows) or Terminal (Linux), and type: python This will start the Python prompt. At this prompt, type: pip install simpleai This will install the simpleai library and all prerequisites on your PC. 3) How to Use the simplear Library You have been given a file called backtracking.py. Study the code carefully as this code demonstrates how to call the backtracking search algorithm that uses the AC-3 algorithm for arc consistency and the MRV (Most Constrained Variable) and LCV (Least Constraining Value) heuristics to solve a given CSP problem. A simple example is already given to you that shows how to solve a three variable CSP problem. Please see the code for the details. Note carefully how variables, domain, and the constraints are defined in the problem. Also, note that constraints need to be defined as explicit constraints. In the example, three different constraints are defined that are to be applied on the three variables. To make sure that you have installed everything correctly, you should run and see the output of this code. 4) How to Write your Code Solution? As mentioned above, you will need to define explicit constraints in this library for solving your problems. Also note that to write the assignment solution, you will edit this code file and write your assignment solution. The lines of the code that you should not change are: a) The top two import statements. b) The last three lines that demonstrate how to call the backtracking search with all heuristics to solve the problem and print the CSP solution. 5) What Problems to Solve for this Assignment? You will need to solve two problems using the above code and the simpleai library: Map Coloring problem and the n-Queens problem. For a review of the formulation of these CSP problems, please see Chapter-6 and the lecture slides. a) Map Coloring Problem [15 Points] NT For the given map at the right, we need to assign a color to each variable so that no two neighboring variables have the same color. We have a total of seven variables, and the domain having {RED, GREEN, BLUE} values. WA NSW) b) n-Queens Problem [15 Points] For this problem, solve the n-Queens problem using n = 5. In this problem you would need to place a Queen in each row of a 5 x 5 table so that no two Queens attack each other. SA T

Answer rating: 100% (QA)

NT solution WA a Map colooring problem csp variables WA NT Q NS... View the full answer