The chaos within Sudoku.
The chaos within Sudoku.
复制标题
DOI：
10.1038/srep00725
复制
发表时间：
2012
影响因子：
4.6
通讯作者：
Toroczkai, Zoltan
中科院分区：
文献类型：
--
作者：
Ercsey-Ravasz, Maria;Toroczkai, Zoltan
数独谜题的数学结构类似于许多应用的基础上的硬约束满足问题，包括蛋白质折叠和玻璃自旋系统的基态问题。通过一个精确的映射数独到一个确定性的，连续时间的动力系统，在这里，我们表明，数独的困难转化为瞬态混沌行为表现出这个系统。我们还表明，逃逸率κ，瞬态混沌的不变量，提供了一个标量测量的难题的硬度，以及与人类的难度评级。因此，η = −log10 κ可以用来定义一个“里氏”类型的谜题硬度，简单谜题的硬度为0 < η ≤ 1，中等谜题的硬度为1 < η ≤ 2，硬谜题的硬度为2 < η ≤ 3，超硬谜题的硬度为η > 3。据我们所知，没有已知的谜题η > 4。
The mathematical structure of Sudoku puzzles is akin to hard constraint satisfaction problems lying at the basis of many applications, including protein folding and the ground-state problem of glassy spin systems. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle's hardness that correlates well with human difficulty ratings. Accordingly, η = −log10 κ can be used to define a “Richter”-type scale for puzzle hardness, with easy puzzles having 0 < η ≤ 1, medium ones 1 < η ≤ 2, hard with 2 < η ≤ 3 and ultra-hard with η > 3. To our best knowledge, there are no known puzzles with η > 4.
登录
查看更多内容
DOI：
10.1073/pnas.81.4.1276
发表时间：
1984-01-01
期刊：
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA-PHYSICAL SCIENCES
影响因子：
--
作者：
KADANOFF, LP;TANG, C
通讯作者：
TANG, C
DOI：
10.1088/0305-4470/15/10/028
发表时间：
1982-01-01
期刊：
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL
影响因子：
--
作者：
BARAHONA, F
通讯作者：
BARAHONA, F
DOI：
10.1073/pnas.0606359104
发表时间：
2007-01-09
影响因子：
11.1
作者：
Elser, V.;Rankenburg, I.;Thibault, P.
通讯作者：
Thibault, P.
DOI：
10.1088/1742-5468/2008/12/p12004
发表时间：
2008-12-01
影响因子：
2.4
作者：
Zdeborova, Lenka;Mezard, Marc
通讯作者：
Mezard, Marc
影响因子：
19.6
作者：
Ercsey-Ravasz, Maria;Toroczkai, Zoltan
通讯作者：
Toroczkai, Zoltan