データ構造

一般的な二次元配列で表現します。

def values_from_grid(grid):
    "テキストから２次元配列のvaluesを作成する"
    values = []
    digits = "123456789"
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    grid_int = map(lambda x: int(x) if x != "." else 0, chars)

    count = 0
    row = []
    for i in grid_int:
        row.append(i)
        count += 1
        if count % 9 == 0: #行毎に分割
            values.append(row)
            row = []
    return values

テキストを読み込んで二次元配列に変換する関数です。
テキストの形式は空欄を0または.で表現したものでそれ以外の数字を順番に登録して
81文字であればOKとしています。
下記のテキスト形式等に対応しています。

..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..

8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .

プログラム

深さ優先探索で再帰的にチェックします。
呼び出し方は

values = values_from_grid(数独データ)
solver(values)

です。solver関数にvaluesを渡します。解き終えるとvaluesが答えの配列になっています。

メイン関数

左上のマスから右下のマスまで、1マスづつ1から9の数字を当てはめます。
この時当てはめる数字が「縦・横・3×3」のマスになかった場合のみ数字を当てはめます。
xは横軸、yは縦軸を表しています。xが8になったら、つまり横軸の最後に達したら
縦軸を一つ下にして横軸を0にして、下の行の一番初めのマスをチェックします。
最後のマスに達したら問題が解けているのでTrueを返します。

def solver(values, x=0, y=0):
    "数独を解く"
    if y > 8: #ポインタが最後までいったら完成
        return True
    elif values[y][x] != 0: #空欄ではないなら飛ばす
        if x == 8: #8列までいったら次の行に移動
            if solver(values, 0, y+1):
                return True
        else:
            if solver(values, x+1, y):
                return True
    else:
        for i in range(1, 10):#1から9までの数字を全て試す
            if check(values, x, y, i): #チェックする
                values[y][x] = i #OKなら数字を入れる
                if x == 8: #8列までいったら次の行に移動
                    if solver(values, 0, y+1):
                        return True
                else:
                    if solver(values, x+1, y):
                        return True
        values[y][x] = 0 #戻ってきたら0に戻す
        return False

返り値はTrueかFalseを返します。解けたらTrueです。

チェック関数

横軸・縦軸・3*3の領域をチェックします。
それぞれの関数を呼び出す関数です。

def check(values, x, y, i):
    if row(values, y, i) and column(values, x, i) and block(values, x, y, i):
        return True
    return False

横軸のチェック

横軸をチェックするために現在の行を示す縦軸の値を引数に取ります。
iは入れようとしている数字です。
横軸を1マスずつチェックして、入れようとしている数字と同一ならFalse、ではないなら
Trueのリストを作成し、それをall関数でチェックします。
全てTrueなら数字の重複はなしでTrueを返します。
一つでも重複があればFalseを返します。

def row(values, y, i):
    "横をチェック"
    return all(True if i != values[y][_x] else False for _x in range(9))

縦軸のチェック

横軸のチェックを縦軸にしただけです。

def column(values, x, i):
    "縦をチェック"
    return all(True if i != values[_y][x] else False for _y in range(9))

3×3のチェック

以下の関数はPythonで数独ソルバーを実装したを参考に作成しました。
0~8の数を3で割って小数点以下を削除した値を3倍するとそれぞれ0, 3, 6が得られるため
マス目が所属しているブロックが分かる、という理屈です。

def block(values, x, y, i):
    "3x3のブロックをチェック"
    xbase = (x // 3) * 3
    ybase = (y // 3) * 3
    return all(True if i != values[_y][_x] else False
            for _y in range(ybase, ybase + 3)
                for _x in range(xbase, xbase + 3))

実行例

問題
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 . 

回答
[8, 5, 9, 6, 1, 2, 4, 3, 7]
[7, 2, 3, 8, 5, 4, 1, 6, 9]
[1, 6, 4, 3, 7, 9, 5, 2, 8]
[9, 8, 6, 1, 4, 7, 3, 5, 2]
[3, 7, 5, 2, 6, 8, 9, 1, 4]
[2, 4, 1, 5, 9, 3, 7, 8, 6]
[4, 3, 2, 9, 8, 1, 6, 7, 5]
[6, 1, 7, 4, 2, 5, 8, 9, 3]
[5, 9, 8, 7, 3, 6, 2, 4, 1]

このパズルを解くのにこのプログラムは私の環境で大体23秒かかりました。
それに対してあらゆる数独パズルを解くにあるプログラムは0.01秒で解きます。
これはあらゆる数独パズルを解くは「取り得る値が１つに決定できるマスを埋めると、他のマスも同様に埋まる」という戦略を実行して、それでも埋まらないマスはマスごとに取り得る値のみ探索して解を求めているからです。
このプログラムは例え9しか入らないマスでも1から8までチェックしていますし、縦・横・3×3のマス目をチェックする際にそれぞれ重複するマス目が発生しますがそれも個別にチェックしています。
なので遅いです。

参考サイト

あらゆる数独パズルを解く
 Pythonで数独ソルバーを実装した

Pythonで数独を解く