sudoku.py

#!/usr/bin/python
from __future__ import print_function
from pprint import pprint

# Write a function done_or_not passing a board (list[list_lines]) as parameter.
# If the board is valid return 'Finished!', otherwise return 'Try again!'

# Sudoku rules:
#
# ROWS:
# Complete the Sudoku puzzle so that each and every row, column,
# and region contains the numbers one through nine only once.
# There are 9 rows in a traditional Sudoku puzzle.
# Every row must contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9.
# There may not be any duplicate numbers in any row.
# In other words, there can not be any rows that are identical.
#
# COLUMNS:
# There are 9 columns in a traditional Sudoku puzzle.
# Like the Sudoku rule for rows, every column must also contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9.
# Again, there may not be any duplicate numbers in any column. Each column will be unique as a result.
#
# REGIONS:
# A region is a 3x3 box like the one shown to the left. There are 9 regions in a traditional Sudoku puzzle.
# Like the Sudoku requirements for rows and columns, every region must also contain the numbers
# 1, 2, 3, 4, 5, 6, 7, 8, and 9. Duplicate numbers are not permitted in any region.
# Each region will differ from the other regions.

first_board = [[1, 3, 2, 5, 7, 9, 4, 6, 8],
               [4, 9, 8, 2, 6, 1, 3, 7, 5],
               [7, 5, 6, 3, 8, 4, 2, 1, 9],
               [6, 4, 3, 1, 5, 8, 7, 9, 2],
               [5, 2, 1, 7, 9, 3, 8, 4, 6],
               [9, 8, 7, 4, 2, 6, 5, 3, 1],
               [2, 1, 4, 9, 3, 5, 6, 8, 7],
               [3, 6, 5, 8, 1, 7, 9, 2, 4],
               [8, 7, 9, 6, 4, 2, 1, 5, 3]]

second_board = [[1, 3, 2, 5, 7, 9, 4, 6, 8],
                [4, 9, 8, 2, 6, 1, 3, 7, 5],
                [7, 5, 6, 3, 8, 4, 2, 1, 9],
                [6, 4, 3, 1, 5, 8, 7, 9, 2],
                [5, 2, 1, 7, 9, 3, 8, 4, 6],
                [9, 8, 7, 4, 2, 6, 5, 3, 1],
                [2, 1, 4, 9, 3, 5, 6, 8, 7],
                [3, 6, 5, 8, 1, 7, 9, 2, 4],
                [8, 7, 9, 6, 4, 2, 1, 3, 5]]

def done_or_not(board):
	def is_region_valid(region):
		# Assume that a region is a 9-element list
		# Check that the numbers 1 through 9 only appear once each
		return set(region) == set(range(1,10))


	def columns(board):
		def _column(board, col):
			return [row[col] for row in board] 
		return [_column(board, i) for i in range(9)]

	def quadrants(board):
		# In a Sudoku board, a quadrant is a 3x3 region with the upper left corner
		# at one of the following coordinates
		# (0,0), (3,0), (6,0)
		# (0,3), (3,3), (6,3)
		# (0,6), (3,6), (6,6)
		# Let these correspond to the following indices
		# 0 1 2
		# 3 4 5
		# 6 7 8
		# And let each 3x3 quadrant be rearranged into a single 9-element list,
		# comprised of the rows concatenated together
		# Then this function will generate a list of those 9 quadrants, and each
		# quadrant being represented by one such list
		def quadrant(board, x, y):
			return [board[z][x:x+3] for z in range(y, y+3)]
		q = []
		for y in range(0,9,3):
			for x in range(0,9,3):
				quadrant_to_list = reduce(lambda l1,l2: l1+l2, quadrant(board, x, y))
				q.append(quadrant_to_list)
		return q

	for row in board:
		if not is_region_valid(row):
			return False

	for column in columns(board):
		if not is_region_valid(column):
			return False

	for quadrant in quadrants(board):
		if not is_region_valid(quadrant):
			return False

	return True

if __name__=="__main__":
    print("First board:")
    pprint(first_board)
    print("done_or_not: " + str(done_or_not(first_board)))
    print("Second board:")
    pprint(second_board)
    print("done_or_not: " + str(done_or_not(second_board)))