Write a Python program (8-puzzle.py) based on A* search for solving the 8-puzzle problem (Python代写,Algorithm代写,香港程序代写)

Instruction:

• Submit your source codes and other requires files to Moodle
• Your source codes must contain your StudentId and Name
• You MUST follow the general program frameworks we studies in class

Question 1 (See Exercise 1 of Chapter 5) [8 marks]

Write a Python program (8-puzzle.py) based on A* search for solving the 8-puzzle problem that implements both the wrong tile heuristic (h1) and Manhattan distance heuristic (h2). Your program must be based on the A* algorithm we discussed in class. Part of the source code is completed for you in Moodle.

For each case, report the running time for both heuristics as well as whether the solution has been found for the following problems

1. [1,0,3,4,2,5,6,7,8]   
2. [5,1,3,4,0,8,7,6,2]    
3. [6,4,3,1,0,8,5,2,7]      
4. [4,7,2,8,0,1,3,6,5]     
5. [1,7,4,2,3,8,0,6,5] 

Submit your findings in the following format, as well as your program code to Moodle.

Question 2 (See Exercise 2 of Chapter 5)

Basic Part [8 marks]

Write a program (sudoku.py) to solve the 4*4 Sudoku problem as shown below. Your program must be based on the CSP algorithm we discussed in class.

 (The program Australia.py may be a useful reference)

Variable: a,b,c,d,e,f,g,h

Domain: {1,2,3,4}

Constraints:

50. Each smaller squares must contains 1 – 4:
50. For example, constraint for the upper left squares can be wrriten as

      sorted[a,1,4,c] == [1,2,3,4]    

(Alternatively, you can convert each four elements into a set, and check whether its length is 4)

50. Each row must contain 1 – 4
50. Each column must contain 1 - 4

Note: for the basic part, you don’t need to solve all 4*4 suduku problem in general. Just solve the problem instance shown above. The input can be hard-coded into the program if you wish.

2 1 4 3

4 3 1 2

1 2 3 4

3 4 2 1

(4 marks):

Change your program so that it can solve any 4*4 suduku problem.

1. Ask the user to enter four rows of four numbers, and replace blank tiles with zero.
2. Show solution.

Example:

            Enter first  row (enter 0 for space): 2 0 0 0

Enter second row (enter 0 for space): 0 1 3 0

Enter third  row (enter 0 for space): 3 0 0 1

Enter fourth row (enter 0 for space): 0 2 4 0

Solution Found!

2 3 1 4

4 1 3 2

3 4 2 1

1 2 4 3

**You program must be based on the CSP framework we discussed. Do not use the Python-Constraint library because there are too many solutions out there!***

2 3 1 4

4 1 3 2

3 4 2 1

1 2 4 3

[10 bonuses]

(Only for those who want some real challenge.)

Rewrite the program to solve a general 9 * 9 puzzle sudoku problem.

7 8 2 4 5 3 6 1 9

4 6 5 1 9 7 8 2 3

3 1 9 6 8 2 7 5 4

5 9 3 8 4 1 2 6 7

1 2 7 3 6 9 4 8 5

8 4 6 7 2 5 9 3 1

6 7 1 9 3 8 5 4 2

2 3 8 5 7 4 1 9 6

9 5 4 2 1 6 3 7 8