Technically Impossible

Lets look at the weak link in your statement. Anything "Technically Impossible" basically means we haven't figured out how yet.

42 SILICON VALLEY Piscine 2017 Rush01(後編) 「難しい」数独を解くプログラム

42 SILICON VALLEY Piscine 2017にはRushと呼ばれるグループ・プロジェクトが含まれている。3つの課題のうちの一つが、数独ナンプレ)を解くプログラムの作成だった。

分からなければインターネット検索し、それでも分からなければ人に聞け、というのが42の学習スタンスだ。数独の解析プログラムの実装は、私にとってはそれを追体験するための格好の題材だった。予定のない正月三が日に集中して取り組んでみた。
1月1日の朝6時に着手し、「簡単な」数独を解けるまでの実装に、2日の午後までを要した。「難しい」数独を解けるまでの実装が完了したのが、3日の14時ごろだった。

今回はいつもとは異なり、プログラムを紹介することを目的とした投稿ではない。サンプル・コードを掲載しているとはいえ、主に紹介するのは、数独が解けるまでの実装についての記録だ。海外Piscine受講者が日々の活動をブログへを投稿している。それと同じような雰囲気を意識している。

前回、「簡単な」数独が解けるまでの記録を投稿した。今回は「難しい」数独が解けるまでの記録だ。前回の投稿を前提として記述しており、必要とされる説明の一部には、前回の投稿でだけ言及しているものがある。読み進める前に、前回の投稿に目を通してほしい。

今回は、一から自分で考えた結果ではなく、とあるサイトの情報を参考に、自分なりに実装した結果をまとめている。サンプル・コードは私が書いたもので、参照サイトのものとは大きく異なるのだが、基本的なロジックは一緒だ。
いつも通り、サンプル・コードはPythonで記述した。Piscine受講生に配慮して、C言語的な記述になるよう配慮しているが、いつも以上に読みにくいのではないかと思う。理由は前回説明した。

準備

Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io

実装作業は、次のサイトを参照しながら進めている。実装されるコードは異なるものの、そのロジックはこのサイトで言及されているものだ。
www.aoky.net

適切なロジックを理解する。

「難しい」数独を解くためには何が欠けているのか?テスト結果を確認すると、各マスの候補番号を1つに絞り切れないまま、プログラムが終了している。これらをさらに絞り込むための追加処理が必要なのだ。

この未完成な回答を新たなパズルとして、候補番号の長さが2つ以上のマスに対する検証処理を実装することになる。この検証処理をオリジナルではsearchと呼んでいる。searchはこのような手順を実装している。

  1. 候補番号の長さが最短のマスを特定する。
  2. 候補番号の一つが確定したと仮定して、assignを実行する。
    1. このassign以降の処理は、前回の処理と同一。
    2. assignは不完全な回答を提示するかもしれない。これを新たなパズルとしてsearchを再帰する。
  3. 全マスの候補番号の長さが1になれば、それが回答。
  4. searchを最初に呼び出したパズルの終わりまで処理を繰り返す。

特定マスの値を<仮定>することで、その結果を「探索」する試みだ。一見、総当たり的な試みなのだが、候補数が少ない順に処理を進めることで、効率的に対処していることが分かる。
<仮定>に際し、バックトラックを使用していない。過程に伴う処理分岐が多すぎるため、バックトラックの巻き戻しは複雑さを伴う。数独の場合は、特定マス一つに対して、番号を一つを保存するだけでは済まず、その仮定の結果生じたピア、ユニットへの変化も巻き戻す必要がある。これの複雑さを回避するため、オリジナルは検証の度にパズル(不完全な回答)を複製し、複製に対して検証を実施している。

写経-ロジックを理解し、書き直す。繰り返して理解を深める。

このロジックを理解するためオリジナルを書き写すのだが、その前にやらなければならないことがある。前回、私はロジックをそのままに、プログラムの構成を独自に変更していた。主要関数の返り値をTrue/Falseにし、回答となるmy_workbdをグローバル変数として実装していた。これらをオリジナルの構成に準拠させなければならない。次のように変更することにした。

  • 主要関数の返り値をworkbd(オリジナルのvaluesに相当)に変更した。
    • ただし矛盾が生じた場合にはNoneを返す。

NoneはCで言うところのNullポインタと認識してもらえば、当たらずとも遠からずだ。指し示す先が「何もない」、つまりNoneだ。Piscine受講生がサンプル・コードを真似るならば、Noneの代わりにNullポインタを代用することになるだろう。
searchに関する実装を始める前に、これらの変更を反映し、プログラムが正常に動作することを確認しておく。

オリジナルで言うsearchを、サンプルではexploreとして実装している。パズルの中で、候補番号の長さが最短であるマスの座標を特定する処理、全マスで、候補番号の長さが1になったかを検証する処理をそれぞれ、関数getMinPos、isAll1をとして実装した。
補助的な関数を除いて、新しい実装はこれだけだ。その他の処理は前回までのコードを踏襲している。
全体の構成はこのようになった。末尾のサンプル・コードは、ここまでを実装したものだ。
前回までの処理を実行する。そこで出力された結果を新たなパズルとしてexploreが実行される。exploreの再帰を除いて、explorer以降の処理は、前回までの処理と同様であることが分かる。
f:id:espio999:20200104121241p:plain

