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

What is an efficient algorithm for solving a maze of this type?
  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. What is an efficient algorithm for moving through this maze?
  5. 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!
  1. Write an algorithm for solving the maze problem.