Complexity measures for logic puzzles vary in correlation with difficulty across puzzle types¶

Claim · All claims
Evidence · 1 study · associational r? · q2
Currency · newest study 2022 · not yet checked against its sources · not reviewed by a person

Subclaims¶

q2 i? Simple complexity measures for logic puzzles correlate mostly only weakly with difficulty, but for some puzzles like Rush Hour even simple measures provide good prediction, while for Sudoku a linear combination of measures achieves high correlation. → Pelánek 2022

Evidence¶

Pelánek 2022¶

Pelánek, R., Effenberger, T., & Čechák, J. (2022). Complexity and Difficulty of Items in Learning Systems. International Journal of Artificial Intelligence in Education. https://doi.org/10.1007/s40593-021-00252-4

q2 · i? · associational · r?

The article reports that "simple complexity measures (size, length of solution) correlate mostly only weakly with difficulty" but that "for some puzzles (Rush hour), even such simple measures can provide a good prediction of difficulty."

"The results show that simple complexity measures (size, length of solution) correlate mostly only weakly with difficulty. However, for some puzzles (Rush hour), even such simple measures can provide a good prediction of difficulty."

Discussion¶

Related Claims¶

• MUSE tasks form coherent but non-redundant capability groups, with Jigsaw Puzzle a distinct compositional capability — related
• Shallow complexity measures for word problems correlate only weakly with difficulty — a narrower finding that bears on this claim