# Udacity: Sudoku

Posted on Mar 17, 2012 by Chung-hong Chan

Udacity CS101 上周的 Programming 功課，最難是這一條，是 check 一個簡化版數獨是否正確。 ((真數獨除了要 check 9 行直行、9 行橫行，還要 check 九個 3x3 的方格數字是否 unique 。最尾的一個 criteria 對於 CS101 來說太難了。但要是真的要做，只要將九個 3x3 拆成 vector 再 check 便可。))

#THREE GOLD STARS

#Sudoku [http://en.wikipedia.org/wiki/Sudoku]
#is a logic puzzle where a game
#is defined by a partially filled
#9 x 9 square of digits where each square
#contains one of the digits 1,2,3,4,5,6,7,8,9.
#For this question we will generalize
#and simplify the game.

#Define a procedure, check_sudoku,
#that takes as input a square list
#of lists representing an n x n
#sudoku puzzle solution and returns
#True if the input is a valid
#sudoku square and returns False
#otherwise.

#A valid sudoku square satisfies these
#two properties:

# 1. Each column of the square contains
# each of the numbers from 1 to n exactly once.

# 2. Each row of the square contains each
# of the numbers from 1 to n exactly once.

correct = [[1,2,3],
[2,3,1],
[3,1,2]]

incorrect = [[1,2,3,4],
[2,3,1,3],
[3,1,2,3],
[4,4,4,4]]

Python 沒有 buildin 的 matrix 格式，故此以 list of list 的方式表達。而此 course 學的 Python 指令也不多，這才增加了此問題的難度。

Udacity 下季有 CS212 ，由 Peter Norvig 教，我已報讀了。友人說我好像好勤學新野。對，我何時都想這樣，而且這些 course 是免費的，夫復何求。最新看了一篇文，是由一位曾於 HKU 任教，再回到美國教書的 computer scientist 寫的，他說：

My students cheated like crazy. On one occasion, I caught 35 out of 100 students cheating on a programming assignment. This is not specific to HKU. My friends at HKUST had problems of a similar magnitude. I believe this is partially due to the dark side of HK culture. Hong Kong is not about intellectual achievement. It is about profit; making money; success in the material world. Half of the shelf-space in HK bookstores is devoted to books on business, marketing, negotiation, and so forth. Cheating is in some sense a profitable activity: maximum return for minimum outlay.

[code]
correct = [[1,2,3],
[2,3,1],
[3,1,2]]

incorrect = [[1,2,3,4],
[2,3,1,3],
[3,1,2,3],
[4,4,4,4]]

def transpose(sudoku):
# nrow of the sudoku
tsudoku = []
nrow = len(sudoku)
for i in range(0,nrow):
colvec = []
for j in range(0,nrow):
colvec.append(sudoku[j][i])
tsudoku.append(colvec)
return tsudoku

def checkVector(vector, n):
checkN = 1
logicVector = []
while checkN < = n:
logicVector.append(checkN not in vector)
checkN = checkN + 1

#print checkVector([1,2,2,4], 4)

#print transpose(incorrect)
def check_sudoku(sudoku):
widthSudoku = len(sudoku)
# first check the orignal
for row in sudoku:
if checkVector(row, widthSudoku):
return False
for row in transpose(sudoku):
if checkVector(row, widthSudoku):
return False
return True
[/code]