論文の概要: Project Patti: Why can You Solve Diabolical Puzzles on one Sudoku Website but not Easy Puzzles on another Sudoku Website?
- arxiv url: http://arxiv.org/abs/2507.21137v1
- Date: Tue, 22 Jul 2025 22:32:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-30 17:08:54.981746
- Title: Project Patti: Why can You Solve Diabolical Puzzles on one Sudoku Website but not Easy Puzzles on another Sudoku Website?
- Title（参考訳）: 原文(投稿日:2012/01/28)へのリンク プロジェクト・パティ: なぜ別のスドクのウェブサイトでダイボリック・プッズを解けるのか?
- Authors: Arman Eisenkolb-Vaithyanathan,
- Abstract要約: 私は5つの人気ウェブサイトで1000以上のスドクパズルを分析し、各ウェブサイトの難易度を特徴付ける。
提案した2つの指標に基づいて,単純な教師なし分類器を用いた普遍評価システムを構築した。
本稿では,初期スドクの実践者が,スドクパズルの解法に利用できるアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we try to answer the question "What constitutes Sudoku difficulty rating across different Sudoku websites?" Using two distinct methods that can both solve every Sudoku puzzle, I propose two new metrics to characterize Sudoku difficulty. The first method is based on converting a Sudoku puzzle into its corresponding Satisfiability (SAT) problem. The first proposed metric is derived from SAT Clause Length Distribution which captures the structural complexity of a Sudoku puzzle including the number of given digits and the cells they are in. The second method simulates human Sudoku solvers by intertwining four popular Sudoku strategies within a backtracking algorithm called Nishio. The second metric is computed by counting the number of times Sudoku strategies are applied within the backtracking iterations of a randomized Nishio. Using these two metrics, I analyze more than a thousand Sudoku puzzles across five popular websites to characterize every difficulty level in each website. I evaluate the relationship between the proposed metrics and website-labeled difficulty levels using Spearman's rank correlation coefficient, finding strong correlations for 4 out of 5 websites. I construct a universal rating system using a simple, unsupervised classifier based on the two proposed metrics. This rating system is capable of classifying both individual puzzles and entire difficulty levels from the different Sudoku websites into three categories - Universal Easy, Universal Medium, and Universal Hard - thereby enabling consistent difficulty mapping across Sudoku websites. The experimental results show that for 4 out of 5 Sudoku websites, the universal classification aligns well with website-labeled difficulty levels. Finally, I present an algorithm that can be used by early Sudoku practitioners to solve Sudoku puzzles.
- Abstract（参考訳）: 本稿では,「数独の難易度とは何か?」という問いに答えようと試みる。
両パズルを解くための2つの異なる手法を用いて,スドゥークの難易度を特徴付けるための2つの新しい指標を提案する。
最初の方法は、スドゥークパズルを対応する満足度(SAT)問題に変換することに基づいている。
最初の提案された計量はSATクラウス長さ分布から導かれるもので、これは与えられた桁数とセルを含むスドゥークパズルの構造的複雑さを捉えている。
第2の方法は,西尾と呼ばれるバックトラッキングアルゴリズムに,一般的な4つのスドク戦略を組み込むことで,人間のスドク解法をシミュレートする。
乱数化された西尾のバックトラックイテレーションにおいて、スドク戦略が適用された回数を数えて、第2の測定値を算出する。
これら2つの指標を用いて,5つのWebサイトをまたいだ1000以上のスドクパズルを分析し,各Webサイトにおける難易度を特徴付ける。
提案指標とウェブサイトラベルの難易度との関係を,Spearmanのランク相関係数を用いて評価し,5サイト中4サイトについて強い相関関係を求めた。
提案した2つの指標に基づいて,単純な教師なし分類器を用いて,普遍的な評価システムを構築した。
この評価システムは,個々のパズルと異なるSudoku Webサイトからの難易度の両方を,Universal Easy,Universal Medium,Universal Hardの3つのカテゴリに分類することで,Sudoku Webサイト間の一貫した難易度マッピングを可能にする。
実験の結果,5サイト中4サイトにおいて,ユニバーサル分類はウェブサイトラベルの難易度とよく一致していることがわかった。
最後に,初期スドクの実践者が,スドクパズルの解法に利用できるアルゴリズムを提案する。
関連論文リスト
- PuzzleWorld: A Benchmark for Multimodal, Open-Ended Reasoning in Puzzlehunts [47.92619068073141]
我々は、ステップバイステップ、オープンエンド、クリエイティブマルチモーダル推論を評価するために設計された667のパズルハントスタイルの大規模ベンチマークであるPuzzleWorldを紹介した。
ほとんどの最先端モデルでは最終解の精度は1-2%に過ぎず、最高のモデルではパズルの14%しか解けず、ステップワイズ精度は40%に達する。
誤り解析により,現在のモデルは筋力的推論を示し,言語に基づく推論の限界に悩まされ,視覚的および空間的推論に不可欠なスケッチ能力が欠如していることが判明した。
論文 参考訳（メタデータ） (2025-06-06T16:17:09Z) - Sudoku-Bench: Evaluating creative reasoning with Sudoku variants [17.624558883326184]
Sudoku-Benchは、創造的で多段階の論理的推論を評価するための、キュレートされたベンチマークである。
Sudoku-Benchには、慎重に選択されたパズルセット、標準化されたテキストベースのパズル表現、数千の公開パズルと互換性のある柔軟なツールが含まれている。
論文 参考訳（メタデータ） (2025-05-22T02:24:35Z) - A Simple QUBO Formulation of Sudoku [0.0]
本稿では,擬似非制約二項最適化(QUBO)を用いた数独パズルの解法について述べる。
729変数を持つQUBOインスタンスが構築され、すべての制約のあるSudokuグリッドを符号化する。
結果として得られるインスタンスは、量子アニールまたは他の戦略で解決でき、完全に満たされたスドク格子を得ることができる。
論文 参考訳（メタデータ） (2024-03-07T09:54:06Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Automated Graph Genetic Algorithm based Puzzle Validation for Faster
Game Desig [69.02688684221265]
本稿では,コンピュータゲームにおける論理パズルを効率的に解くための進化的アルゴリズムを提案する。
制約満足度問題に対するハイブリッド遺伝的アプローチの様々なバリエーションについて論じる。
論文 参考訳（メタデータ） (2023-02-17T18:15:33Z) - Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw
Puzzles [67.39567701983357]
ビデオ異常検出(VAD)はコンピュータビジョンにおいて重要なトピックである。
近年の自己教師型学習の進歩に触発された本論文は,直感的かつ難解なプレテキストタスクを解くことによって,VADに対処する。
提案手法は3つの公開ベンチマークにおいて最先端のベンチマークよりも優れている。
論文 参考訳（メタデータ） (2022-07-20T19:49:32Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Using Small MUSes to Explain How to Solve Pen and Paper Puzzles [4.535832029902474]
本稿では,パズルを高レベル制約プログラミング言語で表現できるツールであるdemystifyを提案する。
MUSでパズルを解くための既存の技術にいくつかの改善を加えます。
手作業でペンと紙のパズルを解くための文書化戦略と比較することにより,Demystifyの有効性と汎用性を実証する。
論文 参考訳（メタデータ） (2021-04-30T15:07:51Z) - A new perspective of paramodulation complexity by solving massive 8
puzzles [0.4514386953429769]
スライディングパズルは、プレイヤーがボード上の特定のルートに沿ってスライドして特定のエンド構成に達するコンビネーションパズルです。
パラモジュレーションで得られる節数をカウントすることで、各パズルの難易度を評価できることが分かりました。
論文 参考訳（メタデータ） (2020-12-15T11:47:47Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - SudoQ -- a quantum variant of the popular game [1.5229257192293197]
古典ゲームSudookuの量子バージョンであるSudoQを紹介する。
SudoQパズルの解集合は古典的な(可換な)設定よりもはるかに大きい。
論文 参考訳（メタデータ） (2020-05-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。