Solving Sudoku with Python (Part 2)

IPFactory Advent Calender 2019 Day 14

I'm pycys from IP Factory and ISC 1st year. This is the second part of Sudoku in Python.

The program below cannot solve problems that require temporary placement in the process of solving. Please be careful when referring to it.

I wrote the code

I was finally able to do it. Most problems should be solved in less than a second. I wrote the algorithm as it is to make it in time, so it is not easy to read. I will write it neatly later. There is also an added algorithm, so I will write an article later including an explanation of it.

nampre.py

import time, copy as cp

#3 × 3 frame n Confirmation judgment&Exclusion process
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

#Column n Confirmation judgment&Exclusion process
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

#Row n Confirmation judgment&Exclusion process
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

#Find a cell that has only one number&Exclusion process
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

#Exception handling 1
def cubic_tumor_excluder():
    flag = False
    #3x3 frame 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)
    #Row 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)
    #Column 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

#Reverse version of exception 1
def remainder_excluder():
    flag = False
    #3x3 frame
    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
    #side
    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
    #Vertical
    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

#Exception handling 2
def line_confirm():
    flag = False
    for i in range(3):
        for j in range(3):
            #Horizontal processing
            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)
            #Vertical processing
            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

#3D array Play the same numbers from the same column
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]

#3D array Play the same numbers from the same row
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]
    
#3D array Play the same number from the same frame
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]

#For output
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|---|---|---|---|---|---|---|---|---|")


#Measure time
start = time.time()

#Input & format to 2D array
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)

#3D array generation for unconfirmed number reference
unconfirmed_numbers = [[[n for n in range(1,10)] for j in range(9)] for i in range(9)]

#Processing continuation flag
flag = False

#Number confirmed subscript
subscripts = set()

#3D array scraping
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]")