This is a solver for the well known puzzle game Hashiwokakero.
The application reads the problem instance from stdin. It expects a number of spaces separated integers of which the first one describes the width and the second one the height of the grid to consider. It is then followed by width times height many integers, each specifying what occurs at the corresponding place on the grid. A zero denotes empty space while a positive integer specifies an island with that number on it.
10 15
3 0 3 0 3 0 3 0 2 0
0 3 0 5 0 3 0 4 0 2
3 0 0 0 2 0 3 0 0 0
0 2 0 0 0 0 0 1 0 0
4 0 0 6 0 0 4 0 0 2
0 1 0 0 0 4 0 2 0 0
1 0 0 0 0 0 1 0 0 2
0 4 0 4 0 6 0 0 1 0
2 0 0 0 0 0 0 3 0 3
0 3 0 0 1 0 0 0 0 0
4 0 0 4 0 5 0 4 0 3
0 0 1 0 0 0 0 0 0 0
0 0 0 5 0 0 4 0 2 0
3 0 3 0 0 0 0 0 0 0
0 1 0 3 0 1 0 0 0 3
The application first prints a textual representation of the solution. For each edge of the solution, the coordinates of the two end points are printed together with the number of bridges between the specified islands which is either 1 or 2. After that, a visual representation is printed as well, where + denotes single bridges between islands and # denotes double bridges. Finally, the overall runtime is printed. If there is no solution to the given problem, an appropriate message is printed.
(0, 0) <-> (2, 0): 1
(0, 0) <-> (0, 2): 2
(2, 0) <-> (4, 0): 2
(4, 0) <-> (6, 0): 1
(6, 0) <-> (8, 0): 2
(1, 1) <-> (3, 1): 1
(1, 1) <-> (1, 3): 2
(3, 1) <-> (5, 1): 2
(3, 1) <-> (3, 4): 2
(5, 1) <-> (7, 1): 1
(7, 1) <-> (9, 1): 2
(7, 1) <-> (7, 3): 1
(0, 2) <-> (0, 4): 1
(4, 2) <-> (6, 2): 2
(6, 2) <-> (6, 4): 1
(0, 4) <-> (3, 4): 2
(0, 4) <-> (0, 6): 1
(3, 4) <-> (6, 4): 1
(3, 4) <-> (3, 7): 1
(6, 4) <-> (9, 4): 2
(1, 5) <-> (1, 7): 1
(5, 5) <-> (7, 5): 2
(5, 5) <-> (5, 7): 2
(6, 6) <-> (9, 6): 1
(9, 6) <-> (9, 8): 1
(1, 7) <-> (3, 7): 1
(1, 7) <-> (1, 9): 2
(3, 7) <-> (5, 7): 2
(5, 7) <-> (8, 7): 1
(5, 7) <-> (5, 10): 1
(0, 8) <-> (0, 10): 2
(7, 8) <-> (9, 8): 1
(7, 8) <-> (7, 10): 2
(9, 8) <-> (9, 10): 1
(1, 9) <-> (4, 9): 1
(0, 10) <-> (3, 10): 1
(0, 10) <-> (0, 13): 1
(3, 10) <-> (5, 10): 2
(3, 10) <-> (3, 12): 1
(5, 10) <-> (7, 10): 2
(9, 10) <-> (9, 14): 2
(2, 11) <-> (2, 13): 1
(3, 12) <-> (6, 12): 2
(3, 12) <-> (3, 14): 2
(6, 12) <-> (8, 12): 2
(0, 13) <-> (2, 13): 2
(1, 14) <-> (3, 14): 1
(5, 14) <-> (9, 14): 1
3 + + + 3 # # # 3 + + + 3 # # # 2
#
# 3 + + + 5 # # # 3 + + + 4 # # # 2
# # # +
3 # # 2 # # # 3 +
+ # # + +
+ 2 # + 1
+ # +
4 # # # # # 6 + + + + + 4 # # # # # 2
+ +
+ 1 + 4 # # # 2
+ + + #
1 + + # 1 + + + + + 2
+ + # +
4 + + + 4 # # # 6 + + + + + 1 +
# + +
2 # + 3 + + + 3
# # + # +
# 3 + + + + + 1 + # +
# + # +
4 + + + + + 4 # # # 5 # # # 4 3
+ + #
+ 1 + #
+ + + #
+ + 5 # # # # # 4 # # # 2 #
+ + # #
3 # # # 3 # #
# #
1 + + + 3 1 + + + + + + + 3
runtime: 0.127s