# Clay Breshears

See more from this author

# Seeing the Light with Backtracking

Use the processing speed of computers to generate and explore different possible configurations to solve Akari puzzles.

Akari is a logic puzzle created by Nikoli Co., Ltd., a publisher of puzzle magazines in Japan since 1980. Like many good logic games, Akari (or "Light Up") has very simple rules, but can pose problems that range from simple to very hard. You only need a pencil and your mind to solve Akari or any other puzzle that Nikoli puts out.

Akari is played on a rectangular grid of black and white squares. A subset of black squares will contain an integer from 0 to 4. The object of the puzzle is to place light bulbs on white squares according to the following conditions:

• Any black square that contains a number must be surrounded by exactly that number of light bulbs in the adjacent vertical (North and South) and horizontal (East and West) white squares.
• Rays of light from bulbs radiate along the vertical and horizontal directions until reaching a black square or the edge of the grid.
• Each white square in the grid must be illuminated while no bulb may be illuminated by another bulb.

When I solve Akari puzzles, I use the analogy of chess rooks as light bulbs since the vertical and horizontal attack matches the light bulb illumination paths. So, keeping the chess theme from the N-Queens problem from the last two posts, I think of this as rooks and islands where some (black square) islands require a specific number of adjacent rooks, no two rooks can attack each other, a rook's attack stops at the beach of an island, and no additional rook can be placed since all white squares are attacked by at least one rook. However, to keep closer to the actual description of Akari, I'll use the light bulb in this post.

Regardless of whether you imagine light bulbs or rooks or four-armed killer robots with ray guns, a human approach to solving an Akari puzzle starts with finding configurations that are "forced" by the conditions of the puzzle (e.g., a 4-square requiring the four open squares filled by a bulb or a 2-square in the corner with only two open adjacent squares). After adding bulbs and tracing out the covered squares, other forced moves will be revealed. More complex puzzles will have fewer obvious configurations and require some logical thinking about the consequences of placing bulbs on alternate squares.

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

### Features

• #### How Data Dependence Affects Performance

Data dependence between statements is a straightjacket on the compiler's ability to optimize code for parallelism. So to get the maximum benefit from parallel code, data dependence must be carefully managed

• #### The Intel Threading Building Blocks Flow Graph

User feedback inspired the flow graph feature in Intel Threading Building Blocks, which allows programmers to express static and dynamic dependency graphs, as well as reactive or event-based graphs.

• #### Dataflow Programming: Handling Huge Data Loads Without Adding Complexity

Manage the data pipelines rather than webs of threads and processes

• #### Language of the Month: Intel's Cilk Plus

The latest C/C++ language extension to facilitate parallel programming

More Features >>

More Twitter >>