KKResearchers at the University of Klagenfurt have achieved a major breakthrough in automated problem-solving with “CheckMate”. This new AI-driven technology independently develops algorithms for complex combinatorial and optimisation problems – such as those encountered in the optimal planning of industrial plants and production processes – delivering significantly better results than existing methods for “hard problems” in industrial practice. A patent has already been filed for the invention, which represents a major step forward towards the “holy grail of problem-solving”.

Computer programmes were already able to solve 9×9 Sudokus without any trouble more than twenty years ago. “However, the core issue lies in the massive explosion of potential solutions as soon as the board is expanded,” explains Gerhard Friedrich, Professor at the Department of Artificial Intelligence and Cybersecurity at the University of Klagenfurt and board member of the FWF-funded Cluster of Excellence Bilateral AI. If the number of rows, columns, and possible numerical entries increases – for example, to 100,000 rows, columns, and numbers, making the problem comparable in scale to practical industrial applications – current general problem-solving methods become overwhelmed. The memory requirements exceed all physical capabilities, and one would have to wait thousands of years for an answer. If additional constraints are then introduced – such as required patterns among the numbers used, comparable to supplementary requirements in industrial problems – the difficulty of the problem escalates dramatically.
Gerhard Friedrich and his colleagues have been working for many years on solutions to these so-called “hard problems”, where humans, with their heuristic problem-solving skills, have previously been considered superior to machines. There are numerous fields of application: from railway safety systems to the most optimal planning of industrial plants or optimisation challenges in logistics – in all of these areas, the goal is to find the best possible solution from an often unimaginably large pool of potential options.
A team of researchers at the University of Klagenfurt – comprising Veronika Semmelrock, Benedetta Strizzolo, Francesco Zuccato, Patrick Rodler, Konstantin Schekotihin, and Gerhard Friedrich – has now succeeded in making a significant contribution towards realising the “holy grail of problem-solving”: the human formulates a problem, and the computer solves it. With CheckMate, they are now introducing automated evolutionary code generation for combinatorial problems, including optimisation. A patent was also recently filed for this new technology, which is highly relevant to industry and will be presented to the specialist community at the prestigious International Joint Conference on Artificial Intelligence 2026. The team also features a unique collaboration: Veronika Semmelrock and Francesco Zuccato are doctoral students at the University of Klagenfurt, while Benedetta Strizzolo is a master’s student from the University of Udine who was integrated into the Klagenfurt team as part of a project.
“In recent years, we have had to recognise that we as humans are failing to develop tools for such difficult problems that come closer to the vision of an AI that truly solves hard problems independently,” explains Gerhard Friedrich. He continues: “Recently, however, there have been decisive breakthroughs in automated software development that have paved the way for entirely new, AI-driven programming processes. A promising example is code evolution, which automatically generates programmes based on LLMs and has already outperformed human-developed software solutions in some cases. However, when applied to complex combinatorial and optimisation problems of the kind we see in industry, generating programmes that solve them efficiently and reliably is anything but trivial.”
CheckMate is a tool that can be integrated into the open-source code evolution framework OpenEvolve. A strict, logic-based correctness check of solutions, systematic evaluation of programme efficiency, and continuous feedback mean that high-quality algorithms emerge from an initially empty programme through a step-by-step refinement process. CheckMate does not need to be told how to calculate solutions – it merely requires the what, i.e., a description of what a solution looks like, and a small set of sample instances. Illustrated using very large and complex Sudokus, this would mean that one only describes the rules of the game to CheckMate, whereupon it can automatically generate a solution algorithm for any given board. “Our team has now succeeded in showing that the programmes generated with CheckMate outperform current leading technologies and achieve better solutions for hard problems with direct industrial relevance than was previously possible. In particular, CheckMate has also made it possible to solve particularly hard, previously unsolved problems for the first time. We therefore seem to have entered the era in which AI is at least a match for humans in solving complex problems,” says Gerhard Friedrich, summarising the results: “LLMs + Logic + Evolution = Superhuman Programming.”
Der Beitrag Klagenfurt AI solves industry’s “hard problems” erschien zuerst auf University of Klagenfurt.