論文の概要: Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty

• arxiv url: http://arxiv.org/abs/2608.23300v1
• Date: Mon, 24 Aug 2026 14:24:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-25 13:29:44.133214
• Title: Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty
• Title（参考訳）: SATソルバー距離を人体知覚非図形難易度予測因子として評価する
• Abstract要約: 我々は,数列と列の数値的な手がかりが一意の解格子を決定する,数独に類似した論理パズルであるNonogramsの仮定を評価する。 被験者の難易度も行動信号もSATソルバ指標と有意な相関は認められなかった。 本プロセスでは, 複雑な伝播に対する人間の嗜好を示す, 個別かつ反復的な解決戦略を明らかにする。
• 参考スコア（独自算出の注目度）: 0.9332987715848716
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithmic solver effort is often assumed to align with perceived puzzle difficulty, but this assumption is rarely tested against human solving data. We evaluate this assumption for Nonograms, a popular logic puzzle similar to Sudoku in which numeric clues along each row and column determine a unique solution grid. We formulate Nonograms as a constraint satisfaction problem and solve them using existing SAT solvers. We then conduct a user study in which we collect data on both participant interactions and reported difficulty. We find that neither participants' reported difficulty nor their behavioural signals correlate meaningfully with SAT solver metrics; however, we find evidence that expertise moderates the relationship between solver metrics and reported difficulty. In this process, we uncover distinct, recurring solving strategies that indicate human preference for complex propagation, diverging from solver-measured complexity.
• Abstract（参考訳）: アルゴリズムによる解法は、しばしば認識されるパズルの難しさと一致すると仮定されるが、この仮定は人間の解法データに対してテストされることは滅多にない。 この仮定は、数列と列の数値的な手がかりが一意の解格子を決定する、数独に類似した一般的な論理パズルであるNonogramsについて評価する。 制約満足度問題としてNonogramを定式化し、既存のSATソルバを用いて解決する。 次に、ユーザ調査を行い、双方のインタラクションに関するデータを収集し、難易度を報告します。 被験者の難易度も行動信号もSATソルバ指標と有意な相関は認められなかったが,専門知識がソルバ指標と難易度の関係を緩和する証拠が得られた。 本プロセスでは, 複雑な伝播に対するヒトの嗜好を示す解法を, 解法によって測定された複雑性から逸脱する, 個別かつ反復的な解法を探索する。

関連論文リスト

• 4OPS: Structural Difficulty Modeling in Integer Arithmetic Puzzles [0.0]
  算術パズルゲームは、数学的推論タスクの難しさを研究するための制御された設定を提供する。 我々は、到達可能な目標を列挙し、最小操作の証人を抽出し、大規模ラベリングを可能にする、正確な動的プログラミング解法を開発する。 難易度は、正確な目撃者から導かれる、解釈可能な構造的属性の小さなセットによって完全に決定されることを示す。
  論文  参考訳（メタデータ） (2026-03-26T12:01:39Z)
• Learning to Pose Problems: Reasoning-Driven and Solver-Adaptive Data Synthesis for Large Reasoning Models [54.29243291958429]
  本研究は, 生成前に問題方向を明示的に計画する問題生成装置の開発である。 我々は,合成問題に対する解法者のフィードバックを報奨信号として扱い,生成元が難易度を調整できるようにする。 本手法は平均2.5%の改善を実現し,言語モデルと視覚言語モデルの両方に一般化する。
  論文  参考訳（メタデータ） (2025-11-13T03:08:51Z)
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints [0.0]
  NP完全満足度問題 3-SAT の局所探索を導入,ベンチマークする。 私たちの建設は、WalkSATのような確立した従来のアプローチが、地元のミニマで立ち往生する傾向にあるという決定的な観察に基づいています。 我々は,N=15000までの様々な問題サイズを持つ3SATインスタンスをランダムに生成したサンプルを用いて,アルゴリズムを解析・ベンチマークする。
  論文  参考訳（メタデータ） (2025-06-18T18:00:01Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。 我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
  論文  参考訳（メタデータ） (2025-05-13T01:24:09Z)
• Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
  グラフニューラルネットワークを用いてオーラクルを訓練し、2つのSLSソルバ上で、様々な難易度を持つランダムSATインスタンス上でそれらを評価する。 GNNベースのオラクルへのアクセスは,両者のパフォーマンスを著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-09-20T16:27:52Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。 ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
  論文  参考訳（メタデータ） (2022-03-02T05:14:12Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Total Deep Variation: A Stable Regularizer for Inverse Problems [71.90933869570914]
  本稿では,データ駆動型汎用全深度変動正規化器について紹介する。 コアでは、畳み込みニューラルネットワークが複数のスケールや連続したブロックで局所的な特徴を抽出する。 我々は多数の画像処理タスクに対して最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-15T21:54:15Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。