ハマり処

1月3日、11時までには、ここまでの実装を終えていた。バグがないのは結構なことだが、実は気づいていないだけ、ということもある。
今回の実装では、ハマり処と言われるような場面に遭遇することはなかったのだが、次の悩みどころがあった。

  1. isAll1 == True時の回答を保存する。
  2. isAll1 == Trueならば、即座にプログラムを終了させたい。

参照サイトには次の言及がある。

あいにくとこの問題には解が複数あって本当の数独パズルとは言えない。

どうやら一つのパズルが複数の回答を持つことがあるようだ。おそらくオリジナルの次の箇所は、それらを全て捉えることを意図したのだろう。

    return some(search(assign(values.copy(), s, d)) 
		for d in values[s])
 
def some(seq):
    "seqの要素からtrueであるものをどれか返す。"
    for e in seq:
        if e: return e
    return False

しかしPiscineでは無用の対応だ。回答は一つだけ、と課題は言及している。

• A valid sudoku has only one possible solution.

exploreは再帰する。ループ処理ではないので、isAll1がTrueだからと言って、一連の処理から抜け出ることはできない。再帰中、workbdは複製され続けるのだが、再帰処理の途上で見つかった回答は、再帰元に戻るまでに更新されてしまうかもしれない。これを同時に解決する方法を考えたのだが、結局は安直な方法に走ってしまった。
isAll1 == Trueの回答を、グローバル変数のmy_workbdに保存する。そして、すべての再起が終了するのを待つ。それだけだ。

実行結果

テスト結果を投稿末尾に掲載している。
Piscine資料のに掲載されている問題、オリジナルのgrid1に指定された問題は、前回同様、良好な結果を得られた。
問題は次の難問だ。こちらも良好な回答を得ることができた。

ここまでで1月3日のお昼過ぎ、2時前くらい。
本来グループワークである課題を、個人課題としてこなしたのはイレギュラーだが、仮にグループワークを金曜日に始めたとしたならば、日曜日中の提出には間に合ったという格好だ。

By Odin, by Thor ! Use your brain !!!

テスト結果

Piscine掲載の問題

 "9...7...." "2...9..53" ".6..124.." "84...1.9." "5.....8.." ".31..4..." "..37..68."
914|375|268
287|496|153
365|812|479
---+---+---
846|521|397
529|637|814
731|984|526
---+---+---
153|749|682
698|253|741
472|168|935

914375268
287496153
365812479
846521397
529637814
731984526
153749682
698253741
472168935

grid1指定の問題

'..3.2.6..' '9..3.5..1' '..18.64..' '..81.29..' '7.......8' '..67.82..' '..26.95..' '8..2.3..9' '..5.1.3..'
483|921|657
967|345|821
251|876|493
---+---+---
548|132|976
729|564|138
136|798|245
---+---+---
372|689|514
814|253|769
695|417|382

483921657
967345821
251876493
548132976
729564138
136798245
372689514
814253769
695417382

難問

'4.....8.5' '.3.......' '...7.....' '.2.....6.' '....8.4..' '....1....' '...6.3.7.' '5..2.....' '1.4......'
417|369|825
632|158|947
958|724|316
---+---+---
825|437|169
791|586|432
346|912|758
---+---+---
289|643|571
573|291|684
164|875|293

417369825
632158947
958724316
825437169
791586432
346912758
289643571
573291684
164875293

サンプル・コード

# coding: utf-8
# Your code here!

def make_puzzle(args):
    puzzle = []
    row = []
    i = 0
    
    for c in args:
        row.append(c)
        
        if (i + 1) % 9 == 0:
            puzzle.append(row)
            row = []
        
        i += 1
    
    return puzzle

def make_workbd():
    digits = '123456789'
    workbd = []
    row = []
    c = 0
    r = 0
    
    while r < 9:
        while c < 9:
            row.append(digits)

            if (c + 1) % 9 == 0:
                workbd.append(row)
                row = []
                c = 0
                r += 1
                break
            else:
                c += 1
    
    return workbd

def print_workbd(isGrid):
    r = 0
    c = 0
    buf = ''
    
    while r < 9:       
        while c < 9:
            buf += my_workbd[r][c]
            
            if isGrid == True and (c == 2 or c == 5):
                buf += '|'

            c += 1
            
        buf += '\n'

        if isGrid == True and (r == 2 or r == 5):
            buf += '---+---+---\n'

        c = 0
        r += 1
    
    print(buf)

def update_workbd(workbd, r, c, d, isOW):
    try_num = workbd[r][c]
    buf = ''
    
    for i in try_num:
        if i == d:
            continue
        
        buf += i
    
    if isOW == True:
        workbd[r][c] = buf
    
    return buf

def search_number(num, val):
    for i in val:
        if i == num:
            return True
        
    return False

