P2: Connect Four Game - [15 marks] Write a program (in a file called c4game.py) that lets two players play a game of connect four. Program Your program will be driven by a main() function. Be sure to include a main guard (if statement) in your file. The program will proceed as follows: 1. The users are asked for the size of the game to play in a single question. The expected input should something like "4,6" to play a game with 4 rows and 6 columns. There can be any amount of whitespace around the numbers and the comma when the user enters this. So 4, 6", "4 , 6" and 4,6" are all valid. If the users enter quit' then the program ends with a parting message like "Thanks for playing". The user will NEVER enter anything other a valid row,column combination or quit. 2. The program checks if there are empty locations in the game grid. If the grid is full, it outputs a message "the game is a tie" and then repeated step 1. If there is at least one empty location, then proceed to step 3. 3. The program asks 'red' which column to play (remember column labels start with 0) and then tries to play a red checker in the given column. a. If this is successful, the grid is shown and then the program checks if the last move was a winning move. If it was a winning move the game ends with an appropriate message ('Red wins the game after M moves') and the program goes back to step 1. If was not a winning move, the program proceeds to step 4. b. If this is unsuccessful , a message is displayed (that it was an invalid move) and we retry step 3. 4. The program checks if there are empty locations in the game grid. If the grid is full, it outputs a message "The game is a tie" and then repeated step 1. If there is at least one empty location, then proceed to step 5. 5. The program asks 'black' which column to play (remember column labels start with 0) and then tries to play a black checker in the given column. a. If this is successful, the grid is shown and then the program checks if the last move was a winning move. If it was a winning move the game ends with an appropriate message ('Black wins the game after M moves") and the program goes back to step 1. If it was not a winning move, we proceed to step 6. b. If this is unsuccessful, a message is displayed (that it was an invalid move) and we retry step 5. 6. Go back and repeat step 2. In the above description, M is the total number of valid moves that have been played in the given game. The minimum number that this can be for a valid game is 7 (when red wins after its first 4 moves). A sample run of the game is as follows: (User input is shown highlighted light yellow; your game will NOT show this highlighting; it is just there for illustrative purposes). Please enter the size of the game you want to play: 4, 5 Where does red (x) want to play? 4 | 10 1 11 1 12 1 X3 +-----+ 01234 Where does black (0) want to play? 4 1 10 1 11 1 012 1 X3 01234 Where does red (x) want to play? 7 That is not a valid move. Where does red (x) want to play? 1 1 10 1 11 012 | XX13 +-----+ 01234 Where does black (0) want to play? 4 1 10 1 011 1 012 I X X3 +-----+ 01234 Where does red (x) want to play? 2 1 10 011 1 012 | XX X3 +---+ 01234 Where does black (0) want to play? 1 1 10 011 1 012 OXX X3 +-----+ 01234 Where does red (x) want to play? 3 1 10 1 011 1 012 OXXXX 13 +-----+ 01234 Red wins after 7 moves Please enter the size of the game you want to play: quit Thanks for playing