BOJ 2580潜水艦

質問する

アルゴリズム#アルゴリズム#

コード#コード#

import sys

input = sys.stdin.readline

# find empty place
def findEmpty():
    for i in range(9):
        for j in range(9):
            if table[i][j] == 0:
                return (i, j)
    
    return (-1, -1)


# check that X can be written in (r, c)
def check(r, c, x):
    
    # check 3 by 3 table
    for i in range(3):
        if x in table[3 * (r // 3) + i][3 * (c // 3) : 3 * (c // 3) + 3]:
            return False

    # check row, column
    if x in table[r]:
        return False
    
    for i in range(9):
        if x == table[i][c]:
            return False

    return True


def DFS():
    global table

    r, c = findEmpty()

    if r == -1 and c == -1:
        return True

    else:
        for nn in range(1, 10):
            if check(r, c, nn):
                table[r][c] = nn
                # go next (recurrsive)
                if DFS(): return True

                # not fit - back tracking
                table[r][c] = 0

        return False

point = []
table = []
for _ in range(9):
    table.append(list(map(int, input().split())))

# print(table)

DFS()

# print(table)

for row in table:
    for col in row:
        print(col, end=' ')
    print()

結果