#!/usr/bin/env python
# The purpose of this assignment is to:
# * Learn how to construct a medium-sized program
# * Learn how a large problem may be broken into a series of small problems using bottom-up modularization
# * Learn how to solve a Sudoku without really trying
# ## Definition of a Sudoku
# A sudoku puzzle is a popular logic puzzle commonly found in newspapers and puzzle books. The puzzle is given as a 9×9 grid with the numbers 1 through 9 entered in it. Throughout this lab, we will take “0” to mean a “blank cell”. The objective of the puzzle is to fill in all the blank cells with numbers between 1 and 9. A typical sudoku puzzle looks like this:
#
# 0 0 7 || 0 0 0 || 0 1 5
#
# 0 0 0 || 3 9 7 || 0 0 0
#
# 0 6 2 || 0 1 0 || 4 0 9
#
# ===============
#
# 0 2 0 || 0 0 1 || 5 4 3
#
# 7 0 0 || 4 0 9 || 0 0 1
#
# 4 8 1 || 2 0 0 || 0 6 0
#
# ===============
#
# 9 0 6 || 0 2 0 || 7 3 0
#
# 0 0 0 || 9 8 4 || 0 0 0
#
# 1 5 0 || 0 0 0 || 2 0 0
#
# There are three rules about what numbers are allowed to go in any particular cell.
#
# 1) Numbers are not allowed to occur more than once in any horizontal row
#
# 2) Numbers are not allowed to occur more than once in any vertical column
#
# 3) Numbers are not allowed to occur more than once in any of the nine smaller squares (here indicated by lines)
#
# Another way of saying this is that a number may only appear once in any row, column, or sub-square.
#
# Over the course of this lab we will construct an algorithm which will solve sudoku problems automatically.
# ## How we will encode a Sudoku Puzzle in Python
# For the purposes of this algorithm, we will define a sudoku puzzle as a two dimensional list, as follows. Every element of s is a list containing nine elements, which correspond to each cell in that row. When any function in this lab specifies a sudoku puzzle as an input, you may expect it in this format.
#