正在加载图片...
abstract Creating and rating the difficulty of Sudoku puzzles is currently a hard computational prob- lem. In particular, most current approaches require the use of somewhat arbitrary choices for the relative difficulties of Sudoku strategies. We present here a novel solver-based solution to this problem by framing Sudoku as a search problem and using the expected search time to determine the difficulty of different strategies. Our method was chosen for its relative independence from external views on the relative difficulties of strategies Upon validation of our metric with a sample of 800 externally rated puzzles with 8 gra dations of difficulty, we found a Goodman-Kruskal y coefficient of 0.82, indicating significant correlation. An independent evaluation of 1000 typical puzzles produced a difficulty distri- bution similar to the distribution of solve times empirically created by millions of users at www.websudoku.com Based upon this difficulty metric, we created two separate puzzle generators. One gen- erates mostly easy to medium puzzles; when run with 4 difficulty levels, it creates boards of levels 1, 2, 3, and 4 in 0.25, 3.1, 4.7, and 30 minutes, respectively. The other modifies difficult boards to create boards of similar difficulty; when tested on a board of difficulty 8122, it was able to create 20 boards with average difficulty 711l in 3 minutesAbstract Creating and rating the difficulty of Sudoku puzzles is currently a hard computational prob￾lem. In particular, most current approaches require the use of somewhat arbitrary choices for the relative difficulties of Sudoku strategies. We present here a novel solver-based solution to this problem by framing Sudoku as a search problem and using the expected search time to determine the difficulty of different strategies. Our method was chosen for its relative independence from external views on the relative difficulties of strategies. Upon validation of our metric with a sample of 800 externally rated puzzles with 8 gra￾dations of difficulty, we found a Goodman-Kruskal γ coefficient of 0.82, indicating significant correlation. An independent evaluation of 1000 typical puzzles produced a difficulty distri￾bution similar to the distribution of solve times empirically created by millions of users at www.websudoku.com. Based upon this difficulty metric, we created two separate puzzle generators. One gen￾erates mostly easy to medium puzzles; when run with 4 difficulty levels, it creates boards of levels 1, 2, 3, and 4 in 0.25, 3.1, 4.7, and 30 minutes, respectively. The other modifies difficult boards to create boards of similar difficulty; when tested on a board of difficulty 8122, it was able to create 20 boards with average difficulty 7111 in 3 minutes
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有