Werden wir Helden für einen Tag

Home | About | Archive

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 便可。))


#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

#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],

incorrect = [[1,2,3,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 。

correct = [[1,2,3],

incorrect = [[1,2,3,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):
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

Powered by Jekyll and profdr theme