辅导Hill Climbing编程、写作Python编程编程

” 辅导Hill Climbing编程、写作Python编程编程HW3: Hill ClimbingDue Thursday by 11am Points 100 Submitting a file upload File Types pyAvailable Sep 24 at 12am – Oct 2 at 11:59pm 9 daysSubmit AssignmentProgram GoalsDeepen understanding of state space generationPractice implementation of search algorithmsSummaryWeve introduced the 8-queens problem in class: place 8 queens on a chessboard such that no queen isattacking any other queen.A solution for an 8×8 board with state [2, 7, 3, 6, 0, 5, 1, 4]Recall that in the game of chess, queens attack any piece they can see (i.e., there is nothing betweenthe queen and the attacking Piece) in the same row, column, or diagonal.In this assignment, you will generalize this problem to a board of arbitrary (square) size and theequivalent number of queens and add a static point to the board. It means that at any time, there mustbe a queen on the static point. You only have to place the other N-1 queens on the board.Given the size of the board (N 0) and location of the static point (0 = static_x N and 0 = static_y N), you will implement a hill-climbing algorithm to solve the problem.2020/9/26 HW3: Hill Climbing httpss://canvas.wisc.edu/courses/205182/assignments/995441 2/6Program SpecificaonThe code for this program must be written in Python in a file called nqueens.py. You should onlysubmit one file with the name nqueens.py, and make sure it includes all functions needed. Do notsubmit a Jupyter notebook .ipynb file.Your state representation must be a list of N integers, 0-indexed, representing the row the queen isoccupying in each column (see figure above). For simplicity of representation, we will retain ourassumption that there is a single queen per column. When you generate the successor states, thereshould not be any states with two queens in the same column.Goal State 辅导Hill Climbing作业、写作Python编程There are multiple possible configurations for a goal state, defined as a state in which no queen isattacking any other queen per the rules above. One of your tasks will be to define an evaluation functionfor the states such that the Goal state has the lowest value (0) when the function is applied to it.FunconsFor this program you should write 5 Python functions:1. succ(state, static_x, static_y) — given a state of the board, return a list of all valid successor states2. f(state) — given a state of the board, return an integer score such that the goal state scores 03. choose_next(curr, static_x, static_y) — given the current state, use succ() to generate thesuccessors and return the selected next state4. n_queens(initial_state, static_x, static_y) — run the hill-climbing algorithm from a given initial state,return the convergence state5. n_queens_restart(n, k, static_x, static_y) — run the hill-climbing algorithm on an n*n board withrandom restartsYou may add other functions as you see fit, but these functions must be present and work as described.Generate SuccessorsThis function should return a list of lists, containing all valid successor states of the given current state.For the purposes of this program, a successor of a current state is any valid state that differs from thecurrent state by ONE queens location, which means you could only move one queen by one tile.We WILL allow multiple Queens to occupy the same row or the same diagonal line, but not the samecolumn, as it could not be described by the representation of the state.We WILL NOT allow moving the queen on the static point.If there is not a queen on the static point in the input state, return an empty listThe returned states should be sorted by the ascending order2020/9/26 HW3: Hill Climbing httpss://canvas.wisc.edu/courses/205182/assignments/995441 3/6For example, if the static point is at (0,0) and n = 3, the valid successors of the state [0, 1, 2] are: succ([0, 1, 2], 0, 0)= [[0, 0, 2], [0, 1, 1], [0, 2, 2]]There is no valid successors of the state [1, 1, 2] , as there is no queen on the static point. Thefunction should return an empty list in this case. succ([1, 1, 2], 0, 0)= []For sorting the states, using sorted() method will be sufficient to get the expected ascending order.Evaluate a StateAs in class, well define our f() to be the number of queens that are being attacked. Even if a queen isattacked by multiple other queens, it will only be counted once.Given n=3, here are some example f() values:[1, 2, 2] – f=3[2, 2, 2] – f=3[0, 0, 2] – f=3[0, 2, 0] – f=2[0, 2, 1] – f=2Select Next StateGiven a current State and the location of the static point, use the previous two functions to select the nextstate to evaluate per the following rules:If one of the possible states (including the current state) has a uniquely low score, select that stateOtherwise, sort the states in ascending order (as though they were integers) and select the loweststateIf the state is invalid, which means there is no queen on the static point, return None . choose_next([1, 1, 2], 1, 1)= [0, 1, 2] choose_next([0, 2, 0], 0, 0)= [0, 2, 0] choose_next([0, 1, 0], 0, 0)= [0, 2, 0] choose_next([0, 1, 0], 0, 1)= NoneN-Queens2020/9/26 HW3: Hill Climbing httpss://canvas.wisc.edu/courses/205182/assignments/995441 4/6Run the hill-climbing algorithm as specified in class on a given initial state until convergence, that is, untilyour algorithm finds a local minimum and gets stuck (or solves the problem). Here, we define that a localminimum means that you encountered two states with the same f value in the consecutive two steps.You should use choose_next() to choose the next state from the current state, which means the nextstate could be the same with your current state and your function should return in this situation.Your printed output for this function should look like the black text below, followed by the returnedminimum state in green: n_queens([0, 1, 2, 3, 5, 6, 6, 7], 1, 1)[0, 1, 2, 3, 5, 6, 6, 7] – f=8[0, 1, 2, 3, 5, 7, 6, 7] – f=7[0, 1, 1, 3, 5, 7, 6, 7] – f=7= [0, 1, 1, 3, 5, 7, 6, 7]# Here function Encounters two consecutive states [0, 1, 2, 3, 5, 7, 6, 7] and [0, 1, 1, 3, 5, 7, 6,7] with the same f value 7, so it gets stuck and returns n_queens([0, 7, 3, 4, 7, 1, 2, 2], 0, 0)[0, 7, 3, 4, 7, 1, 2, 2] – f=7[0, 6, 3, 4, 7, 1, 2, 2] – f=6[0, 6, 3, 5, 7, 1, 2, 2] – f=4[0, 6, 3, 5, 7, 1, 3, 2] – f=3[0, 6, 3, 5, 7, 1, 4, 2] – f=0= [0, 6, 3, 5, 7, 1, 4, 2]Each step of the hill-climbing function should print its current state along with that states f() value, andultimately return the best state you find.N-Queens with Random RestartsGenerate a random (valid!) initial state for your n*n board, and use your n_queens() function on thatstate. If the converged state does not solve the problem with an f() value of 0, generate a new random(valid!) initial state and try again. Try again up to k times.If you find an optimal solution before you reach k restarts, print the solution and terminate.If you reach k before finding an optimal solution with a score of 0, print the best solution(s) in sortedorder.An example of the output is illustrated below. The function does not need to return anything. Note thatyour output may not be the same with the examples below as the init state is generated randomly: n_queens_restart(7, 10, 0, 0)[0, 2, 0, 6, 4, 1, 5] – f=3[0, 3, 5, 2, 4, 6, 4] – f=3[0, 5, 4, 2, 6, 3, 1] – f=3 n_queens_restart(8, 1000, 0, 0)[0, 6, 4, 7, 1, 3, 5, 2] – f=02020/9/26 HW3: Hill Climbing httpss://canvas.wisc.edu/courses/205182/assignments/995441 5/6Pythons random module will be helpful in generating random initial states. Each columns coordinateshould be uniformly distributed over the possible coordinates, except for the column with the static point.To generate a single Uniform integer between 0 (inclusive) and n (inclusive), the Python code is: import random n = random.randint(0, 8)Be sure to account for the static point! Set the random_seed to 1 before using randint to make sure thatthe result of your program is reproducible, like the example below:import randomdef n_queens_restart(n, k, static_x, static_y):random.seed(1)random_int_1 = random.randint(0, 8)random_int_2 = random.randint(0, 8)…// Other part of your programRemember that you just Need to set the seed once at the beginning of your function, or you will alwaysget the same number.Test GradingWe provide a unit test module which includes all examples mentioned above to help you test yourprogram and make sure that your program is compatible with the grading script. Remember that we willuse more test cases when grading, and you are encouraged to add your own test cases to test yourprogram.To use the test script, first upload your nqueens.py to a CSL machine. In your working directory, run thecommands below:wget https://pages.cs.wisc.edu/~ywang2395/cs540/nqueens_test ( https://pages.cs.wisc.edu/~ywang2395/cs540/nqueens_test)mv nqueens_test nqueens_test.pypython3 nqueens_test.pyYou could also directly click the link to download it. The test is also written in Python, so feel free to openit by a text editor and modify it. If you passed all tests you will see an OK message. The unit test modulecould only be executed Under python3 environment, and we assume that your program should becompatible with python3.We do not have a strict limit on the running time, but please make sure that your program could finish ina reasonable period of time. In normal cases, your program could finish running all test cases above inless than 0.1s, and finish running n_queens_restart(8, 1000, 0, 0) in less than 1s.2020/9/26 HW3: Hill Climbing httpss://canvas.Wisc.edu/courses/205182/assignments/995441 6/6Total Points: 100.0Some Rubric (1)Criteria Ratings Pts80.0 pts20.0 ptsTest CasesThe program will be graded based on test cases for all five functions. Forn_queens_restart() the output of the function may not be the same as the standardoutput but for other Functions, their output should be exactly the same with the testcases.Valid SubmissionYour submission Should be a valid submission that is compatible with our testscript, i.e. a file named nqueens.py with five functions mentioned above20.0 ptsFullMarks0.0 ptsNoMarks如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“