Hatena::Grouppython

Pythonで遊ぶよ

 | 

2009-05-27

数独を解く。

10:25

Haskell から移植。

#!/usr/bin/python

def search(table):
    goal(table) or deepen(table)

def goal(table):
    for row in table:
        for ent in row:
            if ent == 0: return False
    report(table)
    return True

def report(table):
    print( '\n'.join( map(str, table) ) + '\n' )

def find_first_zero(table):
    for i in range(0,9):
        for j in range(0,9):
            if table[i][j] == 0: return (i,j)

def deepen(table):
    i,j = find_first_zero(table)
    for n in candidates(table,i,j):
        search( replace_part(table,i,j,n) )

def candidates(table, i, j):
    cand = set(range(1,10))
    i0, j0 = 3*(i//3), 3*(j//3)
    for ent in table[i] + \
                [table[ii][j] for ii in range(0,9)] + \
                [table[ii][jj] for ii in range(i0,i0+3) for jj in range(j0,j0+3)]:
        cand.discard(ent)
    return cand

def replace_part(table,i,j,n):
    _table = []
    for row in table:
        _table.append(row[:])
    _table[i][j] = n
    return _table

def main():
    table = [
            [1,0,0,0,0,7,0,9,0],
            [0,3,0,0,2,0,0,0,8],
            [0,0,9,6,0,0,5,0,0],
            [0,0,5,3,0,0,9,0,0],
            [0,1,0,0,8,0,0,0,2],
            [6,0,0,0,0,4,0,0,0],
            [3,0,0,0,0,0,0,1,0],
            [0,4,0,0,0,0,0,0,7],
            [0,0,7,0,0,0,3,0,0]]
    search(table)

if __name__ == '__main__':
    main()

実行結果 → http://codepad.org/asEcISOX (上のテーブルとはちょっと違って、何通りも解があるものにした)

解説 → Haskellで数独 - Haskellで遊ぶよ - haskell

Haskell で書いてて、プリントデバッグが非常に面倒だったので、Python に移植してみて Pythonデバッグしたという。。

やっぱ Haskell より Python のほうが書き易いわ。

 |