【Python】パズルの解答を求めるプログラム
令和4年度 春期 応用情報技術者試験 午後問題 問3 に出題された「パズルの解答を求めるプログラム」を Python で作成する。
問題文には掲載されていない図表を用いて，わかりやすく解説しています。
パズルのルール
太線で 3×3 の枠に区切られた 9×9 のマスから成る正方形の盤面に，1～9 の数字を入れるパズルの解答を求めるプログラムを考える。このパズルは，図 1 に示すように幾つかのマスに数字が入れられている状態から，数字の入っていない各升に，1～9 のうちのどれか一つの数字を入れていく。このとき，盤面の横 1 行，縦 1 列，及び太線で囲まれた 3×3 の枠内の全てにおいて，1～9 の数字が一つずつ入ることが，このパズルのルールである。パズルの問題例を図 1 に，図 1 の解答を図 2 に示す。
このパズルを解くための方針を次に示す。
方針
数字が入っていない空白のマスに，1～9 の数字を入れて，パズルのルールにのっとって全部のマスを埋めることができる解答を探索する。
この方針に沿ってパズルを解く手順を考える。
パズルを解く手順
- 盤面の左上端から探索を開始する。マスは左端から順に右方向に探索し，右端に達したら一行下がり，左端から順に探索する。
- 空白のマスを見つける。
- 2. で見つけた空白のマスに，1～9 の数字を順番に入れる。
- 数字を入れたときに，その状態がパズルのルールにのっとっているかどうかをチェックする。
- ルールにのっとっている場合は，2. に進んで次の空白のマスを見つける。
- ルールにのっとっていない場合は，3. に戻って次の数字を入れる。このとき，入れる数字がない場合には，マスを空白に戻して一つ前に数字を入れたマスに戻り，3. から再開する
- 最後のマスまで数字が入り，空白のマスがなくなったら，それが解答となる。
盤面の表現
この手順をプログラムに実装するために，9×9 の盤面を次のデータ構造で表現することにした。
- 9×9 の盤面を 81 個の要素をもつ 1 次元配列 board で表現する。添字は 0 から始まる。各要素にはマスに入れられた数字が格納され，空白の場合は 0 を格納する。
配列 board による盤面の表現を図 3 に示す。ここで括弧内の数字は配列 board の添字を表す。
ルールのチェック方法
パズルのルールにのっとっているかどうかのチェックでは，数字を入れたマスが含まれる横 1 行の左端のマス，縦 1 列の上端のマス，3×3 の枠内のマスを特定し，行，列，枠内のマスに既に格納されている数字と，入れた数字がそれぞれ重複していないことを確認する。このチェックを “重複チェック” という。
横 1 行の重複チェック
横 1 行の重複チェックを行う関数を作成する。
まず，board[x] が含まれる行の左端 (row_top)を探す。row_top は，x を 9 で割り，小数点以下を切り捨て，9 倍することで求められる。
その後，row_top から row_top + 8 まで重複チェックを行う。
def row_ok(n,x):
row_top = x // 9 * 9
for i in range(0,9,1):
if(board[row_top+i]==n):
return False
return True
縦 1 列の重複チェック
縦 1 列の重複チェックを行う関数を作成する。
まず，board[x] が含まれる列の最上段 (column_top) を探す。column_top は，x を 9 で割った余りである。
その後，column_top から縦 1 列の重複チェックを行う。
def column_ok(n,x):
column_top = x % 9
for i in range(0,9,1):
if(board[column_top+9*i]==n):
return False
return True
枠内の重複チェック
3 × 3 の枠内の重複チェックを行う。
まず，board[x] が含まれる枠の左端の最上段 (frame_top) を探す。frame_top は，x を 9 で割り，小数点以下を切り捨て，9 倍し，27 で割った余りから，x を 3 で割った余りを引くことで求められる。
その後，frame_top から枠内の重複チェックを行う。
def frame_ok(n,x):
frame_top = x - (x//9*9)%27 - x%3
for i in range(0,3,1):
for j in range(0,3,1):
if(board[frame_top+9*i+j]==n):
return False
return True解法のプログラム
Python で作成した解法のプログラムを示す。
import sys
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]
MAX_BOARD = 81
# board[] の内容を 9×9 の形に出力する関数
def print_board(board):
for m in range(0,73,9):
print(board[m],board[m+1],board[m+2],'|',board[m+3],board[m+4],board[m+5],'|',board[m+6],board[m+7],board[m+8])
if(m==18 or m==45):
print('---------------------')
# 横 1 行の重複チェックを行う関数
def row_ok(n,x):
row_top = x//9*9
for i in range(0,9,1):
if(board[row_top+i]==n):
return False
return True
# 縦 1 列の重複チェックを行う関数
def column_ok(n,x):
column_top = x % 9
for i in range(0,9,1):
if(board[column_top+9*i]==n):
return False
return True
# 3×3 の枠内の重複チェックを行う関数
def frame_ok(n,x):
frame_top = x - (x//9*9)%27 - x%3
for i in range(0,3,1):
for j in range(0,3,1):
if(board[frame_top+9*i+j]==n):
return False
return True
# row_ok，column_ok，frame_ok を呼び出し，全ての重複チェックを実行する関数
def check_ok(n,x):
if row_ok(n,x)==True and column_ok(n,x)==True and frame_ok(n,x)==True :
return True
else:
return False
# パズルを解くための手順を実行する関数
def solve(x):
if (x > MAX_BOARD-1):
print_board(board)
sys.exit()
else:
if(board[x] != 0):
solve(x+1)
else:
for n in range(1,10,1):
if(check_ok(n,x)==True):
board[x] = n
solve(x+1)
board[x] = 0
print_board(board)
print('start solve !')
solve(0)参考文献
- 目指せ！応用情報技術者，「午後問題対策 プログラミング」
更新履歴
- 2024年10月29日 新規作成
- 2025年1月19日 横 1 行の重複チェック，縦 1 列の重複チェック，枠内の重複チェックを行う関数の説明を追加
