数独难度级别
我正在构建一个用 Javascript 编写的有趣的数独游戏。
一切正常，每次都使用单一解决方案完全生成板。
我唯一的问题是，这就是阻止我向公众发布我的项目的原因
是我不知道如何对我的主板进行难度等级评分。我到处都看过
发布在论坛等上。我不想自己编写算法，这不是重点 项目，
此外，它们对我来说太复杂了，因为我不是数学家。
我唯一接近的是这个通过 JS 进行评分的网站
但是问题是，代码是以一种糟糕的、无文档记录的、非常临时的方式编写的，
因此不能借用...
我会说到重点 -
任何人都可以指出我一个提供的地方的源代码数独分级/评级？
谢谢
2011 年 6 月 22 日更新：
这是我的数独游戏，我已经实现了自己的评分系统，该系统依赖
关于基本的人类逻辑解决技术，所以请检查一下。
I am building a Sudoku game for fun, written in Javascript.
Everything works fine, board is generated completely with a single solution each time.
My only problem is, and this is what's keeping me from having my project released to public
is that I don't know how to grade my boards for difficulty levels. I've looked EVERYWHERE,
posted on forums, etc. I don't want to write the algorithms myself, thats not the point of this
project,
and beside, they are too complex for me, as i am no mathematician.
The only thing i came close to was is this website that does grading via JS
but the problem is, the code is written in such a lousy undocumented, very ad-hoc manner,
therefor cannot be borrowed...
I'll come to the point -
Can anyone please point me to a place which offers a source code for Sudoku grading/rating?
Thanks
Update 22.6.11:
This is my Sudoku game, and I've implemented my own grading system which relies
on basic human logic solving techniques, so check it out.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我自己也考虑过这个问题，我能做的最好的事情就是通过实际解决它并分析博弈树来决定解决这个难题的难度。
最初：
使用“人类规则”来实现您的求解器，而不是使用人类玩家不太可能使用的算法。 （这本身就是一个有趣的问题。）根据人类使用的难度，对求解器中的每个逻辑规则进行评分。使用数百或更大的值，以便您可以自由调整相对于彼此的分数。
解决难题。在每个位置：
谜题的整体难度是游戏树路径中各个位置的得分总和。
编辑：替代位置分数：不是使用更难的规则完全排除扣除，而是计算每个规则（或复合应用）的总体难度并选择最小值。 （这里的逻辑是，如果规则 A 的得分为 50，规则 B 的得分为 400，并且规则 A 可以应用于 1 个单元格，但规则 B 可以应用于 10 个单元格，则位置得分为 40，因为玩家更有可能找出十种较难的玩法之一，而不是单一的较容易的玩法。但这需要您计算所有可能性。）
编辑：Briguy37 建议的替代方案：将所有扣除纳入位置得分中。每个位置的评分为
1 / (1/d1 + 1/d2 + ...)，其中d1、d2等是个体扣除额。 （这基本上是在给定个体“演绎阻力”d1、d2等的位置上计算“进行任何演绎的阻力”。但这需要您计算所有可能性。 ）希望这种评分策略能够产生一个谜题指标，该指标随着您对难度的主观评估的增加而增加。如果没有，那么调整规则的分数（或从上述选项中选择的启发式）可能会实现所需的相关性。一旦你在分数和主观体验之间取得了一致的相关性，你应该能够判断“简单”、“困难”等的数字阈值应该是什么。然后你就完成了！
I have considered this problem myself and the best I can do is to decide how difficult the puzzle is to solve by actually solving it and analyzing the game tree.
Initially:
Implement your solver using "human rules", not with algorithms unlikely to be used by human players. (An interesting problem in its own right.) Score each logical rule in your solver according to its difficulty for humans to use. Use values in the hundreds or larger so you have freedom to adjust the scores relative to each other.
Solve the puzzle. At each position:
The puzzle's overall difficulty is the sum of the scores of the positions in your path through the game tree.
EDIT: Alternative position score: Instead of completely excluding deductions using harder rules, calculate overall difficulty of each rule (or compound application) and choose the minimum. (The logic here is that if rule A has score 50 and rule B has score 400, and rule A can be applied in one cell but rule B can be applied in ten, then the position score is 40 because the player is more likely to spot one of the ten harder plays than the single easier one. But this would require you to compute all possibilities.)
EDIT: Alternative suggested by Briguy37: Include all deductions in the position score. Score each position as
1 / (1/d1 + 1/d2 + ...)whered1,d2, etc. are the individual deductions. (This basically computes "resistance to making any deduction" at a position given individual "deduction resistances"d1,d2, etc. But this would require you to compute all possibilities.)Hopefully this scoring strategy will produce a metric for puzzles that increases as your subjective appraisal of difficulty increases. If it does not, then adjusting the scores of your rules (or your choice of heuristic from the above options) may achieve the desired correlation. Once you have achieved a consistent correlation between score and subjective experience, you should be able to judge what the numeric thresholds of "easy", "hard", etc. should be. And then you're done!
Donald Knuth 研究了这个问题，并提出了用于解决数独的Dancing Links 算法，然后对数独进行了评分他们的难度。
Google 周围，有几个 Dancing Links 引擎的实现。
Donald Knuth studied the problem and came up with the Dancing Links algorithm for solving sudoku, and then rating the difficulty of them.
Google around, there are several implementations of the Dancing Links engine.
也许您可以对谜题的一般“限制性”进行评分？考虑一个新的谜题（只有提示）可能有一定数量的单元格，可以通过消除它不能包含的值来简单地确定。我们可以说，这些单元格被“限制”为比典型单元格更少的可能值，并且存在的单元格受到的限制越多，人们在不猜测的情况下就能在谜题上取得更多进展。 （在这里，我们认为“猜测”的要求是谜题变得困难的原因。）
然而，在某些时候，玩家必须开始猜测，并且单元格的约束性很重要，因为可供选择的值较少给定的单元格越容易找到正确的值（并增加其他单元格的约束性）。
当然，我实际上并不玩数独（我只是喜欢为其编写游戏和求解器），所以我不知道这是否是一个有效的指标，只是大声思考=）
Perhaps you could grade the general "constrainedness" of a puzzle? Consider that a new puzzle (with only hints) might have a certain number of cells which can be determined simply by eliminating the values which it cannot contain. We could say these cells are "constrained" to a smaller number of possible values than the typical cell and the more highly constrained cells that exist the more progress one can make on the puzzle without guessing. (Here we consider the requirement for "guessing" to be what makes a puzzle hard.)
At some point, however, the player must start guessing and, again, the constrainedness of a cell is important because with fewer values to choose between for a given cell the easier it is to find the correct value (and increase the constrainedness of other cells).
Of course, I don't actually play Sudoku (I just enjoy writing games and solvers for it), so I have no idea if this is a valid metric, just thinking out loud =)
我有一个简单的求解器，它只寻找行、列和正方形中的独特可能性。当它解决了用这种方法可以解决的几个单元格时，它会选择一个剩余的候选单元来尝试它，看看简单的求解器是否会导致一个解决方案或一个没有可能性的单元格。在第一种情况下，难题得到了解决，在第二种情况下，一种可能性已被证明是不可行的，从而被消除。在第三种情况下，既没有最终的解决方案，也没有不可行的结果。
可以达到抵扣额。
循环执行此过程的主要结果是消除可能性，直到拾取
正确的单元格输入会产生解决方案。到目前为止，这个程序已经解决了最困难的问题
谜题无失败。它可以毫无困难地解决具有多种解决方案的难题。如果
试验候选者是随机挑选的，它将生成所有可能的解决方案。
然后，我根据必须解决的非法候选人的数量来生成谜题的难度。
在简单求解器找到解决方案之前就被消除了。
我知道这就像猜测，但如果简单的逻辑可以消除一个可能的候选人，那么一个
更接近最终的解决方案。
麦克风
I have a simple solver that looks for only unique possibilities in rows, columns and squares. When it has solved the few cells solvable by this method, it then picks a remaining candidate tries it and sees if the simple solver then leads to either a solution or a cell empty of possibilities. In the first case the puzzle is solved, in the second, one possibility has shown to be infeasible and thus eliminated. In the third case, which leads to neither a final solution nor an infeasibility, no
deduction can be reached.
The primary result of cycling through this procedure is to eliminate possiblities until picking
a correct cell entry leads to a solution. So far this procedure has solved even the hardest
puzzles without fail. It solves without difficulty puzzles with multiple solutions. If the
trial candidates are picked a random, it will generate all possilbe solutions.
I then generate a difficulty for the puzzle based on the number of illegal candidates that must
be eliminated before the simple solver can find a solution.
I know that this is like guessing, but if simple logic can eliminated a possible candidate, then one
is closer to the final solution.
Mike
我过去曾经这样做过。
关键是你必须从人类逻辑的角度弄清楚该使用哪些规则。您提供的示例详细介绍了许多不同的人类逻辑模式，如右侧列表所示。
您实际上需要使用这些规则而不是计算机规则来解决难题（计算机规则可以使用简单的模式替换在几毫秒内解决它）。每次更换棋盘时，您都可以从“最简单”的模式（例如，单元格或行中的单个打开的框）开始，并沿着链向下移动，直到找到下一个要使用的逻辑“规则”。
在对数独进行评分时，每种方法都会分配一些分值，您可以将这些分值添加到需要填写的每个字段中。虽然“单个空单元格”可能会得到 0，但“XY 链”可能会得到 100。您将所需的所有方法（和频率）制成表格，最后得到最终的权重。有很多地方列出了这些权重的预期值，但它们都是相当经验性的。您正在尝试对人类逻辑进行建模，因此请随意提出自己的权重或增强系统（如果您确实仅使用 XY 链，则该难题可能比需要更高级的情况更容易机制）。
您可能还会发现，即使您有一个独特的数独，它也无法通过人类逻辑解决。
另请注意，这比以标准、模式化的方式解决它需要更多的 CPU 资源。几年前，当我编写代码时，需要花费数秒（我具体忘记了，但甚至可能长达 15 秒）来解决我创建的一些生成的谜题。
I've done this in the past.
The key is that you have to figure out which rules to use from a human logic perspective. The example you provide details a number of different human logic patterns as a list on the right-risde.
You actually need to solve the puzzle using these rules instead of computer rules (which can solve it in milliseconds using simple pattern replacement). Every time you change the board, you can start over from the 'easiest' pattern (say, single open boxes in a cell or row), and move down the chain until you find one the next logical 'rule' to use.
When scoring the sodoku, each methodology is assigned some point value, which you would add up for every field you needed to fill out. While 'single empty cell' might get a 0, 'XY Chain' might get 100. You tabulate all of the methods needed (and frequency) and you wind up with a final weighting. There are plenty of places that list expected values for those weightings, but they are all fairly empirical. You're trying to model human logic, so feel free to come up with your own weightings or enhance the system (if you really only use XY chains, the puzzle is probably easier than if it requires more advanced mechanisms).
You may also find that even though you have a unique sodoku, that it is unsolvable through human logic.
And also note that this is all far more CPU intensive than solving it in a standard, patterned way. Some years ago when I wrote my code, it was taking multiple (I forget exactly, but maybe even up to 15) seconds to solve some of the generated puzzles I'd created.
假设难度与用户解决难题所需的时间成正比，那么这里有一个人工智能解决方案，随着时间的推移，它会接近理想算法的结果。
注意：您应该将第一个谜题保留在随机谜题列表中，以便您可以获得越来越好的统计数据。
注意：当用户选择玩额定难度的谜题时，这不应影响平均随机解决时间或平均解决时间乘数，除非您想计算加权平均值（否则如果用户玩很多更难的谜题，它们的平均时间和时间乘数会有所偏差）。
使用上述方法，解决方案的评分范围为 0（已解决/没有时间解决）到 1（用户可能会在平均时间内解决这个难题）到 2（用户解决这个难题可能需要两倍的时间）他们的平均时间）到无穷大（用户将花很长时间才能找到这个难题的解决方案）。
Assuming difficulty is directly proportional to the time it takes a user to solve the puzzle, here is an Artificially Intelligent solution that approaches the results of the ideal algorithm over time.
Note: You should keep the first puzzle in your random puzzles list so that you can get better and better statistics on it.
Note: When users choose to play puzzles with rated difficulty, this should NOT affect the average random solution time or average solution time multiplier, unless you want to get into calculating weighted averages (otherwise if a user plays a lot of harder puzzles, their average time and time multipliers will be skewed).
Using the method above, a solution would be rated from 0 (already solved/no time to solve) to 1 (users will probably solve this puzzle in their average time) to 2 (users will probably take twice as long to solve this puzzle than their average time) to infinity (users will take forever to find a solution to this puzzle).