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 指令也不多，這才增加了此問題的難度。
很多的同學在網上 forum 指太難。這個問題最佳的解決方法，就是將大問題解為細問題。
這個問題的最細 unit ，是 check 每一橫行 Vector 的每個數字是否 unique 。例如 [1,2,3,4] ，每個數字都是 unique 。而 [4,4,4,4] 就不是 unique 了。用 abstraction 的方法，可以將如此 function 暫名為 checkVector ，就先不去想如此的 function 如何 define 。
只要用 checkVector 查 matrix 的所有橫行，就最少證實了原來 matrix 所有橫行是正確。
可能我太習慣用 R 來思考，我想到只要將如此 matrix transpose （即是將直行轉成橫行），再 check 橫行，也可證明直行也是正確的。
我寫 program 實在不叻，故此是很 verbose 的。但如此 verbose 也有好處，就是可以容易理解。
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.
我需要的是 intellectual achievement 。
[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
badVector = True in logicVector
return badVector
#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]