글 읽기 - python 스도쿠 질문입니다.

ssw02041 3년 전 0

총 2가지 질문이 있습니다.

1. find_ans의 return 관련 질문

첨부된 코드 중 find_ans 함수에서 이해가 안되는 부분이 있습니다.

81개의 칸 중 완성되지 않은 칸(값이 0 인 index)이 없으면 스도쿠 문제를 다 푼 것으로 간주하여 찾은 해답을 출력합니다. (print_board(board)로 출력)

문제는 그 다음 return board 로 array를 리턴하게 되면 None이 리턴됩니다.

그래서 처음에는 print_board(find_ans(Q))로 정답을 출력하려 하였으나, print_board함수를 find_ans함수 내부로 옮기게 되었습니다.

왜 None이 출력되는지 고수님들께 여쭤봅니다.

2. 시간초과 질문

시간을 더 줄이기 위한 아이디어가 특별히 생각나지 않는데 이 부분에 있어서 첨언 해주시면 감사하겠습니다.

import sys
import time

def return_row(x, board):#position x 의외의 원소들 출력
    nrow=int(x / 9)
    row=[]
    for i in range(0,9):
        if i != x % 9:
            row.append(board[nrow*9+i])
    return row

def return_col(x, board):
    ncol=x % 9
    col=[]
    for i in range(0,9):
        if i != int(x/9):
            col.append(board[ncol+9*i])
    return col

def return_box(x, board):
    nrow = int(x/9)
    ncol = x%9
    if nrow <=2:
        start=0
    else:
        if nrow <=5:
            nrow-=3
            start=9*3
        else:
            if nrow<=8:
                nrow-=6
                start=9*6
    if ncol <=2:
        start+=0
    else:
        if ncol <=5:
            ncol-=3
            start+=3
        else:
            if ncol<=8:
                ncol-=6
                start+=6
    box=[]
    for i in range(0,3):
        for j in range(0,3):
            if i != nrow or j != ncol:
                box.append(board[start+i*9+j])
    return box

def check(x, value, board):#x is position, value must be in range of 1~9
    if return_row(x, board).count(value) > 0:
        return False
    if return_col(x, board).count(value) > 0:
        return False
    if return_box(x,board).count(value) > 0:
        return False
    return True

def print_board(board):
    for i in range(0,9):
        s=""
        for j in range(0,9):
            s+=str(board[9*i+j])+" "
        print(s)

def find_ans(board):
    temp=-1
    for i in range(0,81):
        if board[i] == 0:
            temp=i
            break
    if temp == -1:
        print_board(board)
        return board
    else:
        for x in range(1,10):
            if check(i,x,board):
                next_board=board[:]
                next_board[i]=x
                find_ans(next_board)


Q=[]
for i in range(0,9):
    Q.extend(list(map(int, sys.stdin.readline().split())))

find_ans(Q)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 스도쿠 질문입니다.

ssw02041 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말