Thesis Review / Posudek oponenta
Title: Difficulty Rating of Sudoku Puzzles: Comparsion of Several Techniques
Author: Martin Křivánek
Reviewer: Jiří Šimša
Proposed Grade: E
Overview: The broader context of this thesis is the study of methods for predicting
difficulty rating of computational problems. The goal of this thesis is an analysis of
correlation between the performance of human solvers and the performance of
computer algorithms. In case of high correlation between the two variables,
computer algorithms could be used as accurate predictors of problem‘s difficulty.
Summary: After motivating the work in an introduction, the thesis defines what a
Sudoku problem is, describes the human solver data used for the analysis, and
provides an overview of algorithmic approaches for solving a Sudoku puzzle. The
thesis then presents an experimental evaluation of correlation between human
solvers and three different algorithms. Lastly, the thesis studies the suitability of
these algorithms for prediction of other phenomena.
Positives: The work is well motivated and the questions the thesis seeks to answer
are very interesting. Throughout his thesis work, the student has demonstrated
several important computer science skills:
1. The ability to adapt existing algorithms to a particular computational
problem and produce a working implementation of these algorithms.
2. The ability to carry out controlled experiments to collect performance
measurements for the algorithms he implemented.
3. The ability to compare the results of his measurements with the data
on human solving and to draw conclusions from these comparisons.
Negatives: Unfortunately, the quality of the thesis is impeded by several factors
and the level of rigor throughout the work is generally low.
Although I applaud the student’s decision to write the thesis in English, the
decision came at a price of decreased readability. The document contains
grammatical errors, convoluted sentences, colloquial expressions, typos, and
incorrectly translated words.
More importantly, the thesis does not do justice to its scientific method. The
introduction of the thesis mostly discusses the motivation for the work to be
presented and then jumps to describing the organization of the thesis. What is
missing here is a clear statement of the problem addressed by the thesis and the
goal of the thesis. Given there is no explicit goal stated in the introduction, it is
difficult to judge whether this work has succeeded in what it set out to do. Ideally,
the introduction should also state a hypothesis and describe what steps will be
taken to evaluate the hypothesis.
The deficiencies of the second section include:
● The superficiality of the description of the data on human solving
exemplified by the decision to discard one year of measurements
without providing the reader with evidence that would justify this
decision.
● The varied level of detail with which the thesis discusses the different
approaches to Sudoku solving.
● Forward references to the description of algorithms to be evaluated;
An overview section should discuss all approaches.
● The lack of motivation for selecting the three approaches used in the
experimental evaluation section.
The deficiencies of the third section include:
● The superficiality of the sensitivity analysis of the simulated annealing
and the harmony analysis exemplified by presenting the reader with
certain „good“ values for algorithm parameters without providing
evidence that would justify the choices.
● The lack of rigor in defining what random variables were used for
correlation measurements; this renders certain graphs difficult to
interpret.
● Concluding the section with a superficial comparison of several
approaches, mixing previous work with the work of the thesis without
clearly distinguishing the two.
The deficiencies of the fourth section include:
● The lack of motivation for studying general applicability of the
evaluated algorithms given the poor performance of the algorithms
when tailored to a specific problem.
● Using two closely related problems for the study of general
applicability.
● The superficial discussion of why harmony analysis did not work.
The conclusion of the thesis simply summarizes the thesis. What is missing here is a
discussion of the original hypothesis in the light of the experiments carried out,
description of what lessons were learned in the course of the thesis, what
experiments worked / did not work and conjectures as to why. Finally, unless a
thesis has provided a complete solution to a problem, a conclusion should also point
out interesting avenues for future work.
Verdict: All in all, the main problem of the thesis is that it sets out on an ambitious
journey but instead of meticulously exploring each of its parts step by step it resorts
to shortcuts. In comparison to the work of other master’s degree students I had the
opportunity to recently review, this thesis is sub par. However, it meets the
minimum standard for passing a diploma thesis and, therefore, I propose this thesis
to receive the grade E.