LoginSignup
3
0

More than 3 years have passed since last update.

ナンプレをPythonで解く(後編)

Last updated at Posted at 2019-12-14

IPFactory Advent Calender 2019 14日目

IPFactory所属、ISC 1年のpycysです。
ナンプレをPythonで解くの後編です。

下記のプログラムでは、解く過程で仮置きを必要とする問題は解けないため、
参考にする際は気をつけてください。

コード書いたよ

やっとできました。
大抵の問題は1秒以内で解けるはずです。
間に合わせるためにアルゴリズムをそのまま書いたので、読みやすくは書かれていません。
後でもうちょい綺麗に書きます。
追加したアルゴリズムもあるので、それの説明も含め後日また記事書きます

nampre.py
import time, copy as cp

# 3×3枠n確定判定&排除処理
def cubic_frame_judgment():
    flag = False
    for i in range(3):
        for j in range(3):
            indices = [() for n in range(9)]
            for sub_i in range(i*3, i*3+3):
                for sub_j in range(j*3, j*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        indices[num-1] = (sub_i, sub_j) if not indices[num-1] else (9,9)
            for index in indices:
                if index != (9,9) and index not in subscripts:
                    flag = True
                    nampre[index[0]][index[1]] = indices.index(index)+1
                    column_excluder(index[0], index[1], indices.index(index)+1)
                    row_excluder(index[0], index[1], indices.index(index)+1)
                    cubic_frame_excluder(index[0], index[1], indices.index(index)+1)
                    subscripts.add((index[0], index[1]))
    return flag

# 縦列n確定判定&排除処理
def column_judgment():
    flag = False
    for j in range(9):
        indices = [() for n in range(9)]
        for i in range(9):
            for num in unconfirmed_numbers[i][j]:
                indices[num-1] = (i, j) if not indices[num-1] else (9,9)
        for index in indices:
            if index != (9,9) and index not in subscripts:
                flag = True
                nampre[index[0]][index[1]] = indices.index(index)+1
                column_excluder(index[0], index[1], indices.index(index)+1)
                row_excluder(index[0], index[1], indices.index(index)+1)
                cubic_frame_excluder(index[0], index[1], indices.index(index)+1)
                subscripts.add((index[0], index[1]))
    return flag

# 横列n確定判定&排除処理
def row_judgment():
    flag = False
    for i in range(9):
        indices = [() for n in range(9)]
        for j in range(9):
            for num in unconfirmed_numbers[i][j]:
                indices[num-1] = (i, j) if not indices[num-1] else (9,9)
        for index in indices:
            if index != (9,9) and index not in subscripts:
                flag = True
                nampre[index[0]][index[1]] = indices.index(index)+1
                column_excluder(index[0], index[1], indices.index(index)+1)
                row_excluder(index[0], index[1], indices.index(index)+1)
                cubic_frame_excluder(index[0], index[1], indices.index(index)+1)
                subscripts.add((index[0], index[1]))
    return flag

# 置ける数字が1つしかないマスを探す&排除処理
def only_one_judgment():
    flag = False
    for i in range(9):
        for j in range(9):
            if len(unconfirmed_numbers[i][j]) == 1 and (i,j) not in subscripts:
                flag = True
                num = unconfirmed_numbers[i][j][0]
                nampre[i][j] = num
                column_excluder(i, j, num)
                row_excluder(i, j, num)
                cubic_frame_excluder(i, j, num)
                subscripts.add((i,j))
    return flag

# 例外処理1
def cubic_tumor_excluder():
    flag = False
    # 3×3枠check
    for i in range(3):
        for j in range(3):
            overlapping_numbers = [[] for i in range(9)]
            for sub_i in range(i*3, i*3+3):
                for sub_j in range(j*3, j*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        overlapping_numbers[num-1].append((sub_i, sub_j))
            for index_box in overlapping_numbers:
                if overlapping_numbers.count(index_box) == len(index_box) >= 2:
                    nums = [index+1 for index, indices in enumerate(overlapping_numbers) if indices == index_box]
                    for index in index_box:
                        if unconfirmed_numbers[index[0]][index[1]] != nums:
                            flag = True
                            unconfirmed_numbers[index[0]][index[1]] = cp.deepcopy(nums)
    # 横列check
    for i in range(9):
        overlapping_numbers = [[] for i in range(9)]
        for j in range(9):
            for num in unconfirmed_numbers[i][j]:
                overlapping_numbers[num-1].append((i, j))
        for index_box in overlapping_numbers:
            if overlapping_numbers.count(index_box) == len(index_box) >= 2:
                nums = [index+1 for index, indices in enumerate(overlapping_numbers) if indices == index_box]
                for index in index_box:
                    if unconfirmed_numbers[index[0]][index[1]] != nums:
                        flag = True
                        unconfirmed_numbers[index[0]][index[1]] = cp.deepcopy(nums)
    # 縦列check
    for j in range(9):
        overlapping_numbers = [[] for i in range(9)]
        for i in range(9):
            for num in unconfirmed_numbers[i][j]:
                overlapping_numbers[num-1].append((i, j))
        for index_box in overlapping_numbers:
            if overlapping_numbers.count(index_box) == len(index_box) >= 2:
                nums = [index+1 for index, indices in enumerate(overlapping_numbers) if indices == index_box]
                for index in index_box:
                    if unconfirmed_numbers[index[0]][index[1]] != nums:
                        flag = True
                        unconfirmed_numbers[index[0]][index[1]] = cp.deepcopy(nums)
    return flag

# 例外1の逆バージョン
def remainder_excluder():
    flag = False
    # 3×3枠
    for i in range(3):
        for j in range(3):
            cubic_frame_nums = []
            for sub_i in range(i*3, i*3+3):
                for sub_j in range(j*3, j*3+3):
                    cubic_frame_nums.append(cp.deepcopy(unconfirmed_numbers[sub_i][sub_j]))
            for nums in cubic_frame_nums:
                if len(nums) == cubic_frame_nums.count(nums) > 1:
                    for sub_i in range(i*3, i*3+3):
                        for sub_j in range(j*3, j*3+3):
                            if unconfirmed_numbers[sub_i][sub_j] != nums:
                                for num in nums:
                                    if num in unconfirmed_numbers[sub_i][sub_j]:
                                        unconfirmed_numbers[sub_i][sub_j].remove(num)
                                        flag = True
    # 横
    for i in range(9):
        row_line_nums = []
        for j in range(9):
            row_line_nums.append(cp.deepcopy(unconfirmed_numbers[i][j]))
        for nums in row_line_nums:
            if len(nums) == row_line_nums.count(nums) > 1:
                for j in range(9):
                    if unconfirmed_numbers[i][j] != nums:
                        for num in nums:
                            if num in unconfirmed_numbers[i][j]:
                                unconfirmed_numbers[i][j].remove(num)
                                flag = True
    # 縦
    for j in range(9):
        column_line_nums = []
        for i in range(9):
            column_line_nums.append(cp.deepcopy(unconfirmed_numbers[i][j]))
        for nums in column_line_nums:
            if len(nums) == column_line_nums.count(nums) > 1:
                for i in range(9):
                    if unconfirmed_numbers[i][j] != nums:
                        for num in nums:
                            if num in unconfirmed_numbers[i][j]:
                                unconfirmed_numbers[i][j].remove(num)
                                flag = True
    return flag

# 例外処理2
def line_confirm():
    flag = False
    for i in range(3):
        for j in range(3):
            # 横処理
            row_lines = []
            for sub_i in range(i*3, i*3+3):
                row_line = []
                for sub_j in range(j*3, j*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        row_line.append(num)
                row_lines.append(list(set(row_line)))
            exclusive_union = row_lines[0] + row_lines[1] + row_lines[2]
            exclusive_union = [num for num in exclusive_union if not exclusive_union.count(num) >= 2]
            if exclusive_union:
                for number in exclusive_union:
                    for row in row_lines:
                        if number in row:
                            row_i = i*3+row_lines.index(row)
                            for sub_j in range(0, j*3):
                                if number in unconfirmed_numbers[row_i][sub_j] and len(unconfirmed_numbers[row_i][sub_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[row_i][sub_j].remove(number)
                            for sub_j in range(j*3+3, 9):
                                if number in unconfirmed_numbers[row_i][sub_j] and len(unconfirmed_numbers[row_i][sub_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[row_i][sub_j].remove(number)
            # 縦処理
            column_lines = []
            for sub_j in range(j*3, j*3+3):
                column_line = []
                for sub_i in range(i*3, i*3+3):
                    for num in unconfirmed_numbers[sub_i][sub_j]:
                        column_line.append(num)
                column_lines.append(list(set(column_line)))
            exclusive_union = column_lines[0] + column_lines[1] + column_lines[2]
            exclusive_union = [num for num in exclusive_union if not exclusive_union.count(num) >= 2]
            if exclusive_union:
                for number in exclusive_union:
                    for column in column_lines:
                        if number in column:
                            column_j = j*3+column_lines.index(column)
                            for sub_i in range(0, i*3):
                                if number in unconfirmed_numbers[sub_i][column_j] and len(unconfirmed_numbers[sub_i][column_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[sub_i][column_j].remove(number)
                            for sub_i in range(i*3+3, 9):
                                if number in unconfirmed_numbers[sub_i][column_j] and len(unconfirmed_numbers[sub_i][column_j]) > 1:
                                    flag = True
                                    unconfirmed_numbers[sub_i][column_j].remove(number)
    return flag

# 3次元配列同縦列から同じ数字を弾く
def column_excluder(i, j, n):
    flag = False
    for sub_i in range(9):
        if n in unconfirmed_numbers[sub_i][j]:
            unconfirmed_numbers[sub_i][j].remove(n)
            flag = True
    unconfirmed_numbers[i][j] = [n]

# 3次元配列同横列から同じ数字を弾く
def row_excluder(i, j, n):
    flag = False
    for sub_j in range(9):
        if n in unconfirmed_numbers[i][sub_j]:
            unconfirmed_numbers[i][sub_j].remove(n)
            flag = True
    unconfirmed_numbers[i][j] = [n]

# 3次元配列同枠内から同じ数字を弾く
def cubic_frame_excluder(i, j, n):
    flag = False
    for sub_i in range(i//3*3, i//3*3+3):
        for sub_j in range(j//3*3, j//3*3+3):
            if n in unconfirmed_numbers[sub_i][sub_j]:
                flag = True
                unconfirmed_numbers[sub_i][sub_j].remove(n)
    unconfirmed_numbers[i][j] = [n]

# 出力用
def nampre_print():
    print("____________________________________")
    for index, nums in enumerate(nampre):
        if index == 8:
            print("|", end="")
            [print(" "+str(n)+" |",end="") for i, n in enumerate(nums)]
            print("\n  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄")
        elif (index+1)%3 == 0:
            print("|", end="")
            [print(" "+str(n)+" |",end="") for i, n in enumerate(nums)]
            print("\n|===|===|===|===|===|===|===|===|===|")
        else:
            print("|", end="")
            [print(" "+str(n)+" |",end="") for i, n in enumerate(nums)]
            print("\n|---|---|---|---|---|---|---|---|---|")


# 時間を測る
start = time.time()

# 入力&2次元配列に整形
nums = [int(i) for i in input().split()]
nampre = [[] for i in range(9)]
for index, i in enumerate(nums):
    nampre[index//9].append(i)

# 未確定数字参照用の3次元配列生成
unconfirmed_numbers = [[[n for n in range(1,10)] for j in range(9)] for i in range(9)]

# 処理継続フラグ
flag = False

# 数字確定済添字
subscripts = set()

# 3次元配列削る
for i in range(9):
    for j in range(9):
        if nampre[i][j] != 0 and (i,j) not in subscripts:
            flag = True
            num = nampre[i][j]
            column_excluder(i, j, num)
            row_excluder(i, j, num)
            cubic_frame_excluder(i, j, num)
            subscripts.add((i,j))

nampre_print()
while flag:
    flag = cubic_frame_judgment() or row_judgment() or column_judgment() or only_one_judgment() or cubic_tumor_excluder() or remainder_excluder() or line_confirm()
nampre_print()
print(str(time.time()-start)+"[sec]")
3
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0