Hashiwokakero

[1] It has also been published in English under the name Bridges or Chopsticks (based on a mistranslation: the hashi of the title, 橋, means bridge; hashi written with another character, 箸, means chopsticks).

It is common practice to cross off or fill in islands whose bridge quota has been reached.

Determining whether a Hashiwokakero puzzle has a solution is NP-complete, by a reduction from finding Hamiltonian cycles in integer-coordinate unit distance graphs.

[4] There is a solution using integer linear programming in the MathProg examples included in GLPK.

[5] A library of puzzles counting up to 400 islands as well as integer linear programming results are also reported.