Python定制 | Notakto – Human vs. Human

这个作业是用python完成一个井字棋变体游戏
1. Notakto – Human vs. Human
Weight: 25%
Academic Dishonesty
We will be checking your code against other submissions in the class and from the Internet for logical redundancy. If you copy someone else’s code and submit it with minor changes, we will know. We trust you all to submit your own work only; please don’t let us down. If you do, we will pursue the strongest consequences available to us.
Discussion Forum
Please be careful not to post spoilers. Please don’t post any code that is directly related to the assignments. However you are welcome and encouraged to discuss general ideas on the discussion forums. If you have any questions about this exam you should post them in the discussion forums. Do not email individual teachers with questions.
In this question, you are going to implement a human vs. human version of Notakto.
Notakto is a tic-tac-toe variant. It is played across three 3 x 3 boards: Board A, board B and board C. When you start the game you should output the boards as follows.
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1:
There are two players: Player 1 and player 2. Player 1 always starts. Both players play the same piece: X. E.g., let player 1 choose location 6 on board A, i.e., the user will enter A6. The output of the program should be as follows (bold font represents user input).
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: A6
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X 7 8 6 7 8 6 7 8
Player 2:
Each player takes turn placing an X on the board in a vacant space (a space not already occupied by an X).
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: A6
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X 7 8 6 7 8 6 7 8
Player 2: A7
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X X 8 6 7 8 6 7 8
Player 1:
If a board has three X in a row, column, or diagonal, the board is dead and it cannot be played anymore. It should not be displayed anymore. E.g., in the following example, board A becomes dead and is not displayed anymore.
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: A6
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X 7 8 6 7 8 6 7 8
Player 2: A7
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X X 8 6 7 8 6 7 8
Player 1: A8
B C
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
Player 2:
The game ends when all the boards contain three X in a row, column, or diagonal, at which point the player to have made the last move loses the game. Unlike tic-tac-toe, there will always be a player who wins any game of Notakto.
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: A6
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X 7 8 6 7 8 6 7 8
Player 2: A7
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
X X 8 6 7 8 6 7 8
Player 1: A8
B C
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
Player 2: B0
B C
X 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
Player 1: B4
B C
X 1 2 0 1 2
3 X 5 3 4 5
6 7 8 6 7 8
Player 2: C0
B C
X 1 2 X 1 2
3 X 5 3 4 5
6 7 8 6 7 8
Player 1: C4
B C
X 1 2 X 1 2
3 X 5 3 X 5
6 7 8 6 7 8
Player 2: C8
B
X 1 2
3 X 5
6 7 8
Player 1: B8
Player 2 wins game
Note that you should check for legal moves. If the users enters something illegal you should prompt them again. Let’s play a new game to illustrate this.
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: C0
A B C
0 1 2 0 1 2 X 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 2: B9
Invalid move, please input again
Player 2: fds
Invalid move, please input again
Player 2: C0
Invalid move, please input again
Player 2: C6
A B C
0 1 2 0 1 2 X 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 X 7 8
Player 1: C6
Invalid move, please input again
Player 1: C3
A B
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
Player 2: C2
Invalid move, please input again
Player 2:
Implement the game and try to pass all test cases. The list of test cases is not complete. We may add more test cases when marking after the deadline.