def get_box_range(val):
    if 0 <= val and val <= 2:
        return 0
    elif 3 <= val and val <= 5:
        return 3
    elif 6 <= val and val <= 8:
        return 6

def get_pos(r, c, isPeer):
    pos = []
    row = []
    col = []
    box = []
    sr = get_box_range(r)
    sc = get_box_range(c)
    
    #row
    i = 0
    while i < 9:
        if isPeer == True and (i == sc or i == sc + 1 or i == sc + 2):
            i += 1
            continue
        
        pos.append(r)
        pos.append(i)
        row.append(pos)
        pos = []
        i += 1
    
    #column
    i = 0
    while i < 9:
        if isPeer == True and (i == sr or i == sr + 1 or i == sr + 2):
            i += 1
            continue
        
        pos.append(i)
        pos.append(c)
        col.append(pos)
        pos = []
        i += 1

    #box
    x = sc
    y = sr
    while y < sr + 3:
        while x < sc + 3:
            if isPeer == True and x == c and y == r:
                x += 1
                continue

            pos.append(y)
            pos.append(x)
            box.append(pos)
            pos = []
            x += 1

        x = sc
        y += 1

    return row + col + box

def check_peer(workbd, r, c, d):
    for peer_pos in get_pos(r, c, True):
        if eliminate(workbd, peer_pos[0], peer_pos[1], d) is None:
            return None
    
    return workbd

def check_unit(workbd, r, c, d):
    psbl_pos = []
    for unit_pos in get_pos(r, c, False):
        y = unit_pos[0]
        x = unit_pos[1]

        if search_number(d, workbd[y][x]) == True:
            psbl_pos.append(unit_pos)

    l = len(psbl_pos)
    if l == 0:
        return None
    elif l == 1:
        y = psbl_pos[0][0]
        x = psbl_pos[0][1]

        if assign(workbd, y, x, d) is None:
            return None

    return workbd
        
def eliminate(workbd, r, c, d):
    cell = workbd[r][c]
    
    if search_number(d, cell) == False:
        return workbd
    
    cell = update_workbd(workbd, r, c, d, True)
    
    l = len(cell)
    if l == 0:
        return None
    elif l == 1:
        if check_peer(workbd, r, c, cell) is None:
              return None

    if check_unit(workbd, r, c, d) == None:
        return None
    return workbd

def assign(workbd, r, c, d):
    psbl_num = update_workbd(workbd, r, c, d, False)
    
    for try_num in psbl_num:
        if eliminate(workbd, r, c, try_num) is None:
            return None
    
    return workbd

def isAll1(workbd):
    r = 0
    c = 0
    
    while r < 9:
        while c < 9:
            if len(workbd[r][c]) != 1:
                return False
            
            c += 1
        c = 0
        r += 1
    
    return True

def findMinPos(psbl_pos, psbl_min):
    real_min = psbl_min[0]
    real_pos = 0
    
    for i in range(len(psbl_min)):
        m = psbl_min[i]
        
        if real_min > m:
            real_min = m
            real_pos = i

    return psbl_pos[real_pos]
    
def getMinPos(workbd):
    r = 0
    c = 0
    psbl_min = 0
    psbl_pos = []
    ret_min = []
    ret_pos = []
    
    while r < 9:
        while c < 9:
            psbl_min = len(workbd[r][c])
            
            if psbl_min > 1:
                ret_min.append(psbl_min)
                psbl_pos.append(r)
                psbl_pos.append(c)
                ret_pos.append(psbl_pos)
                psbl_pos = []
            
            c += 1
        
        c = 0
        r += 1
    
    return findMinPos(ret_pos, ret_min)
               
def explore(workbd):
    import copy
    
    if workbd is None:
        return None

    if isAll1(workbd) == True:
        global my_workbd
        my_workbd = workbd
        return workbd

    min_pos = getMinPos(workbd)
    r = min_pos[0]
    c = min_pos[1]

    for try_num in workbd[r][c]:       
        wbd_copy = copy.deepcopy(workbd)
        
        if assign(wbd_copy, r, c, try_num) is None:
            continue
        
        explore(wbd_copy)        

#42SV Piscine 2017 sample
#args = "9...7...." "2...9..53" ".6..124.." "84...1.9." "5.....8.." ".31..4..." "..37..68." ".9..5.741" "47......."

#easy
#args = '..3.2.6..' '9..3.5..1' '..18.64..' '..81.29..' '7.......8' '..67.82..' '..26.95..' '8..2.3..9' '..5.1.3..'

#hard
args = '4.....8.5' '.3.......' '...7.....' '.2.....6.' '....8.4..' '....1....' '...6.3.7.' '5..2.....' '1.4......'

my_puzzle = make_puzzle(args)
my_workbd = make_workbd()

r = 0
c = 0
while r < 9:
    while c < 9:
        d = my_puzzle[r][c]
        if d != '.':
            assign(my_workbd, r, c, d)
        c += 1
    
    c = 0
    r += 1

explore(my_workbd)

print_workbd(True)
print_workbd(False)