ECE 190: Introduction to Computing Systems, Spring 2010 Machine Problem 2 Checkpoint 1 Due: 5 p.m., Wednesday 3 March, 2010 Checkpoint 1 Due: 5 p.m., Wednesday 10 March, 2010 Sudoku Introduction: For this machine problem you will be writing a program in LC-3 assembly to implement the game of Sudoku. Sudoku is a numbers game in which there is a 9x9 grid of numbers, and the player must compete the grid in such a way that each row, column, and 3x3 sub-block of the grid contain every number from 1 to 9. Your program will use ASCII characters to display the 9x9 game boards, and a player will be able to fill out the grid and solve the puzzle one number at a time. If a spot on the game board does not have a number held within, a space will be displayed. Your implementation should be able to take row and column coordinates as user input, detect if the number placement is "legal," and determine when the game is finished. A skeleton mp2.asm file and test cases will be provided (read the MP2 README in the Machine Problems section). Checkpoint 1: For the first checkpoint you will need to correctly display the 9x9 gameboard and detect if a board is completely filled out. You do not, at this time, need to be concerned with the board being correctly filled out. You will be given a database that contains 81 numbers stored sequentially starting at memory address x4000 as shown below. Address Memory Value (row, column) x4000 Memory Value (0,0) x4001 Memory Value (1,0) x4002 Memory Value (2,0) ... ... x4050 Memory Value (8,8) Each memory location will have data in the following format: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Binary Number If the number is a zero (x0000) that shall mean that there is no number in that space on the game board. Any non-zero number will always be between the values of 1 and 9. The board shall be a 9x9 grid rendered using ASCII '+', '-', '|' and ' ' (space) characters. An empty spot of the game board would be printed as three spaces in the location, whereas a spot with a number would have a single space followed by the ASCII number followed by another space. The board is shown below.+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | 5 | 3 | | | 7 | | | | | | 5 | 3 | 4 | 6 | 7 | 8 | 9 | 1 | 2 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | 6 | | | 1 | 9 | 5 | | | | | 6 | 7 | 2 | 1 | 9 | 5 | 3 | 4 | 8 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | 9 | 8 | | | | | 6 | | | 1 | 9 | 8 | 3 | 4 | 2 | 5 | 6 | 7 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | 8 | | | | 6 | | | | 3 | | 8 | 5 | 9 | 7 | 6 | 1 | 4 | 2 | 3 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | 4 | | | 8 | | 3 | | | 1 | | 4 | 2 | 6 | 8 | 5 | 3 | 7 | 9 | 1 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | 7 | | | | 2 | | | | 6 | | 7 | 1 | 3 | 9 | 2 | 4 | 8 | 5 | 6 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | 6 | | | | | 2 | 8 | | | 9 | 6 | 1 | 5 | 3 | 7 | 2 | 8 | 4 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | | | 4 | 1 | 9 | | | 5 | | 2 | 8 | 7 | 4 | 1 | 9 | 6 | 3 | 5 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ | | | | | 8 | | | 7 | 9 | | 3 | 4 | 5 | 2 | 8 | 6 | 1 | 7 | 9 | +---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+ The board on the left is what a player would see at the beginning of the game, while the board on the right is the final solution for the puzzle. The top left corner of the grid is considered to be the coordinate (0,0) and the bottom right is (8,8). The top right is (8,0) and the bottom left is (0,8). CHECK_FOR_WIN is the last subroutine you will need to create. It is responsible for determining if all 81 spaces on the board have numbers in them, and exits the game after printing the WIN_MSG if the board is full. If the board is not full, then return to the main program. Required Subroutines (Checkpoint 1): • Display Subroutine: To display the game board you should write a display subroutine. This subroutine should first clear the screen by writing 50 linefeeds (\n or x000A) to the screen using the OUT trap. Then display the current game board using OUT. Entries with 0's in all bits should be displayed as a space and entries with numbers should be displayed as their ASCII equivalents. • Check For Win: This subroutine displays the WIN_MSG using PUTS and then HALTS if all 81 entries of the Sudoku table are filled, otherwise it returns to the main routine. Checkpoint 2: Any user playing the game will need to be able to input information to the program, so your program will also need to take in user input using a GET_VALID_INPUT subroutine that will be given to you in the template code. For any input you are given, you will need to store it in any labeled memory location and also print it back out to the screen. You will need to write a GET_INPUTS subroutine that asks the user for all the needed information and uses GET_VALID_INPUT to help with this task. Finally, the new data is to be stored in the database of numbers for the puzzle. For the second checkpoint, you will need to create a CHECK_INPUT subroutine that will enforce the rules of Sudoku onto the player. That is to say that CHECK_INPUT will make sure the new entry does not break these rules:• Each row must contain no more than one of the same number. • Each column must contain no more than one of the same number. • Each 3x3 sub-block must contain no more than one of the same number. If any of those three conditions are not met, the new board entry should be removed from the database and INVALID_MSG2 should be displayed using PUTS. You will be given several look up tables in the template code that may or may not help you fulfill the objectives of this checkpoint. After all of this is done, you need to display the WAIT_MSG using PUTS and wait for the user to input any character prior to exiting. Required Subroutines (Checkpoint 2): …