'Problem Solving' Tasks and Computer Science

Updated 2020-05-20 / Created 2020-05-20 / 582 words

Is solving Sudoku and similar puzzles by hand really useful in building computer science ability? We don't think so.

Co-written with Aidan, developer of Emu War. He did most of it.

Computer Science (CS) can be defined as 'the study of problems and problem-solving, and the study of solutions to those problems'. It seems, at first glance, that solving logic puzzles would develop CS skill, since 'CS is all about problem solving'. But this isn't the case; computer science is about inventing creative ways to solve these problems, understanding their mathematical basis, being able to express your ideas in a precise and clear form, and being able to translate these ideas into code. The goal of this is for computers to be able to solve them automatically with their ability to do repetitive tasks very fast, instead of relying on the flexible but slow general reasoning and intuitive abilities of humans.

One common example of a problem-solving puzzle to help develop 'computational skills' is Sudoku. While the logical reasoning skills used in Sudoku are admirable, and may even be useful for a few problems in CS, we do not often think about why we take certain steps when deducing the value of a tile, instead reasoning retroactively about how we know it. When we solve Sudoku we do not develop a general algorithm for solving Sudoku in our heads and then execute it; instead, we solve it through a combination of intuition and creative logical reasoning, which are not well-defined or easily applicable to computers. Here is an interesting article relating to this.

'Computational skills' puzzles are inherently unhelpful as tools for improving CS ability, as they do not force players to formalise and be specific in their thought processes while solving problems; instead, they develop the player's intuitive ability. In chess, competitive players often talk about 'developing intuition', i.e. being able to play a chess game automatically and without formalising their thought processes. Similarly, in Sudoku, top-class solvers develop intuition so that they instinctively 'know' which number to put next. This intuition is not limited to the top category of solvers; even amateur players use this to decide which area to focus on. Instead of being able to create a formal program to solve Sudoku, the solver has programmed themself in a way they can't easily explain or pass on.

These puzzles are demonstrably a different class of problem to designing algorithms to solve them; if they were similar, then machines that can solve one set should mostly be able to solve the other. However, although modern computers are extremely fast, and able to solve many common 'computational thinking' tasks orders of magnitude faster than humans, humans are still in control, for this simple reason: computers cannot program other computers. Since computers can do 'computational skills' tasks easily, but cannot (yet) solve the problems of computer science itself, we can conclude that these are entirely different categories of problem. In other words, learning to do 'computational skills' problems does not help you become a computer scientist, it helps you become a computer - and one easily outdone by a real computer at these tasks.

Update (28/01/2023 CE):

It only took a year after this was written for OpenAI Codex to become reasonably competent at programming. Oops. And I didn't actually think to update this until now, when I happened to be reviewing it. Regardless, I think the relevant argument still holds up, inasmuch as even today's language models still aren't that great at "thinky" programming tasks, and mostly serve to reveal how much stupid glue code we have to write.