Please provide a Python Program

Specification

This project is based on a popular puzzle, variously known as "Hashiwokakero", "Hashi" or "Bridges". You will need to write a program to solve this puzzle, and provide a brief description of the algorithm and data structures you have used. The input to your program will be a rectangular array of numbers and dots, for example:

$\mathrm{.}1..\mathrm{.}6..\mathrm{.}7...\mathrm{.}4\mathrm{.}4\mathrm{.}2.$

$.\mathrm{.}4\mathrm{.}2.\mathrm{.}2..\mathrm{.}3\mathrm{.}8..\mathrm{.}6\mathrm{.}2$

$....\mathrm{.}2..............$

$5.$c$\mathrm{.}7..$a$.$a$.\mathrm{.}5\mathrm{.}6.\mathrm{.}8\mathrm{.}5$

$............\mathrm{.}2......$

$..\mathrm{.}5..\mathrm{.}9.$a$.\mathrm{.}8.$b$\mathrm{.}8\mathrm{.}4.$

$4\mathrm{.}5...............\mathrm{.}3$

$...\mathrm{.}2.\mathrm{.}4.\mathrm{.}1\mathrm{.}5..\mathrm{.}2...$

$\mathrm{.}2\mathrm{.}7\mathrm{.}4..\mathrm{.}7\mathrm{.}2.\mathrm{.}5..\mathrm{.}3.$

$...........\mathrm{.}4.\mathrm{.}3\mathrm{.}1\mathrm{.}2$

Each number represents an "island", while the dots represent the empty space $($water$)$ between the islands. Numbers larger than $9$ are indicated by $\text{'}$a$\text{'}(10),\text{'}$b$\text{'}(11)$ or $\text{'}$c$\text{'}(12).$ The aim is to connect all the islands with a network of bridges, satisfying these rules:

all bridges must run horizontally or vertically

bridges are not allowed to cross each other, or other islands

there can be no more than three bridges connecting any pair of islands

the total number of bridges connected to each island must be equal to the number on the island

For example, after reading the $10-$line input above, your program might produce this output:

$1---6$EEE$7====4=4=2$

$4-2"2"3$E$8$EEE$62$

# $|2"""$ # $"$

$5$EcE$7$EEaEa$==5"6$EE$8=5$

$"$ # $"$ # #$2$# $|$

$"$ #$5===9$Ea$--8=$bE$8$E$4|$

$4=5$# $"$ # $"$ # $"|3$

#$2==4$ #$1-5$ # $2|"$

$2=7=4===7=2"5===3"$

$4==3-12$

Note that single bridges are indicated by the characters $\text{'}-\text{'}$ or $\text{'}|\text{'},$ pairs of bridges by $\text{'}=\text{'}$ or $\text{'}"\text{'}$ and triples by $\text{'}$E$\text{'}$ or $\text{'}$#$\text{'},$ depending on whether they run horizontally or vertically. Water between bridges and islands is indicated by space characters $\text{'}\text{'}.$

In some cases, there may be many solutions, in which case your program should only print one solution. More details about the puzzle can be found on this Wikipedia page. Note, however, that our version allows up to $3$ bridges instead of $2$; also, we do not insist that the entire graph be connected.