Thursday, May 25, 2006

Solve Sudoku Puzzle with Python

เคยเขียนเรื่องการ solve Sudoku ด้วย Oz
กับ Solve ด้วย java ไปแล้ว

Peter Norvig ปล่อยบทความว่าด้วยการใช้
Solving Every sudoku Puzzle ออกมา
โดย implement ด้วย python

แค่เริ่มต้น declare ตัวแปรต่างๆ ผมก็ร้องว้าวแล้ว
rows = 'ABCDEFGHI'
cols = '123456789'
digits = '123456789'
squares = [r+c for r in rows for c in cols]
unitlist = ([[r+c for r in rows] for c in cols] +
[[r+c for c in cols] for r in rows] +
[[rows[r+dr]+cols[c+dc] for dr in (0,1,2) for dc in (0,1,2)]
for r in (0,3,6) for c in (0,3,6)])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(s2 for u in units[s] for s2 in u if s2 != s))
for s in squares)


วิธีการที่ใช้ solve ก็คือ constraint propagation กับ search
จำนวนบรรทัด ใช้ไปแค่ 100 บรรทัด

ผมชอบวิธีที่เขาเขียน code
ติดใจมาจากหนังสือ "Artificial Intelligence Programming" ที่เขาเขียน

Related link from Roti

1 comment:

amyggie said...

มิน่าล่ะ ชื่อคุ้นๆ ที่แท้ก็เป็นคนเขียนหนังสือเล่มนี้นี่เอง