3. Algorithm
In order to design a Tic-Tac-Toe game, or any other software project, we must break the problem into small pieces. To this effect, we have created the following flow chart for Tic-Tac-Toe.



You will use this flowchart as the basis for designing the program. The blocks that you must implement are in bold.

4. What to do
The following starter code provides a general framework for the Tic-Tac-Toe game, plus a single subroutine called EVALBOARD.
Your job is to complete the Tic-Tac-Toe game by writing the following four subroutines

• GETVALIDINPUT
  This subroutine combines two tasks:
  
  1. Getting input from the user (this input is returned to the caller in register R1)
  
  2. Performing error checking on the input
  
  
  The only valid input during the Tic-Tac-Toe game is a number 1-9, or the letter 'q'.
  You should prompt the player for input with the following prompt:
  

       "X - Which square? [1-9] "
       "O - Which square? [1-9] "
  

  If the player does not enter a valid input, you should print the following message to the screen
  

       "Invalid input"
  

  and again prompt the player to choose a square.
  
  If the player chooses a square which is already occupied, you should print the message
  

       "Space occupied"
  

  and again prompt the player to choose a square.
  
  The ASCII code of the valid input character must be returned in register R1.



• UPDATEBOARD
  When this subroutine is called, R1 contains the ASCII code for a numeric character 1-9, which you previously have provided in GETVALIDINPUT.
  The player, X or O, is defined by the contents of the memory location labeled PLAYER, which is initially set to 1.
  

  Memory[PLAYER] = 1 for player X
                   0 for player O
  

  You should update the Tic-Tac-Toe board in memory by writing an X or O into the square designated by the value in R1. You must also update the contents of location PLAYER after updating the board.
  


• DRAWBOARD
  This subroutine simply prints the Tic-Tac-Toe board to the screen.
  


• PRINTOUTCOME
  When this subroutine is called, R1 contains a value indicating the outcome of the game. This value is provided by the EVALBOARD subroutine.
  1 = X wins
  2 = O wins
  3 = Cat Game
  You should print one of the following messages based on the value in R1.
  

       "X wins!" 
       "O wins!"
       "Cat Game!"
  

• EVALBOARD
  This code examines the nine squares and returns a value in register R1 according to the following:
  

        R1 = 0     Game still in progress
             1     X wins
             2     O wins
             3     Cat Game (no winner)
  

  It is a very good idea to go through the EVALBOARD subroutine and verify for yourself that it actually works. Doing so will provide some useful hints on how to construct the other subroutines.
  

5. Guidlines
You should adhere to the following guidelines when designing your program.

• The squares on the board are numbered sequentially, starting from the top-left corner as shown below:




        |   |   
      1 | 2 | 3 
        |   |   
     -----------
        |   |   
      4 | 5 | 6 
        |   |   
     -----------
        |   |   
      7 | 8 | 9 
        |   |   



• X always goes first. This is especially important for grading!


• In each subroutine you write, you should save and restore any registers that you use. This will avoid a major headache during debugging.

6. Page Boundary
The code we have provided you starts at location x3000. You will notice that we have added a .BLKW pseudo-op to add blank space in the program up to address x31FF. Starting at location x3200, we have provided several useful .FILL pseudo-ops for you to use in your solution.

All of your subroutines will be stored in memory on page x19 of memory (page x19 starts with address x3200). Towards the end of page x18 in the code, you'll see a jump table, which is a table of the starting addresses of all the subroutines you must implement. You must populate this table.

Recall that if you attempt to use symbols on one page of memory that were defined on a different page, the LC-2 Editor will not assemble your program. This problem is due to the fact that the LD, ST, BR, and many other instructions only store the 9-bit page offset of the address they are loading from, storing to, or branching to during execution. This is why we are using the JSRR instruction in the main section of the program instead of the JSR instruction.

In order to figure out what value to put in the .FILL pseudo-ops in the jump table, you will look at the program listing produced by the LC-2 Editor at assembly time. This file has the extension ".lst" and contains the machine code, assembly code, symbols, and address information for your entire program.

Note: when you assemble a program that crosses a page boundary, the LC-2 Editor gives you a warning, but still correctly assembles the program.

7. Sample Input
Remember, X always goes first. You may test your game with the following inputs:

    InputString          OutputString
    ---------------      ------------
    1 4 2 5 7 6          O wins!
    5 4 3 1 7            X wins!
    1 2 3 7 8 9 4 5 6    Cat Game!

8. Submission Instructions
--Instructions for submission are posted on the course homepage.