Blogs

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.





Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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

More Features >>

Go Parallel Twitter Feed

More Twitter >>

Our Facebook Community