Is Light Up (Akari) Hard for Computers? The NP-Complete Puzzle

Light Up looks like one of the gentlest logic puzzles around: place some light bulbs, light up the grid, mind the numbered walls. So here's a fact that surprises almost everyone — in a precise mathematical sense, Light Up (Akari) is genuinely hard. Not hard for you on a Tuesday afternoon, but hard for computers, in the same category as some of the most notoriously difficult problems in computer science. The puzzle is proven NP-complete. This guide explains what that actually means, why a puzzle with such simple rules can be so computationally tough, and — reassuringly — why none of it stops you from happily solving one. Speaking of which, you can play a Light Up puzzle right after.

The surprising headline: Akari is NP-complete

Researchers in computational complexity have shown that Light Up (Akari) is NP-complete. That's a formal classification, and it puts the humble light-bulb puzzle in the company of famously hard problems. It also means Akari isn't alone — a whole roster of beloved pencil puzzles, including generalised Sudoku, Nurikabe, and Slitherlink, have been proven NP-complete too. Simple rules, it turns out, are no guarantee of an easy problem.

So what does "NP-complete" actually mean, in plain terms?

What "NP-complete" means, without the jargon

Strip away the technicality and NP-complete describes a problem with two key properties:

1. A solution is easy to check, but hard to find. If someone hands you a completed Light Up grid, you can verify it's correct in seconds — just confirm every cell is lit, no bulbs clash, and the walls are satisfied. But finding that solution from scratch, for an arbitrary grid, is believed to require an amount of work that explodes as the grid grows.

2. They're all secretly the same problem. "NP-complete" problems are the hardest in a class called NP, and they're all interconnected: a fast, efficient method for solving any one of them would instantly give a fast method for solving all of them — including thousands of important real-world problems in logistics, scheduling, and chip design. No one has ever found such a method, and most computer scientists believe none exists. (Whether one could exist is the famous P versus NP question — a million-dollar open problem.)

So when we say Akari is NP-complete, we're saying: solving a general Light Up puzzle is, in the worst case, as hard as the hardest problems we know of.

How can such a simple puzzle be so hard?

This is the genuinely fascinating part. The difficulty doesn't come from complicated rules — Akari's rules are trivial. It comes from the explosion of possibilities as the grid grows.

On a big, sparsely-clued grid, each open cell might or might not hold a bulb, and the choices interact in tangled ways: a bulb here forbids bulbs along its whole corridor, a numbered wall there constrains its neighbours, and a dark cell across the board quietly demands to be lit. As the grid gets larger, the number of possible bulb arrangements grows astronomically, and there's no known shortcut that's guaranteed to home in on the single valid one without, in the worst case, exploring a huge search space.

That's the paradox of NP-complete puzzles: dead-simple to describe, potentially brutal to solve in general.

Then how do humans solve them at all?

If the general puzzle is so hard, how do you finish one over coffee? Two reasons.

First, the puzzles you play are specially designed. A constructor doesn't hand you a random grid; they craft one with a unique solution reachable by a clean chain of logic. That careful design is exactly what spares you the brutal worst case — the hard instances that make Akari NP-complete are the nasty, pathological ones, not the elegant puzzles in a book or on this site. (How that design works is the subject of our piece on how Light Up puzzles are made.)

Second, NP-completeness is about the worst case and large sizes. A 5×5 or 10×10 grid is tiny by computational standards. Even a brute-force computer cracks small grids instantly, and a human armed with the right solving techniques follows the intended logical path without ever fighting the exponential blow-up. The theoretical hardness only bites for enormous, adversarial grids you'll never actually be handed.

Why this is a fun fact, not a warning

None of this should make you nervous about the puzzle. It's a delightful piece of trivia: the gentle little bulb puzzle on your screen belongs to the same complexity class as problems that keep computer scientists up at night. It's a reminder that "simple rules" and "easy problem" are not the same thing — one of the deepest and most surprising lessons in all of computer science, hiding inside a puzzle you can learn in a minute.

So enjoy the irony, then go put it to rest by solving a perfectly fair, perfectly solvable grid. Play Light Up (Akari) now, or brush up on the rules first.

Frequently asked questions

Is Light Up (Akari) NP-complete?

Yes. Computer scientists have proven that Light Up (Akari) is NP-complete, placing it among the hardest problems in the complexity class NP. This means that, in the worst case, solving an arbitrary Light Up grid is computationally as hard as famously difficult problems, despite the puzzle's very simple rules.

What does NP-complete mean for a puzzle?

It means a solution is easy to verify but, in general, hard to find — and that the problem is among the hardest in its class, so an efficient method for solving it would solve thousands of other hard problems too. For puzzles, it implies that arbitrary large grids can be extremely difficult to solve algorithmically in the worst case.

If Akari is NP-complete, why can I still solve it?

Because the puzzles you play are specially designed to have a single solution reachable by clean logic, which avoids the worst-case difficulty entirely. NP-completeness concerns worst-case, large, adversarial grids — not the small, carefully constructed puzzles in books and apps, which both humans and computers solve easily.

Are other logic puzzles NP-complete?

Yes. Several well-known Nikoli-style puzzles have been proven NP-complete, including generalised Sudoku, Nurikabe, and Slitherlink, alongside Light Up. It's a striking pattern: many puzzles with extremely simple rules turn out to belong to this hard complexity class.