Regular sudoku is played on a grid of 9 x 9 spaces. Within the rows and columns are 9 ?squares? (made up of 3 x 3 spaces). Each row, column and square (9 spaces each) needs to be filled out with the numbers 1-9, without repeating any numbers within the row, column or square. As you can see from the image below of an actual Sudoku grid, each Sudoku grid comes with a few spaces already filled in; the more spaces filled in, the easier the game the more difficult Sudoku puzzles have very few spaces that are already filled in.

Consider a 4 by 4 sudoku in which only numbers 1,2,3, and 4 will be used to fill the cells.

1. Using Graph representation identify a way to represent a 4 by 4 sudoku. Note: Refer to the cells as (1,1), (1,2), (1,3), (1,4), (2,1),...,(4,4), where the first number in the bracket is the row number of the cell, and the second number is column number.

2. Suggest an algorithm (pseudocode) to solve a 4 by 4 sudoku.

3. Show the application of your algorithm manually on problem below.

(a) is unsolved Sudoku and

(b) is the solution.

6 5 49 6 42 89 2861549 7 3 19576384 2 743289516 7 5 8 1 5 34 6 3796 25 4 |8|1 85 13476 29 4 6 2918 7 3 5 6 345721|98 9 178362 54 5 2849 1367 7 3 4 1 9 8 5 4 3 2. 4.