エクセル関数応用
「Python in Excel」数独（ナンプレ）解法プログラムの移植と最適化

def _to_grid(data):
    """Excelの入力データを 9x9 の int 配列（数値以外は0）に整形するヘルパー関数"""
    rows_iter = data.itertuples(index=False) if hasattr(data, 'itertuples') else data
    grid = []
    for row in rows_iter:
        grid_row = []
        for v in row:
            try:
                grid_row.append(int(float(v)))
            except (ValueError, TypeError):
                grid_row.append(0)
        grid.append(grid_row)
    return grid


def solve_sudoku_set(data):
    """
    Python in Excel 用 数独解法関数（set版）
    """
    # 1. 入力データの成形
    grid = _to_grid(data)
    if len(grid) != 9 or any(len(r) != 9 for r in grid):
        return "エラー: 9x9の範囲を指定してください"

    # 2. 状態管理用 set（集合）の初期化
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    blocks = [set() for _ in range(9)]

    for r in range(9):
        for c in range(9):
            val = grid[r][c]
            if 1 <= val <= 9:
                rows[r].add(val)
                cols[c].add(val)
                blocks[(r // 3) * 3 + (c // 3)].add(val)
            else:
                grid[r][c] = 0

    # 3. 再帰的バックトラック探索（MRVヒューリスティック）
    def backtrack():
        min_count = 10      # 最小候補数の初期値
        best_pos = None     # 次に試行するセル位置 (r, c)
        min_candidates = [] # 該当セルの候補数字リスト

        # 全空きマスをチェックし、最も候補が少ないセルを抽出（MRV）
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    b_idx = (r // 3) * 3 + (c // 3)

                    # 行・列・ブロックの使用済み数字を和集合で合算
                    used = rows[r] | cols[c] | blocks[b_idx]

                    # 1～9 のうち使われていない数字を抽出
                    cands = [num for num in range(1, 10) if num not in used]

                    cnt = len(cands)
                    if cnt < min_count:
                        min_count = cnt
                        min_candidates = cands
                        best_pos = (r, c)

                        # 確定セル(1個)または破綻(0個)が見つかれば直ちに走査を終了
                        if min_count <= 1:
                            break
            if min_count <= 1:
                break

        # 解答完成
        if best_pos is None:
            return True

        # 行き止まり（破綻）
        if min_count == 0:
            return False

        r, c = best_pos
        b_idx = (r // 3) * 3 + (c // 3)

        # 候補数字を順番に試行
        for num in min_candidates:
            grid[r][c] = num
            rows[r].add(num)
            cols[c].add(num)
            blocks[b_idx].add(num)

            if backtrack():
                return True

            # 元に戻す（バックトラック）
            rows[r].remove(num)
            cols[c].remove(num)
            blocks[b_idx].remove(num)
            grid[r][c] = 0

        return False

    backtrack()
    return grid

solve_sudoku_set(xl("A1:I9"))

def _to_grid(data):
    """Excelの入力データを 9x9 の int 配列（数値以外は0）に整形するヘルパー関数"""
    rows_iter = data.itertuples(index=False) if hasattr(data, 'itertuples') else data
    grid = []
    for row in rows_iter:
        grid_row = []
        for v in row:
            try:
                grid_row.append(int(float(v)))
            except (ValueError, TypeError):
                grid_row.append(0)
        grid.append(grid_row)
    return grid


def solve_sudoku_bitmask(data):
    """
    Python in Excel 用 数独解法関数（ビットマスク最適化版）
    """
    # ------------------------------------------------------------------
    # 1. 入力データの成形
    # ------------------------------------------------------------------
    grid = _to_grid(data)
    if len(grid) != 9 or any(len(r) != 9 for r in grid):
        return "エラー: 9x9の範囲を指定してください"

    # ------------------------------------------------------------------
    # 2. ビットフラグの初期化（1～9 の数字を 9ビットで管理）
    # ------------------------------------------------------------------
    FULL_MASK = 0b111111111  # 1～9 の全フラグが立った状態 (511)
    rows = [0] * 9
    cols = [0] * 9
    blocks = [0] * 9

    for r in range(9):
        for c in range(9):
            val = grid[r][c]
            if 1 <= val <= 9:
                bit = 1 << (val - 1)
                rows[r] |= bit
                cols[c] |= bit
                blocks[(r // 3) * 3 + (c // 3)] |= bit
            else:
                grid[r][c] = 0

    # ------------------------------------------------------------------
    # 3. ビット演算によるバックトラック探索
    # ------------------------------------------------------------------
    def backtrack():
        min_count = 10
        best_pos = None
        best_allowed_mask = 0

        # 全空きマスを走査し、配置可能なビット（候補数）が最小のマスを検索
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    b_idx = (r // 3) * 3 + (c // 3)

                    # 配置可能なビットのみを抽出
                    allowed = FULL_MASK & ~(rows[r] | cols[c] | blocks[b_idx])
                    cnt = allowed.bit_count()  # 高速ビットカウント

                    if cnt < min_count:
                        min_count = cnt
                        best_pos = (r, c)
                        best_allowed_mask = allowed
                        if min_count <= 1:
                            break
            if min_count <= 1:
                break

        if best_pos is None:
            return True

        if min_count == 0:
            return False

        r, c = best_pos
        b_idx = (r // 3) * 3 + (c // 3)

        # 許可されたビットから最下位ビット（LSB）を順に取り出して試行
        mask = best_allowed_mask
        while mask > 0:
            lsb = mask & -mask       # 最低位の立っているビットを取得
            num = lsb.bit_length()  # ビット位置から数値 (1～9) を復元

            # 仮置き
            grid[r][c] = num
            rows[r] |= lsb
            cols[c] |= lsb
            blocks[b_idx] |= lsb

            if backtrack():
                return True

            # 元に戻す
            rows[r] ^= lsb
            cols[c] ^= lsb
            blocks[b_idx] ^= lsb
            grid[r][c] = 0

            # 試行済みビットを消去して次の候補へ
            mask &= mask - 1

        return False

    backtrack()
    return grid

solve_sudoku_bitmask(xl("A1:I9"))

import time

# ------------------------------------------------------------------
# 1. 入力データの整形用ヘルパー関数（DRY原則の適用）
# ------------------------------------------------------------------
def _to_grid(data):
    """Excelの入力データを 9x9 の int 配列（数値以外は0）に整形する"""
    rows_iter = data.itertuples(index=False) if hasattr(data, 'itertuples') else data
    grid = []
    for row in rows_iter:
        grid_row = []
        for v in row:
            try:
                grid_row.append(int(float(v)))
            except (ValueError, TypeError):
                grid_row.append(0)
        grid.append(grid_row)
    return grid


# ------------------------------------------------------------------
# 2. set（集合）版 解法コア関数
# ------------------------------------------------------------------
def solve_set(src_grid):
    grid = [r[:] for r in src_grid]  # ディープコピー
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    blocks = [set() for _ in range(9)]

    for r in range(9):
        for c in range(9):
            val = grid[r][c]
            if 1 <= val <= 9:
                rows[r].add(val)
                cols[c].add(val)
                blocks[(r // 3) * 3 + (c // 3)].add(val)

    def backtrack():
        min_count = 10
        best_pos = None
        min_candidates = []

        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    b_idx = (r // 3) * 3 + (c // 3)
                    used = rows[r] | cols[c] | blocks[b_idx]
                    cands = [num for num in range(1, 10) if num not in used]
                    cnt = len(cands)
                    if cnt < min_count:
                        min_count = cnt
                        min_candidates = cands
                        best_pos = (r, c)
                        if min_count <= 1:
                            break
            if min_count <= 1:
                break

        if best_pos is None:
            return True
        if min_count == 0:
            return False

        r, c = best_pos
        b_idx = (r // 3) * 3 + (c // 3)

        for num in min_candidates:
            grid[r][c] = num
            rows[r].add(num)
            cols[c].add(num)
            blocks[b_idx].add(num)

            if backtrack():
                return True

            rows[r].remove(num)
            cols[c].remove(num)
            blocks[b_idx].remove(num)
            grid[r][c] = 0

        return False

    backtrack()
    return grid


# ------------------------------------------------------------------
# 3. ビットマスク版 解法コア関数
# ------------------------------------------------------------------
def solve_bitmask(src_grid):
    grid = [r[:] for r in src_grid]  # ディープコピー
    FULL_MASK = 0b111111111
    rows = [0] * 9
    cols = [0] * 9
    blocks = [0] * 9

    for r in range(9):
        for c in range(9):
            val = grid[r][c]
            if 1 <= val <= 9:
                bit = 1 << (val - 1)
                rows[r] |= bit
                cols[c] |= bit
                blocks[(r // 3) * 3 + (c // 3)] |= bit

    def backtrack():
        min_count = 10
        best_pos = None
        best_allowed_mask = 0

        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    b_idx = (r // 3) * 3 + (c // 3)
                    allowed = FULL_MASK & ~(rows[r] | cols[c] | blocks[b_idx])
                    cnt = allowed.bit_count()

                    if cnt < min_count:
                        min_count = cnt
                        best_pos = (r, c)
                        best_allowed_mask = allowed
                        if min_count <= 1:
                            break
            if min_count <= 1:
                break

        if best_pos is None:
            return True
        if min_count == 0:
            return False

        r, c = best_pos
        b_idx = (r // 3) * 3 + (c // 3)

        mask = best_allowed_mask
        while mask > 0:
            lsb = mask & -mask
            num = lsb.bit_length()

            grid[r][c] = num
            rows[r] |= lsb
            cols[c] |= lsb
            blocks[b_idx] |= lsb

            if backtrack():
                return True

            rows[r] ^= lsb
            cols[c] ^= lsb
            blocks[b_idx] ^= lsb
            grid[r][c] = 0

            mask &= mask - 1

        return False

    backtrack()
    return grid


# ------------------------------------------------------------------
# 4. データ取得とベンチマーク実行（1,000回連続）
# ------------------------------------------------------------------
base_grid = _to_grid(xl("A1:I9"))
N = 1000

# set 版の計測
t0 = time.perf_counter()
for _ in range(N):
    solve_set(base_grid)
t_set = time.perf_counter() - t0

# ビットマスク版の計測
t0 = time.perf_counter()
for _ in range(N):
    solve_bitmask(base_grid)
t_bitmask = time.perf_counter() - t0

# ------------------------------------------------------------------
# 5. 結果フォーマット出力
# ------------------------------------------------------------------
f"""【数独解法ベンチマーク結果（{N:,}回実行）】
----------------------------------------
■ set（集合）版
  ・合計時間 : {t_set:.4f} 秒
  ・平均時間 : {(t_set / N) * 1000:.4f} ms / 回

■ ビットマスク版
  ・合計時間 : {t_bitmask:.4f} 秒
  ・平均時間 : {(t_bitmask / N) * 1000:.4f} ms / 回

■ 速度比
  ・ビットマスク版は set 版の約 {t_set / t_bitmask:.2f} 倍高速
----------------------------------------"""

【数独解法ベンチマーク結果（1,000回実行）】
----------------------------------------
■ set（集合）版
  ・合計時間 : 10.8209 秒
  ・平均時間 : 10.8209 ms / 回

■ ビットマスク版
  ・合計時間 : 3.4319 秒
  ・平均時間 : 3.4319 ms / 回

■ 速度比
  ・ビットマスク版は set 版の約 3.15 倍高速
----------------------------------------

【数独解法ベンチマーク結果（1,000回実行）】
----------------------------------------
■ set（集合）版
  ・合計時間 : 10.8152 秒
  ・平均時間 : 10.8152 ms / 回

■ ビットマスク版
  ・合計時間 : 3.3554 秒
  ・平均時間 : 3.3554 ms / 回

■ 速度比
  ・ビットマスク版は set 版の約 3.22 倍高速
----------------------------------------