白駿2580史都庫

白駿2580数独問題

https://www.acmicpc.net/problem/2580

Pythonコード

import sys

board = []
zero = []

row_sum = [0 for _ in range(9)]
column_sum = [0 for _ in range(9)]
rec_sum = [0 for _ in range(9)]

for i in range(9):  
  board.append(list(map(int, input().split())))

for i in range(9):
  for v in range(9):
    if board[i][v] == 0 :
      zero.append([i, v])

def check(index, r, c):
  number_set = {1, 2, 3, 4, 5, 6, 7, 8, 9}
  
  for i in range(9):
    if board[r][i] in number_set:
      number_set.remove(board[r][i])
    if board[i][c] in number_set:
      number_set.remove(board[i][c])

  for i in range(r - r%3 , r - r%3 +3):
    for v in range(c- c%3 , c- c%3 +3):
      if board[i][v] in number_set:
        number_set.remove(board[i][v])
  
  return number_set

def dfs(index, number):
  global reset

  if index != 0:
    prev_r, prev_c = zero[index - 1]
    board[prev_r][prev_c] = number
  
  if index == len(zero):
    for n in range(9):
      print(" ".join(map(str, board[n])))
    sys.exit()
  
  r, c = zero[index]

  for number in check(index, r, c):
    board[r][c] = number
    dfs(index+1, number)
    board[r][c] = 0


dfs(0, 0)

解題方法

スドック問題は実現が難しくないと考えている.条件通りに記入すればいいのですが、問題はタイムアウトだと思います.
この解題プログラムは、dfsを用いて複数の場合の解題であり、数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数~数

疑問点

最初にスタックを使用してdfsを記述します.しかし、タイムアウトの問題が発生し続け、関連資料を探す過程で再帰関数の代わりにスタックのwhile文を使用すると、時間が少なくなります.
dfsの実装方法を上のコードのように再帰関数で実装すると,時間内に通過できる.
ではstackと再帰関数の役割は何が違うのでしょうか.

反復文VS再帰関数

逆vs順方向

半木戸では、スタックに積み上げられた数字は逆です.たとえば、ノードが到達可能な数が1、2、3、4の場合、スタックは1、2、3、4の順にスタックされ、4つの数が先に外側に出てから重複文に戻ります.
しかし、再帰関数は、あるノードが到達できる数字が1,2,3,4であれば、次の再帰は1という数字から回転します.
しかし、この違いは数独問題に大きな影響を与えるのだろうか.
もちろん、特定の問題でどの数字を先に探索するかによって、解答時間は異なりますが、問題ごとに異なるので、あまり影響はないと思います.

斯多庫条件が適切でない場合(逆追跡)

dfsを迂回する場合、sdokuの条件が適切でないため、対応するノードを削除してから戻る必要がある場合があります.
重複文を使用してdfsを実装する場合は、親ノードに戻り、数独ボードの情報を返す必要があります.あるいは、いずれの場合も、スドクパンをコピーして渡すと解決されます.
dfsを再帰関数で実現すると、サブノードが順次再帰関数を完了するにつれて、数独板が自動的に戻り、関数を終了する.
この違いは数独問題を解く上で時間的な違いが生じる!!

に感銘を与える

もちろん,コードを見たときに確認しやすく理解しやすいのは,重複文を用いたdfsである.
しかし,backtrackingに基づいてアルゴリズムを解く(タイムアウトの可能性を考慮する必要がある場合!)
より効率的なコードを記述するには、dfsおよびbacktrackingを再帰関数で実現する必要があります.