# CompSci 18S - Fall 2007 - Puzzles

** Sept. 3, 2007 **

Classwork 2: 10 points, Assignment 3: 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 30 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.
- 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

What is an efficient algorithm for solving a maze of this type?
- 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?
- What is an efficient algorithm for moving through this maze?
- Are there any similarities in solving the maze and solving
sudoku?

## Assignment 3 (10 pts)

Assignment 3 is your own work and must be placed on your CompSci 18S
web page within one week after this class period. Do not write more
than one page!
- Write an algorithm for solving the maze problem.