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.