search_consistent_sets

Instructions

Implementation Reference

• src/server.py:356-400 (handler)

  Main handler for the 'search_consistent_sets' tool. Validates inputs, prepares target clues and candidates, and calls the _solve helper to find consistent assignments via backtracking.

  async def search_consistent_sets(target_clue_ids: list[str] | None = None) -> list[dict[str, str]]:
      """登録済み候補から交差条件を満たす割当てを探索する。
  
      Args:
          target_clue_ids (list[str] | None): 探索対象とするカギ ID のリスト。`None` または
              空リストを渡した場合は、候補が登録済みのすべてのカギを対象とする。
  
      Returns:
          list[dict[str, str]]: 整合性が取れた解集合のリスト。各要素は `clue_id` をキー、
              採用した候補語を値とする辞書。複数の最大解が存在する場合は重複しない
              形で列挙し、整合するカギが 1 件も無い場合は空リストを返す。
  
      Raises:
          RuntimeError: `setup` が未実行、または候補語が一件も登録されていない場合。
          KeyError: `target_clue_ids` に含まれる ID がカギ定義または候補登録に存在しない
              場合。
      """
  
      _ensure_setup()
  
      if not state.candidates:
          raise RuntimeError("register_candidates を先に呼び出して候補ワードを登録してください。")
  
      if target_clue_ids is None:
          target_ids = list(state.candidates.keys())
      else:
          target_ids = [cid.strip() for cid in target_clue_ids if cid and cid.strip()]
          if not target_ids:
              target_ids = list(state.candidates.keys())
  
      unique_ids = list(dict.fromkeys(target_ids))
  
      target_info: list[tuple[str, tuple[tuple[int, int], ...], list[str]]] = []
      for clue_id in unique_ids:
          if clue_id not in state.clues:
              raise KeyError(f"clue_id={clue_id} のカギが存在しません。")
          if clue_id not in state.candidates:
              raise KeyError(f"clue_id={clue_id} の候補が登録されていません。")
  
          clue = state.clues[clue_id]
          candidates = state.candidates[clue_id]
          target_info.append((clue_id, clue.positions, candidates))
  
      return _solve(target_info)

• src/server.py:291-352 (helper)

  Helper function implementing the backtracking algorithm to find all maximum consistent sets of word assignments that satisfy crossword intersection constraints.

  def _solve(target_info: list[tuple[str, tuple[tuple[int, int], ...], list[str]]]) -> list[dict[str, str]]:
      "候補語を総当たりして交差一致を判定し、最大数のカギが一致する割当てを収集する"
      cell_letters: dict[tuple[int, int], str] = {}
      assignments: dict[str, str] = {}
      best_assignments: list[dict[str, str]] = []
      best_size = 0
      signatures: set[tuple[tuple[str, str], ...]] = set()
  
      def update_best() -> None:
          nonlocal best_size
          current_size = len(assignments)
          signature = tuple(sorted(assignments.items()))
          if current_size > best_size:
              best_size = current_size
              best_assignments.clear()
              signatures.clear()
          if current_size == best_size and signature not in signatures:
              best_assignments.append(dict(assignments))
              signatures.add(signature)
  
      def backtrack(index: int) -> None:
          if index == len(target_info):
              update_best()
              return
  
          clue_id, positions, candidates = target_info[index]
  
          for word in candidates:
              conflict = False
              placed: list[tuple[int, int]] = []
  
              for (row, col), char in zip(positions, word):
                  existing = cell_letters.get((row, col))
                  if existing is not None and existing != char:
                      conflict = True
                      break
  
              if conflict:
                  continue
  
              assignments[clue_id] = word
  
              for (row, col), char in zip(positions, word):
                  if (row, col) not in cell_letters:
                      cell_letters[(row, col)] = char
                      placed.append((row, col))
  
              backtrack(index + 1)
  
              for cell in placed:
                  del cell_letters[cell]
  
              del assignments[clue_id]
  
          backtrack(index + 1)
  
      backtrack(0)
  
      if best_size == 0:
          return []
  
      return best_assignments