Sudoku solver
なぜか突然思い立って、総当たり的なことをしない方向の数独のソルバを書き始めた。
問題の持ち方
sudoku = """
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
"""
データ構造と基本的な解き方
9 x 9 の配列に 1-9 の数字が入った set を入れておく。 ソルバを実行して、set 内に存在しえない数値を順次消していく。
def transform(sudoku):
sudoku = re.sub(r'\D','',sudoku)
print(sudoku)
board = []
for ri in range(0,9):
r = []
for ci in range(0,9):
col = int(sudoku[ri*9+ci])
if col == 0:
r.append(set([ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]))
else:
r.append(set([ col ]))
board.append(r)
return board
盤面の状態を判定する。単純に全マス全 set を足すだけ。結果が405(45x9)になった時点であがり。
def calc_digest(board):
ret = 0
for row in board:
for col in row:
ret += sum(col)
return ret
ユーティリティ的なもの
盤面印刷や、行/列/3x3の矩形それぞれの座標でと出した9マスへのアクセサ
def coord_to_row(coord):
return coord[0]
def coord_to_col(coord):
return coord[1]
def coord_to_sqi(coord):
return (coord[0]//3) * 3 + (coord[1]//3)
def row_to_coord(ri):
ret = []
for i in range(0,9):
ret.append((ri,i))
return ret
def col_to_coord(ci):
ret = []
for i in range(0,9):
ret.append((i,ci))
return ret
def sqi_to_coord(sqi):
rs = (sqi//3)*3
cs = (sqi%3)*3
ret = []
for ri in range(rs, rs+3):
for ci in range(cs, cs+3):
ret.append((ri,ci))
return ret
def print_board(board):
for ri, row in enumerate(board):
for nr in [1,4,7]:
for ci, col in enumerate(row):
for n in range(nr, nr+3):
if n in col:
print(n, end="")
else:
print(" ", end="")
if (ci + 1) % 3:
print(" ", end="")
else:
print("|", end="")
print("\n", end="")
if (ri + 1) % 3:
print("\n", end="")
else:
print("--- --- --- --- --- --- --- --- ---")
独立数字用ソルバ
単独の数字があった際、属する行/列/3x3矩形に同じ数字があったら消す。 o が確定できていれば、x の位置に o が入ることはない。
xxx| |
xox|xxx|xxx
xxx| |
---+---+---
x | |
x | |
x | |
---+---+---
x | |
x | |
x | |
def solv1(board):
ret = False
digest = calc_digest(board)
print_board(board)
print(f"solv1: digest {digest}")
while True:
for ri, row in enumerate(board):
for ci, col in enumerate(row):
if len(col) == 1:
search = row_to_coord(ri) + col_to_coord(ci) + sqi_to_coord(coord_to_sqi((ri, ci)))
for coord in search:
if board[coord[0]][coord[1]] != col:
board[coord[0]][coord[1]] -= col
digest_orig = digest
digest = calc_digest(board)
print_board(board)
print(f"solv1: digest {digest} digest_orig {digest_orig}")
if digest == digest_orig:
break
ret = True
return ret
複数数字用ソルバ
属する行/列/3x3矩形内で n個の数字の組み合わせがnマスにしかない場合残マスに同じ数字は入れないはず。 aとbはどちらがどちらか確定できていない場合でも、すくなくとも x にはaもbも入れないパターン
xxx| |
xab|xxx|xxx
xxx| |
---+---+---
| |
| |
| |
---+---+---
| |
| |
| |
def solv_n(board, n):
def solv_n_one_chunk(chunk):
remain = set(range(1,10))
for coord in chunk:
if len(board[coord[0]][coord[1]]) == 1:
remain -= board[coord[0]][coord[1]]
print(remain, end=" ")
for tpl in itertools.combinations(remain,n):
print(tpl, end=" ")
found = []
not_found = []
for coord in chunk:
if set(tpl) >= board[coord[0]][coord[1]]:
found.append(coord)
else:
not_found.append(coord)
if(len(found) == n):
print(f"{found}")
for coord in not_found:
board[coord[0]][coord[1]] -= set(tpl)
print("\n", end="")
ret = False
digest = calc_digest(board)
print_board(board)
print(f"solv_n: n {n} digest {digest}")
for i in range(0,9):
solv_n_one_chunk(row_to_coord(i))
solv_n_one_chunk(col_to_coord(i))
solv_n_one_chunk(sqi_to_coord(i))
digest_orig = digest
digest = calc_digest(board)
print_board(board)
print(f"solv_n: n {n} digest {digest} digest_orig {digest_orig}")
if digest != digest_orig:
ret = True
print(f"solv_n: n {n} {ret}")
return ret
3x3矩形用ソルバ
3x3矩形内での座標は確定できないが、行/列のいずれかは確定できるパターン パターン1: 左上の矩形内でoの正確な列はわからないが、少なくとも x に o は入らない。
| |
ooo|xxx|xxx
| |
---+---+---
| |
| |
| |
---+---+---
| |
| |
| |
パターン2: o がoの座標にしか登場なければ、同座標にほかの数字がどれだけ残っていようが o
| |
o | |
| |
---+---+---
| |
| |
| |
---+---+---
| |
| |
| |
def solv_sqi_line(board):
def solv_sqi_line_one_chunk(sqi):
chunk = sqi_to_coord(sqi)
remain = set(range(1,10))
for coord in chunk:
if len(board[coord[0]][coord[1]]) == 1:
remain -= board[coord[0]][coord[1]]
print(remain, end=" ")
for num in remain:
found = []
for coord in chunk:
if num in board[coord[0]][coord[1]]:
found.append(coord)
if(len(found) > 0 and len(found) < 4):
print(f"{found}")
ri = 0
ci = 0
print(len(found))
if(len(found) == 1):
coord = found[0]
board[coord[0]][coord[1]] = set([num])
elif(found[0][0] == found[1][0] and (len(found) == 2 or found[2][0] == found[0][0])):
search = row_to_coord(found[0][0])
for coord in search:
if coord_to_sqi(coord) != sqi:
board[coord[0]][coord[1]] -= set([num])
elif(found[0][1] == found[1][1] and (len(found) == 2 or found[2][1] == found[0][1])):
search = col_to_coord(found[0][1])
for coord in search:
if coord_to_sqi(coord) != sqi:
board[coord[0]][coord[1]] -= set([num])
print("\n", end="")
ret = False
digest = calc_digest(board)
print_board(board)
print(f"solv_sqi_line: digest {digest}")
for i in range(0,9):
solv_sqi_line_one_chunk(i)
digest_orig = digest
digest = calc_digest(board)
print_board(board)
print(f"solv_sqi_line: digest {digest} digest_orig {digest_orig}")
if digest != digest_orig:
ret = True
return ret
10/13 bugfix
たかだかこれだけで、無実の行をバスバスけしてしまうことがある。やはりアクセサの書き換えが最優先か。
メイン
盤面に変化があった際には solv1 から再開する。 (最悪パターンでも8まででいいはずだし、8の場合は残る1マスの数字は自明で決まるはずだが、一応)solv_n の 9 番目まで実行して盤面に変化がなければ、ギブアップ。
board = transform(sudoku)
while calc_digest(board) != 405:
if solv1(board):
continue
if solv_sqi_line(board):
continue
for n in range(2,10):
if solv_n(board, n):
break
if n == 9:
print("give up")
print_board(board)
exit(1)
やること
- アクセサ類の整理
- ソルバのリファクタ
- 3x3矩形用ソルバのパターン2はsolv1でやっとくべき
- solv_n と solv1 は共用できると思うんだが。。。 solv1 は solv_n(n=1) で実装できそうな気がするんだが、、、集合演算の方向が逆なのでよくわからない
- まだないパターンのソルバ実装
o が下記のうち任意の2つ(矩形左上に一つ、矩形右上に一つ)だとすると、xの場所にoがくることはない。
| |
ooo|xxx|ooo
ooo|xxx|ooo
---+---+---
| |
| |
| |
---+---+---
| |
| |
| |
- kotlin で書き直す。