問題の説明
「ラテン方陣 (Latin square)」は「数独」の枠の条件を無くした方陣です。ラテン方陣の定義を 参考文献 1 より引用します。『ラテン方陣を一般的にいうなら、n 行 n 列の正方形の枡に n 種類の記号を n 個ずつ配列して、各行各列に記号の重複のないものを n 次のラテン方陣というのです。』このラテン方陣をパズルに応用したものが数独というわけです。
簡単な例を示しましょう。3 次のラテン方陣は次に示す 12 通りになります。
1 2 3 1 2 3 1 3 2 1 3 2 2 1 3 2 1 3
2 3 1 3 1 2 2 1 3 3 2 1 1 3 2 3 2 1
3 1 2 2 3 1 3 2 1 2 1 3 3 2 1 1 3 2
標準形
2 3 1 2 3 1 3 1 2 3 1 2 3 2 1 3 2 1
1 2 3 3 1 2 1 2 3 2 3 1 1 3 2 2 1 3
3 1 2 1 2 3 2 3 1 1 2 3 2 1 3 1 3 2
図 : 3 次のラテン方陣
この中で、最初の行と列の要素を昇順に並べたものを「標準形」といいます。3 次のラテン方陣の場合、標準形は 1 種類しかありません。ラテン方陣は任意の行を交換する、または任意の列を交換してもラテン方陣になります。3 次のラテン方陣の場合、標準形から行または列を交換することで、残りの 11 種類のラテン方陣を生成することができます。
それでは問題です。
- 4, 5, 6, 7 次の標準形ラテン方陣の総数を求めてください
- 下図に示す 6 行 6 列盤の数独において、解となる盤面の総数を求めてください
- 9 行 9 列盤の数独を解くプログラムを作成してください
●解答１
最近のパソコンは高性能なので、次数が大きくなければ単純な深さ優先探索で解を求めることができます。使用するプログラミング言語は Python3 (PyPy3) です。
リスト : 標準形ラテン方陣の総数を求める
# 盤面の初期化
def init_board(size):
b = [[0] * size for _ in range(size)]
for i in range(size):
b[0][i] = b[i][0] = i + 1
return b
# 縦横で同じ数字が無いことを確認する
def is_safe(board, y, x, n):
for i in range(len(board)):
if board[y][i] == n or board[i][x] == n: return False
return True
# 深さ優先探索
def dfs(fn, b, y, x):
if y == len(b):
fn(b)
elif x == len(b):
dfs(fn, b, y + 1, 1)
else:
for n in range(1, len(b) + 1):
if not is_safe(b, y, x, n): continue
b[y][x] = n
dfs(fn, b, y, x + 1)
b[y][x] = 0
# ラテン方陣
def latin_solver(size):
cnt = 0
def counter(b):
nonlocal cnt
cnt += 1
b = init_board(size)
dfs(counter, b, 1, 1)
return cnt
プログラムは簡単なので説明は割愛させていただきます。実行結果は次のようになりました。
>>>> latin_solver(4) 4 >>>> latin_solver(5) 56 >>>> latin_solver(6) 9408 >>>> import time >>>> s = time.time(); latin_solver(7); time.time() - s 16942080 252.56771516799927 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
I4 = 4 I5 = 56 I6 = 9408 I7 = 16942080
7 次ラテン方陣の実行時間は PyPy3 で 4 分ちょっとかかりました。Python では時間がかかりますね。高次の標準形ラテン方陣の総数は、簡単に求めることができない非常にハードな問題だと思います。興味のある方は他のプログラミング言語で試してみてください。
●解答２
解の総数を求める場合、単純な方法では 6 * 6 の数独でも大変です。そこでラテン方陣のような標準形を考えることにします。数独の場合、数字 N と数字 M を交換しても数独の条件を満たすので、数字の配置を下図のように限定することにします。
1 2 3 4 5 6 4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 図 : 数字の配置
一番上の行で数字を交換することで 6! = 720 通り、右上のグループの残り 3 つの数字を交換することで 6 通りの解が生成されます。したがって、上図の解の総数を I とすると、解の総数は I * 720 * 6 になります。
プログラムは次のようになります。
リスト : 数独 (6 行 6 列盤) の解の総数を求める
# 盤面の初期化
def init_board6():
board = [[0] * 6 for _ in range(6)]
for i in range(6):
board[0][i] = i + 1
for i in range(3):
board[1][i] = i + 4
return board
# 縦横枠で安全確認
def is_safe6(board, y, x, n):
for i in range(len(board)):
if board[y][i] == n or board[i][x] == n: return False
y1 = (y // 2) * 2
x1 = (x // 3) * 3
for i in (y1, y1 + 1):
for j in (x1, x1 + 1, x1 + 2):
if board[i][j] == n: return False
return True
# 深さ優先探索
def dfs6(fn, b, y, x):
if y == len(b):
fn(b)
elif x == len(b):
dfs6(fn, b, y + 1, 0)
else:
for n in range(1, len(b) + 1):
if not is_safe6(b, y, x, n): continue
b[y][x] = n
dfs6(fn, b, y, x + 1)
b[y][x] = 0
def numplace6():
cnt = 0
def counter(b):
nonlocal cnt
cnt += 1
b = init_board6()
dfs6(counter, b, 1, 3)
return cnt
難しいところはないと思いますので、説明は割愛させていただきます。実行結果は次のようになりました。
>>>> s = time.time(); numplace6(); time.time() - s 6528 0.20812034606933594
解の総数は 6528 * 720 * 6 = 28,200,960 通りになります。
●解答３
最近のパソコンは高性能なので、9 行 9 列盤の数独ならば単純な深さ優先探索で解くことができます。プログラムは次のようになります。
リスト : 数独の解法
# 縦横枠で安全確認
def is_safe9(board, y, x, n):
for i in range(len(board)):
if board[y][i] == n or board[i][x] == n: return False
y1 = (y // 3) * 3
x1 = (x // 3) * 3
for i in (y1, y1 + 1, y1 + 2):
for j in (x1, x1 + 1, x1 + 2):
if board[i][j] == n: return False
return True
# 深さ優先探索
def dfs9(fn, b, y, x):
if y == len(b):
fn(b)
elif x == len(b):
dfs9(fn, b, y + 1, 0)
elif b[y][x] != 0:
dfs9(fn, b, y, x + 1)
else:
for n in range(1, len(b) + 1):
if not is_safe9(b, y, x, n): continue
b[y][x] = n
dfs9(fn, b, y, x + 1)
b[y][x] = 0
def numplace9(qs):
print_board(qs)
print('----------------')
dfs9(print_board, qs, 0, 0)
難しいところはないと思いますので、説明は割愛させていただきます。それでは、実際に数独を解いてみましょう。
リスト : 問題 (出典 : 数独 - Wikipedia の例)
q00 = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
>>>> s = time.time(); numplace9(q00); time.time() - s 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 ---------------- 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 0.10623049736022949
盤面が 9 * 9 の場合、Python でも高速に解くことができました。ところで、バックトラックしないで解く方法もあります。興味のある方は拙作のページ Scheme Programming パズルの解法 [4] [5] [6] [7] をお読みください。
●参考文献, URL
- 大村平, 『数理パズルのはなし』, 日科技連出版社, 1998
●プログラムリスト
#
# latin.py : ラテン方陣
#
# Copyright (C) 2022 Makoto Hiroi
#
# 盤面の初期化
def init_board(size):
b = [[0] * size for _ in range(size)]
for i in range(size):
b[0][i] = b[i][0] = i + 1
return b
# 縦横で同じ数字が無いことを確認する
def is_safe(board, y, x, n):
for i in range(len(board)):
if board[y][i] == n or board[i][x] == n: return False
return True
# 深さ優先探索
def dfs(fn, b, y, x):
if y == len(b):
fn(b)
elif x == len(b):
dfs(fn, b, y + 1, 1)
else:
for n in range(1, len(b) + 1):
if not is_safe(b, y, x, n): continue
b[y][x] = n
dfs(fn, b, y, x + 1)
b[y][x] = 0
# 盤面の表示
def print_board(board):
for xs in board:
for x in xs:
print(x, end=' ')
print()
print()
# ラテン方陣の個数
def latin_solver(size):
cnt = 0
def counter(b):
nonlocal cnt
cnt += 1
b = init_board(size)
dfs(counter, b, 1, 1)
return cnt
#
# ナンバープレース
#
# 6 行 6 列盤の総数を求める
# 盤面の初期化
def init_board6():
board = [[0] * 6 for _ in range(6)]
for i in range(6):
board[0][i] = i + 1
for i in range(3):
board[1][i] = i + 4
return board
# 縦横枠で安全確認
def is_safe6(board, y, x, n):
for i in range(len(board)):
if board[y][i] == n or board[i][x] == n: return False
y1 = (y // 2) * 2
x1 = (x // 3) * 3
for i in (y1, y1 + 1):
for j in (x1, x1 + 1, x1 + 2):
if board[i][j] == n: return False
return True
# 深さ優先探索
def dfs6(fn, b, y, x):
if y == len(b):
fn(b)
elif x == len(b):
dfs6(fn, b, y + 1, 0)
else:
for n in range(1, len(b) + 1):
if not is_safe6(b, y, x, n): continue
b[y][x] = n
dfs6(fn, b, y, x + 1)
b[y][x] = 0
def numplace6():
cnt = 0
def counter(b):
nonlocal cnt
cnt += 1
b = init_board6()
dfs6(counter, b, 1, 3)
return cnt
#
# 9 行 9 列盤の解法
#
# 縦横枠で安全確認
def is_safe9(board, y, x, n):
for i in range(len(board)):
if board[y][i] == n or board[i][x] == n: return False
y1 = (y // 3) * 3
x1 = (x // 3) * 3
for i in (y1, y1 + 1, y1 + 2):
for j in (x1, x1 + 1, x1 + 2):
if board[i][j] == n: return False
return True
# 深さ優先探索
def dfs9(fn, b, y, x):
if y == len(b):
fn(b)
elif x == len(b):
dfs9(fn, b, y + 1, 0)
elif b[y][x] != 0:
dfs9(fn, b, y, x + 1)
else:
for n in range(1, len(b) + 1):
if not is_safe9(b, y, x, n): continue
b[y][x] = n
dfs9(fn, b, y, x + 1)
b[y][x] = 0
def numplace9(qs):
print_board(qs)
print('----------------')
dfs9(print_board, qs, 0, 0)
# 問題 (出典: 数独 - Wikipedia の問題例)
q00 = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]