# CompSci 18S - Fall 2009 - Puzzles

** Aug. 31, 2009 **

Classwork 2: 10 points, Assignment 2: 10 points

# 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

You will discuss how to solve this puzzle within your group
and then write an algorithm
to turn in.
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

What is an efficient algorithm for solving a Sudoku puzzle?
- Consider trying all possible combinations of numbers in the blank squares.
How many filled in puzzles would that be to check?
- 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?
- What are other smaller problems that would be useful to define an algorithm for?
- Should there be a starting square? If so, which square do you start in?
- How do you put the smaller subproblems together into an algorithm?

## Group Writeup (10 pts)

- 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?
- 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

Discuss how one would solve the maze. Think about the questions below
as you discuss.
Once you have talked through it thoroughly, see assignment 2 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 2 should be done for homework.

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

## Assignment 2 (10 pts)

Assignment 2 is your own work. Bring into class next time.
- Write an algorithm for solving the maze problem.