2. Notakto – AI vs. Human
Weight: 25%
Academic Dishonesty
We will be checking your code against other submissions in the class and from the Internet for logical redundancy. If you copy someone else’s code and submit it with minor changes, we will know. We trust you all to submit your own work only; please don’t let us down. If you do, we will pursue the strongest consequences available to us.
Discussion Forum
Please be careful not to post spoilers. Please don’t post any code that is directly related to the assignments. However you are welcome and encouraged to discuss general ideas on the discussion forums. If you have any questions about this exam you should post them in the discussion forums. Do not email individual teachers with questions.
In this question, you are going to implement an artificial intelligence (AI) vs. human version of Notakto. The AI will be the Player 1, i.e., the AI will always start. Here the AI means that the move of player 1 is determined by your program automatically. You should finish the previous question first before working on this one. All output / input requirements are identical to the previous question. The only difference is that you replace Player 1 with an AI, i.e., don’t wait for user input and let your program decide the valid move.
In Notakto, Player 1 can force a win. It doesn’t matter how Player 2 plays. If Player 1 plays optimally there should be a win for Player 1. In this task your AI must always win. Here is an example run (bold font represents user input).
A B C
0 1 2 0 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: B0
A B C
0 1 2 X 1 2 0 1 2
3 4 5 3 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 2: B3
A B C
0 1 2 X 1 2 0 1 2
3 4 5 X 4 5 3 4 5
6 7 8 6 7 8 6 7 8
Player 1: B6
A C
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
Player 2: C0
A C
0 1 2 X 1 2
3 4 5 3 4 5
6 7 8 6 7 8
Player 1: C3
A C
0 1 2 X 1 2
3 4 5 X 4 5
6 7 8 6 7 8
Player 2: C6
A
0 1 2
3 4 5
6 7 8
Player 1: A0
A
X 1 2
3 4 5
6 7 8
Player 2: A4
A
X 1 2
3 X 5
6 7 8
Player 1: A7
A
X 1 2
3 X 5
6 X 8
Player 2: A8
Player 1 wins game
There will be no student site automatic marking for this question. Please perform your own testing and ensure that you never win against your AI. We suggest that you finish the previous question first and then copy over your code from there and only change the part where player 1 (your AI implementation) is moving.
We will mark your code by playing a number of games against an optimal AI. Your AI must win all games to get full marks for this question.
Important: Implementing an optimal AI that is able to always win does not require complex computation. Your AI must be very fast. We will use a time threshold of 1 second per move. You are allowed to discuss solution strategies for this question. But don’t share any code.
3. Safety map
Two maps are shown below.
• The one on the left gives the dangerous chemical map.
• The one on the right shows the safety map.

In the dangerous chemical map, a cell value is:
• 1 – denote the existence of a dangerous chemical.
• 0 – no dangerous chemical in that location.
In the safety map, a location is considered to be
• Safe (safety = 1) if there is no chemical around its 3×3 neighbourhood, and
• Super safe (safety = 2) if there is no chemical around its 5×5 neighbourhood, and
• Dangerous chemical (safety = #) if there exists a dangerous chemical in that location
• (safety = 0) Otherwise
Write a program that reads in the map on left, and output the map on right.
You can assume that both the maps square (have the same number of rows and columns)
Sample test cases (The bolded text are user input)
101000000
001010110
010000001
000000010
010000000
000000010
100000000
001011000
000110000
#0#000000
00#0#0##0
0#000000#
0001110#0
0#0121000
0001110#0
#00000000
00#0##011
100##0012
4. Drone stations
You have a drone that can fly for a distance of D before it runs out of battery.
There are N charging stations that can fully charge up a drone.
Write a program to determine whether there is a way to fly a drone (initially fully charged) from your location to a target location via zero or more intermediate charging stations.
Input specification:
• The first line consists of two positive integers N (≤ 10) and D (≤ 10); where N is the number of charging stations, D is the distance that a fully charged drone can travel.
• The next N lines are the X-Y coordinates of the locations of the N charging stations.
• The 2nd last line is the X-Y coordinate of your location (with a fully charged drone).
• The last line is the X-Y coordinate of the target location.
Output specification:
• The (lower-case) character “y” if there is a way to fly a drone (initially fully charged) from your location to a target location via zero or more intermediate charge stations., or “n” if there is not.
Sample testcases (The bolded text are user input)
Case 1
3 7
0 3
5 1
8 6
0 1
13 3
y
Case 2
4 6
1 7
5 5
6 1
7 8
5 6
14 32
n