search
LoginSignup
0
Help us understand the problem. What are the problem?

posted at

updated at

【Python】令和4年度春期応用情報技術者試験 プログラミング問題

問題

IPA公式HPの以下を参照。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2022r04.html

深さ優先探索での解法(前半部)

コード

ans.py
import pprint

MAX_BOARD = 81

board = [2,0,1,0,9,0,7,0,0,
         0,4,0,2,0,0,3,0,0,
         5,0,0,0,0,8,0,2,9,
         0,9,0,6,7,0,2,0,0,
         6,0,0,3,0,5,0,0,4,
         0,0,7,0,4,9,0,1,0,
         7,6,0,9,0,0,0,0,3,
         0,0,9,0,0,6,0,4,0,
         0,0,4,0,1,0,6,0,0]

def solve(x):
    if x > MAX_BOARD-1:
        print_board()
        return
    else:
        if board[x] != 0:
            solve(x+1)
        else:
            for n in range(1,10):
                if check_ok(n,x):
                    board[x] = n
                    solve(x+1)
                    board[x] = 0

def row_ok(n,x):
    row_top = div(x,9) * 9
    for i in range(9):
            if board[row_top+i] == n:
                return False
    return True

def column_ok(n,x):
    column_top = mod(x,9)
    for i in range(9):
            if board[column_top+9*i] == n:
                return False
    return True

def frame_ok(n,x):
    frame_top = x - 9 * mod(div(x, 9), 3) - mod(x,3)
    for i in range(3):
        for j in range(3):
            if board[frame_top + 9*i + j] == n:
                return False
    return True


def check_ok(n,x):
    return all([row_ok(n,x),column_ok(n,x),frame_ok(n,x)])

def div(n,m):
    return n//m

def mod(n,m):
    return n%m

def print_board():
    pprint.pprint(board, width=28, compact = True)


def main():
    print("Before solve")
    print_board()
    print("After solve")
    solve(0)

main()

実行結果

Before solve
[2, 0, 1, 0, 9, 0, 7, 0, 0,
 0, 4, 0, 2, 0, 0, 3, 0, 0,
 5, 0, 0, 0, 0, 8, 0, 2, 9,
 0, 9, 0, 6, 7, 0, 2, 0, 0,
 6, 0, 0, 3, 0, 5, 0, 0, 4,
 0, 0, 7, 0, 4, 9, 0, 1, 0,
 7, 6, 0, 9, 0, 0, 0, 0, 3,
 0, 0, 9, 0, 0, 6, 0, 4, 0,
 0, 0, 4, 0, 1, 0, 6, 0, 0]
After solve
[2, 8, 1, 4, 9, 3, 7, 6, 5,
 9, 4, 6, 2, 5, 7, 3, 8, 1,
 5, 7, 3, 1, 6, 8, 4, 2, 9,
 4, 9, 5, 6, 7, 1, 2, 3, 8,
 6, 1, 8, 3, 2, 5, 9, 7, 4,
 3, 2, 7, 8, 4, 9, 5, 1, 6,
 7, 6, 2, 9, 8, 4, 1, 5, 3,
 1, 5, 9, 7, 3, 6, 8, 4, 2,
 8, 3, 4, 5, 1, 2, 6, 9, 7]

バックトラック法での解法(後半部)

(作成中。。)

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?