Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Seeing the Light with Backtracking

December 22, 2011

Can we program a computer to solve Akari like a human? Probably, but I doubt if the subtleties of the human mind's thought processes to deal with unforeseen situations can be programmed efficiently. Maybe one day, but not today. Instead, we should use the processing speed of computers to generate and explore many different possible bulb placement configurations to determine which one solves the puzzle. At this point you should have realized that we'll use backtracking to explore the solution space rather than enumerate all possible "legal" placements of bulbs for a given puzzle.

I break down the approach to solving Akari puzzles into three phases: 1) place bulbs around all 4-squares, 2) place bulbs around all other numbered squares, and 3) place bulbs to cover any non-illuminated white square. Once the grid configuration (grid dimensions and locations of numbered and plain black squares) has been input, there is only one way to place bulbs around a 4-square (North-East-South-West). The second and third phases are then solved with backtracking.

Unlike the N-Queens problem, each 3-, 2-, and 1-square will have a different number of possible legal moves. There are four ways to position three bulbs around a 3-square: North-East-South, East-South-West, South-West-North, and West-North-East; six ways to position two bulbs around a 2-square: North-South, East-West, North-East, East-South, South-West, and West-North; and four ways to position one bulb around a 1-square: North, East, South, and West. When examining a potential move, the code first determines if the squares that will be covered by bulbs are open; i.e., a white square that is not illuminated by a previously placed bulb, not adjacent to a 0-square, and not adjacent to a number square that is already "filled." If the required squares are not all available, the move being considered is not possible (and will not lead to a legal solution), so another move will be checked or, if all possible moves have been tried, a previously placed bulb is in a square that is not part of the solution and the (recursive) code will return up the search tree to make other choices.

Once all numbered squares are legally covered (or left uncovered in the case of 0-squares), the third phase finds all remaining white squares that are not illuminated by a placed bulb and puts them into a list. The final solution(s) will either have a bulb in a given open white square or that open square will be illuminated by a bulb placed in some other open white square. This means there is a binary decision for each open white square on the list: try to find solutions with the bulb placed in the square and try to find solutions without a bulb in that square.

The parallelization of the recursive calls of the second and third phases is very straightforward. In the third phase, a new task can be created to look for solutions with a bulb placed on the proposed square (if such placement is legal) and a new task can be created to look for solutions that leave the proposed square open. For the second phase, each of the possible legal moves for numbered squares can spawn a task. In order to avoid race conditions, whenever a new task is to be spawned, I must make a copy of the current partial solution (grid configuration) — with all previously placed bulbs — to be used by the thread executing the task.

Related Reading


More Insights






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.
 


Video