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 で書き直す。