Puzzles

Learn the game of Sudoku (also known as Suduko).

To solve the puzzle below, fill in the digits 1-9 on each row, on each column and in each 3x3 box that is highlighted. Only one of each digit should appear in each row, column or 3x3 box.

Go ahead and solve the puzzle. As you solve the puzzle, think about the method you are using to solve the puzzle. Keep track of what works well and what does not. Do not spend more than 20 minutes attempting to solve this puzzle.

Problem 1: Sudoku

An algorithm is a set of well-defined instructions (written in pseudocode or phrases, not code for a programming language) for accomplishing a task.

DISCUSS: Solving Sudoku

1. Consider trying all possible combinations of numbers in the blank squares. How many filled in puzzles would that be to check?
2. Think about solving a smaller problem first. Assume the puzzle is just the first row. What is an algorithm for filling in the squares with the digits 1-9 so that there is a unique number in each square?
3. What are other smaller problems that would be useful to define an algorithm for?
4. Should there be a starting square? If so, which square do you start in?
5. How do you put the smaller subproblems together into an algorithm?

Group Writeup (10 pts)

1. Write an algorithm for solving the Sudoku puzzle. If you give your algorithm to another group, would they be able to follow your algorithm to solve it?
2. Explain how long your algorithm will take. You do not have to give the exact time, but can instead explain what parts of your algorithm make it more efficient than the "try all puzzles" approach.

Note: For group writeups you turn in just one sheet of paper with all your names on it.

Problem 2: Maze

Consider the following Maze that is made up of black and white squares of size 21x21.

Discuss

Once you have talked through it thoroughly, see assignment 1 below where each of you should write down the algorithm on paper to turn it in. If you have time in class, you can do this in class. Otherwise Assignment 1 should be done for homework.

1. Would numbering the squares be helpful and if so how would you number them?
2. How do you define a valid move from one square to another?
3. Is there anything you need to keep track of as you move through the maze?
4. Are there any similarities in solving the maze and solving sudoku?

Assignment 1 (10 pts)

1. Write an algorithm for solving the maze problem.