BridgesSolver

Player vs CPU implementation of Bridges(Simon Tatham)

Solver Algorithms

Greedy Algorithm

Goal : An solver that can just get pass the post of failure

Algorithm

Start
if visitedCountdfs(node) != # nodes
	ConnectionPhase	
else 
 SatisfactionPhase

Connection Phase

• Get the maximum end points
  • Connect them to the neighbors
    1. who are not connected currently to anyone
    2. The connect wont go over the bridge count required by the island and is not the neighbour of the current node

Satisfaction Phase

• Get the minimum node from the graph
  • Not satisfied already
• Connect it to its neighbor
  1. Connection wont go over their bridge count

Divide-and-Conquer (DAC) Algorithm (theory + what this project visualizes)

This repo also contains a DAC-style solver (selectable in the UI) that is meant to show how a divide-and-conquer approach can solve Hashiwokakero / Bridges.

Problem model (what we are solving)

• Nodes (islands) sit on a grid. Each island has a required degree (d(v)) (the number on the island).
• Edges (bridges) can only be drawn orthogonally (horizontal/vertical) to the next visible island in that direction.
• Between a pair of islands you can place 0, 1, or 2 bridges.
• Bridges must not cross and must not pass through an island.
• Final solution must satisfy:
  • Degree constraints: for every island (v), (\sum_{e \ni v} x_e = d(v)) where (x_e \in {0,1,2}).
  • Connectivity: all islands are in one connected component.

The key DAC idea: solve by “separators” (cuts) instead of guessing random edges

Divide-and-conquer works well when you can cut the board into two parts and only a small amount of information needs to “flow” across the cut.

For Bridges, that information is:

• How many bridges cross the cut at each possible crossing line (0/1/2).

So instead of guessing every edge everywhere, DAC guesses an interface assignment on the cut, then solves both halves consistently.

Vertical cut example (interface constraints)

Imagine a vertical cut at grid column (x = mid).

Some horizontal bridges might cross this cut. Each potential crossing happens on a specific row (y).

For each such row (y), define an interface variable:

• (c_y \in {0,1,2}) = how many bridges cross the cut on row (y).

Those (c_y) values become boundary constraints:

• Left subproblem must “send” exactly (c_y) bridges through its right boundary at row (y).
• Right subproblem must “receive” exactly (c_y) bridges through its left boundary at row (y).

Horizontal cuts are the same idea, but with columns instead of rows.

Full DAC solving loop (what a complete DAC solver would do)

At a region (R):

1. Divide:
   • Pick a cut line (vertical if region is wider, horizontal if taller).
   • Split (R) into (R_1) and (R_2).
2. Enumerate the interface:
   • Find all rows/cols where a bridge could cross that cut (line-of-sight exists).
   • Generate assignments where each crossing is 0/1/2 (the “interface”).
3. Conquer:
   • Recursively solve (R_1) with boundary constraints updated by the interface.
   • Recursively solve (R_2) with the matching boundary constraints.
4. Combine:
   • Merge edge sets from both halves + add the interface bridges themselves.
5. Validate / prune:
   • Degree feasibility checks inside subregions (don’t exceed required degree).
   • No-crossing checks.
   • At the top level (or sometimes during recursion), enforce global connectivity.
6. If any step fails, backtrack and try the next interface assignment.

This is the “real” DAC approach: the hard work is in making interface enumeration small and pruning aggressively so you don’t try (3^k) combinations blindly.

What DACSolver does in this project today

Our DACSolver currently has two distinct parts:

1. DAC splitting visualization (divide step)

• Each press of N shows the next split:
  • highlights islands in the current region
  • draws a rectangle around the region
  • draws the cut line
• Internally, the solver:
  • compresses world coordinates into grid indices (so cuts align with island columns/rows)
  • generates a queue of split steps by recursively partitioning the region

2. Bridge construction (making connections)

• After all split steps are shown, the solver computes bridges using a backtracking search over the legal neighbor edges:
  • chooses an unassigned candidate edge
  • tries counts 2 → 1 → 0
  • prunes when remaining degree cannot be satisfied
  • rejects any assignment that creates a crossing
  • finally checks that the graph is connected
• Once a satisfying assignment is found, it is applied one move per N press using EdgeSystem.createEdge(...) so you see bridges appear step-by-step.

So: the visualization is DAC-like (divide-and-conquer splitting), while the actual connection generation is currently done by a correct backtracking solver.

How to use it in the UI

• Select the solver in the dropdown: Greedy or DAC (visual).
• Press N:
  • Greedy: applies the next greedy move
  • DAC (visual): shows region splits first, then starts placing bridges

Where to look in code

• core/src/main/java/io/solvers/bridgeSolver/Solvers/DACSolver.java: split-step visualization + solving logic
• core/src/main/java/io/solvers/bridgeSolver/DebugLineComponent.java: debug line primitive for visualization
• core/src/main/java/io/solvers/bridgeSolver/RenderSystem.java: draws debug lines
• core/src/main/java/io/solvers/bridgeSolver/Main.java: solver dropdown + wiring N to the selected solver