// hashisolver/solver.go
package hashisolver

import (
	"bufio"
	"errors"
	"fmt"
	"io"
	"strings"
)

// Direction constants for bridge connections
const (
	DirectionUp    = 0
	DirectionDown  = 1
	DirectionLeft  = 2
	DirectionRight = 3
)

// Node represents an island in the puzzle
type Node struct {
	Value        int
	XPos         int
	YPos         int
	UpBridges    int
	DownBridges  int
	LeftBridges  int
	RightBridges int
	TotalBridges int

	// Neighbor nodes this one MAY connect to
	UpNeighbor    *Node
	DownNeighbor  *Node
	LeftNeighbor  *Node
	RightNeighbor *Node

	// Blocked directions
	UpBlocked    bool
	DownBlocked  bool
	LeftBlocked  bool
	RightBlocked bool
	NumBlocked   int

	// Used when traversing nodes to check for potential islands
	Visited bool
}

// Puzzle represents the entire hashiwokakero puzzle
type Puzzle struct {
	Board        [][]*Node
	Size         int
	BuiltBridges int
	FullBridges  int
}

// NewNode creates a new node with the given value and position
func NewNode(value, x, y int) *Node {
	return &Node{
		Value:        value,
		XPos:         x,
		YPos:         y,
		UpBridges:    0,
		DownBridges:  0,
		LeftBridges:  0,
		RightBridges: 0,
		TotalBridges: 0,
		UpBlocked:    false,
		DownBlocked:  false,
		LeftBlocked:  false,
		RightBlocked: false,
		NumBlocked:   0,
		Visited:      false,
	}
}

// GetNeighbor returns the neighbor in the specified direction
func (n *Node) GetNeighbor(direction int) *Node {
	switch direction {
	case DirectionUp:
		return n.UpNeighbor
	case DirectionDown:
		return n.DownNeighbor
	case DirectionLeft:
		return n.LeftNeighbor
	case DirectionRight:
		return n.RightNeighbor
	default:
		return nil
	}
}

// BridgesInDirection returns the number of bridges in the specified direction
func (n *Node) BridgesInDirection(direction int) int {
	switch direction {
	case DirectionUp:
		return n.UpBridges
	case DirectionDown:
		return n.DownBridges
	case DirectionLeft:
		return n.LeftBridges
	case DirectionRight:
		return n.RightBridges
	default:
		return -1
	}
}

// NumNeighbors returns the number of neighbors this node has
func (n *Node) NumNeighbors() int {
	count := 0
	if n.UpNeighbor != nil {
		count++
	}
	if n.DownNeighbor != nil {
		count++
	}
	if n.LeftNeighbor != nil {
		count++
	}
	if n.RightNeighbor != nil {
		count++
	}
	return count
}

// RemainingPossibleMoves calculates how many bridge connections are still possible
func (n *Node) RemainingPossibleMoves() int {
	moves := 2 * n.NumNeighbors()

	if n.UpNeighbor != nil {
		moves -= n.UpBridges
		if n.UpNeighbor.Value-n.UpNeighbor.TotalBridges == 1 && n.UpBridges == 0 {
			moves--
		} else if n.UpNeighbor.Value-n.UpNeighbor.TotalBridges == 0 && n.UpBridges == 1 {
			moves--
		}
	}

	if n.DownNeighbor != nil {
		moves -= n.DownBridges
		if n.DownNeighbor.Value-n.DownNeighbor.TotalBridges == 1 && n.DownBridges == 0 {
			moves--
		} else if n.DownNeighbor.Value-n.DownNeighbor.TotalBridges == 0 && n.DownBridges == 1 {
			moves--
		}
	}

	if n.LeftNeighbor != nil {
		moves -= n.LeftBridges
		if n.LeftNeighbor.Value-n.LeftNeighbor.TotalBridges == 1 && n.LeftBridges == 0 {
			moves--
		} else if n.LeftNeighbor.Value-n.LeftNeighbor.TotalBridges == 0 && n.LeftBridges == 1 {
			moves--
		}
	}

	if n.RightNeighbor != nil {
		moves -= n.RightBridges
		if n.RightNeighbor.Value-n.RightNeighbor.TotalBridges == 1 && n.RightBridges == 0 {
			moves--
		} else if n.RightNeighbor.Value-n.RightNeighbor.TotalBridges == 0 && n.RightBridges == 1 {
			moves--
		}
	}

	return moves
}

// TotalPossibleMoves calculates the total possible moves (not accounting for nodes with only one possible connection)
func (n *Node) TotalPossibleMoves() int {
	moves := 2 * n.NumNeighbors()

	if n.UpNeighbor != nil {
		moves -= n.UpBridges
		if n.UpBridges == 1 && n.UpNeighbor.Value == n.UpNeighbor.TotalBridges {
			moves--
		}
	}

	if n.DownNeighbor != nil {
		moves -= n.DownBridges
		if n.DownBridges == 1 && n.DownNeighbor.Value == n.DownNeighbor.TotalBridges {
			moves--
		}
	}

	if n.LeftNeighbor != nil {
		moves -= n.LeftBridges
		if n.LeftBridges == 1 && n.LeftNeighbor.Value == n.LeftNeighbor.TotalBridges {
			moves--
		}
	}

	if n.RightNeighbor != nil {
		moves -= n.RightBridges
		if n.RightBridges == 1 && n.RightNeighbor.Value == n.RightNeighbor.TotalBridges {
			moves--
		}
	}

	return moves
}

// UnblockedNode returns the direction of the single unblocked node (assumes only one exists)
func (n *Node) UnblockedNode() int {
	if !n.UpBlocked {
		return DirectionUp
	} else if !n.DownBlocked {
		return DirectionDown
	} else if !n.LeftBlocked {
		return DirectionLeft
	} else if !n.RightBlocked {
		return DirectionRight
	}

	return -1 // Error case
}

// UnblockedNodes returns a slice of all unblocked directions
func (n *Node) UnblockedNodes() []int {
	result := []int{}
	if !n.UpBlocked {
		result = append(result, DirectionUp)
	}
	if !n.DownBlocked {
		result = append(result, DirectionDown)
	}
	if !n.LeftBlocked {
		result = append(result, DirectionLeft)
	}
	if !n.RightBlocked {
		result = append(result, DirectionRight)
	}
	return result
}

// NodeFilled blocks all directions of this node (used when the node is filled with all its bridges)
func (n *Node) NodeFilled() {
	n.UpBlocked = true
	n.DownBlocked = true
	n.LeftBlocked = true
	n.RightBlocked = true
	n.NumBlocked = 4

	// Also blocks the corresponding directions of neighbor nodes if they aren't already blocked
	if n.UpNeighbor != nil && !n.UpNeighbor.DownBlocked {
		n.UpNeighbor.DownBlocked = true
		n.UpNeighbor.NumBlocked++
	}

	if n.DownNeighbor != nil && !n.DownNeighbor.UpBlocked {
		n.DownNeighbor.UpBlocked = true
		n.DownNeighbor.NumBlocked++
	}

	if n.LeftNeighbor != nil && !n.LeftNeighbor.RightBlocked {
		n.LeftNeighbor.RightBlocked = true
		n.LeftNeighbor.NumBlocked++
	}

	if n.RightNeighbor != nil && !n.RightNeighbor.LeftBlocked {
		n.RightNeighbor.LeftBlocked = true
		n.RightNeighbor.NumBlocked++
	}
}

// DirectionBlocked blocks the connection between this node and the neighbor node in the given direction
func (n *Node) DirectionBlocked(direction int) {
	switch direction {
	case DirectionUp:
		if !n.UpBlocked {
			n.UpBlocked = true
			n.NumBlocked++
		}
		if n.UpNeighbor != nil && !n.UpNeighbor.DownBlocked {
			n.UpNeighbor.DownBlocked = true
			n.UpNeighbor.NumBlocked++
		}

	case DirectionDown:
		if !n.DownBlocked {
			n.DownBlocked = true
			n.NumBlocked++
		}
		if n.DownNeighbor != nil && !n.DownNeighbor.UpBlocked {
			n.DownNeighbor.UpBlocked = true
			n.DownNeighbor.NumBlocked++
		}

	case DirectionLeft:
		if !n.LeftBlocked {
			n.LeftBlocked = true
			n.NumBlocked++
		}
		if n.LeftNeighbor != nil && !n.LeftNeighbor.RightBlocked {
			n.LeftNeighbor.RightBlocked = true
			n.LeftNeighbor.NumBlocked++
		}

	case DirectionRight:
		if !n.RightBlocked {
			n.RightBlocked = true
			n.NumBlocked++
		}
		if n.RightNeighbor != nil && !n.RightNeighbor.LeftBlocked {
			n.RightNeighbor.LeftBlocked = true
			n.RightNeighbor.NumBlocked++
		}
	}
}

// BlockCheck checks whether bridges need to be blocked in any direction
func (n *Node) BlockCheck() {
	// If node is filled up with bridges, block all directions
	if n.Value == n.TotalBridges {
		n.NodeFilled()
	}

	// 2 bridges is maximum in any direction, so block that direction
	if n.UpBridges == 2 {
		n.DirectionBlocked(DirectionUp)
	}
	if n.UpNeighbor != nil && n.UpNeighbor.TotalBridges == n.UpNeighbor.Value {
		n.UpNeighbor.NodeFilled()
	}

	if n.DownBridges == 2 {
		n.DirectionBlocked(DirectionDown)
	}
	if n.DownNeighbor != nil && n.DownNeighbor.TotalBridges == n.DownNeighbor.Value {
		n.DownNeighbor.NodeFilled()
	}

	if n.LeftBridges == 2 {
		n.DirectionBlocked(DirectionLeft)
	}
	if n.LeftNeighbor != nil && n.LeftNeighbor.TotalBridges == n.LeftNeighbor.Value {
		n.LeftNeighbor.NodeFilled()
	}

	if n.RightBridges == 2 {
		n.DirectionBlocked(DirectionRight)
	}
	if n.RightNeighbor != nil && n.RightNeighbor.TotalBridges == n.RightNeighbor.Value {
		n.RightNeighbor.NodeFilled()
	}
}

// ConnectNodes connects two nodes with a bridge in the specified direction
func ConnectNodes(puzzle *Puzzle, node *Node, neighbor *Node, direction int, isSpeculative bool) {
	if !isSpeculative {
		puzzle.BuiltBridges++
	}

	node.TotalBridges++
	neighbor.TotalBridges++

	switch direction {
	case DirectionUp:
		node.UpBridges++
		neighbor.DownBridges++

		// Mark the bridge in the board
		distance := node.YPos - neighbor.YPos
		for i := 1; i < distance; i++ {
			if node.UpBridges == 1 {
				puzzle.Board[node.YPos-i][node.XPos].Value = -1 // Vertical single bridge
			} else {
				puzzle.Board[node.YPos-i][node.XPos].Value = -2 // Vertical double bridge
			}
		}

	case DirectionDown:
		node.DownBridges++
		neighbor.UpBridges++

		// Mark the bridge in the board
		distance := neighbor.YPos - node.YPos
		for i := 1; i < distance; i++ {
			if node.DownBridges == 1 {
				puzzle.Board[node.YPos+i][node.XPos].Value = -1 // Vertical single bridge
			} else {
				puzzle.Board[node.YPos+i][node.XPos].Value = -2 // Vertical double bridge
			}
		}

	case DirectionLeft:
		node.LeftBridges++
		neighbor.RightBridges++

		// Mark the bridge in the board
		distance := node.XPos - neighbor.XPos
		for i := 1; i < distance; i++ {
			if node.LeftBridges == 1 {
				puzzle.Board[node.YPos][node.XPos-i].Value = -3 // Horizontal single bridge
			} else {
				puzzle.Board[node.YPos][node.XPos-i].Value = -4 // Horizontal double bridge
			}
		}

	case DirectionRight:
		node.RightBridges++
		neighbor.LeftBridges++

		// Mark the bridge in the board
		distance := neighbor.XPos - node.XPos
		for i := 1; i < distance; i++ {
			if node.RightBridges == 1 {
				puzzle.Board[node.YPos][node.XPos+i].Value = -3 // Horizontal single bridge
			} else {
				puzzle.Board[node.YPos][node.XPos+i].Value = -4 // Horizontal double bridge
			}
		}
	}

	// Check for bridge conflicts and node filling
	node.BlockCheck()
	neighbor.BlockCheck()
}

// BridgeCheck checks for bridges that would block one edge of the node
func BridgeCheck(node *Node) {
	// This function implements the bridge checking logic from the C++ implementation
	// For each direction, if that's the only direction with a possible bridge, connect it

	if node.NumBlocked == 3 && node.Value-node.TotalBridges > 0 {
		direction := node.UnblockedNode()
		neighbor := node.GetNeighbor(direction)

		if neighbor != nil && neighbor.Value-neighbor.TotalBridges > 0 {
			// This is an obvious move - only one direction is available
			return
		}
	}
}

// CheckForIsland checks if adding a bridge would create an isolated island
func CheckForIsland(puzzle *Puzzle, node *Node, direction int, bridgeCount int) bool {
	// Reset visited flags
	for i := 0; i < puzzle.Size; i++ {
		for j := 0; j < puzzle.Size; j++ {
			if puzzle.Board[i][j].Value > 0 {
				puzzle.Board[i][j].Visited = false
			}
		}
	}

	// Temporarily block the direction we're testing
	oldBlocked := false
	switch direction {
	case DirectionUp:
		oldBlocked = node.UpBlocked
		node.UpBlocked = true
	case DirectionDown:
		oldBlocked = node.DownBlocked
		node.DownBlocked = true
	case DirectionLeft:
		oldBlocked = node.LeftBlocked
		node.LeftBlocked = true
	case DirectionRight:
		oldBlocked = node.RightBlocked
		node.RightBlocked = true
	}

	// Mark the current node as visited
	node.Visited = true

	// Start a depth-first search from this node
	connected := true
	for i := 0; i < puzzle.Size && connected; i++ {
		for j := 0; j < puzzle.Size && connected; j++ {
			if puzzle.Board[i][j].Value > 0 && !puzzle.Board[i][j].Visited {
				// Found an unvisited node, check if it's reachable
				connected = CheckNodeString(puzzle.Board[i][j])
				if !connected {
					// We found an island, so we must add a bridge in the tested direction
					// Restore the original blocked state
					switch direction {
					case DirectionUp:
						node.UpBlocked = oldBlocked
					case DirectionDown:
						node.DownBlocked = oldBlocked
					case DirectionLeft:
						node.LeftBlocked = oldBlocked
					case DirectionRight:
						node.RightBlocked = oldBlocked
					}

					// Add the bridge
					ConnectNodes(puzzle, node, node.GetNeighbor(direction), direction, false)
					return true
				}
			}
		}
	}

	// Restore the original blocked state
	switch direction {
	case DirectionUp:
		node.UpBlocked = oldBlocked
	case DirectionDown:
		node.DownBlocked = oldBlocked
	case DirectionLeft:
		node.LeftBlocked = oldBlocked
	case DirectionRight:
		node.RightBlocked = oldBlocked
	}

	return false
}

// CheckNodeString performs a DFS to mark all nodes that are connected
func CheckNodeString(node *Node) bool {
	if node == nil || node.Visited {
		return true
	}

	node.Visited = true

	// Check all four directions
	if !node.UpBlocked && node.UpNeighbor != nil {
		CheckNodeString(node.UpNeighbor)
	}

	if !node.DownBlocked && node.DownNeighbor != nil {
		CheckNodeString(node.DownNeighbor)
	}

	if !node.LeftBlocked && node.LeftNeighbor != nil {
		CheckNodeString(node.LeftNeighbor)
	}

	if !node.RightBlocked && node.RightNeighbor != nil {
		CheckNodeString(node.RightNeighbor)
	}

	return true
}

// Clone creates a deep copy of a puzzle
func (p *Puzzle) Clone() *Puzzle {
	newPuzzle := &Puzzle{
		Size:         p.Size,
		Board:        make([][]*Node, p.Size),
		BuiltBridges: p.BuiltBridges,
		FullBridges:  p.FullBridges,
	}

	// Clone the board
	for i := 0; i < p.Size; i++ {
		newPuzzle.Board[i] = make([]*Node, p.Size)
		for j := 0; j < p.Size; j++ {
			oldNode := p.Board[i][j]
			newNode := NewNode(oldNode.Value, oldNode.XPos, oldNode.YPos)

			// Copy node state
			newNode.UpBridges = oldNode.UpBridges
			newNode.DownBridges = oldNode.DownBridges
			newNode.LeftBridges = oldNode.LeftBridges
			newNode.RightBridges = oldNode.RightBridges
			newNode.TotalBridges = oldNode.TotalBridges

			newNode.UpBlocked = oldNode.UpBlocked
			newNode.DownBlocked = oldNode.DownBlocked
			newNode.LeftBlocked = oldNode.LeftBlocked
			newNode.RightBlocked = oldNode.RightBlocked
			newNode.NumBlocked = oldNode.NumBlocked

			newPuzzle.Board[i][j] = newNode
		}
	}

	// Reconnect neighbors
	for i := 0; i < p.Size; i++ {
		for j := 0; j < p.Size; j++ {
			oldNode := p.Board[i][j]
			newNode := newPuzzle.Board[i][j]

			if oldNode.UpNeighbor != nil {
				newNode.UpNeighbor = newPuzzle.Board[oldNode.UpNeighbor.YPos][oldNode.UpNeighbor.XPos]
			}

			if oldNode.DownNeighbor != nil {
				newNode.DownNeighbor = newPuzzle.Board[oldNode.DownNeighbor.YPos][oldNode.DownNeighbor.XPos]
			}

			if oldNode.LeftNeighbor != nil {
				newNode.LeftNeighbor = newPuzzle.Board[oldNode.LeftNeighbor.YPos][oldNode.LeftNeighbor.XPos]
			}

			if oldNode.RightNeighbor != nil {
				newNode.RightNeighbor = newPuzzle.Board[oldNode.RightNeighbor.YPos][oldNode.RightNeighbor.XPos]
			}
		}
	}

	return newPuzzle
}

// IsComplete checks if the puzzle is completely solved
func (p *Puzzle) IsComplete() bool {
	// Check if all nodes have their required number of bridges
	for i := 0; i < p.Size; i++ {
		for j := 0; j < p.Size; j++ {
			node := p.Board[i][j]
			if node.Value > 0 && node.Value != node.TotalBridges {
				return false
			}
		}
	}

	// Check if all islands are connected
	var startNode *Node

	// Find the first node
	for i := 0; i < p.Size && startNode == nil; i++ {
		for j := 0; j < p.Size && startNode == nil; j++ {
			if p.Board[i][j].Value > 0 {
				startNode = p.Board[i][j]
			}
		}
	}

	if startNode == nil {
		return true // Empty puzzle
	}

	// Reset visited flags
	for i := 0; i < p.Size; i++ {
		for j := 0; j < p.Size; j++ {
			if p.Board[i][j].Value > 0 {
				p.Board[i][j].Visited = false
			}
		}
	}

	// Start a DFS from the first node
	CheckNodeString(startNode)

	// Check if all nodes were visited
	for i := 0; i < p.Size; i++ {
		for j := 0; j < p.Size; j++ {
			if p.Board[i][j].Value > 0 && !p.Board[i][j].Visited {
				return false // Disconnected island
			}
		}
	}

	return true
}

// FindCandidateNode finds a node with the most constrained but unresolved connections
func (p *Puzzle) FindCandidateNode() *Node {
	var bestNode *Node
	bestScore := -1

	for i := 0; i < p.Size; i++ {
		for j := 0; j < p.Size; j++ {
			node := p.Board[i][j]

			if node.Value <= 0 || node.Value == node.TotalBridges {
				continue // Skip empty or satisfied nodes
			}

			// Calculate a score based on how constrained this node is
			remainingBridges := node.Value - node.TotalBridges
			unblocked := node.UnblockedNodes()

			if len(unblocked) == 0 {
				continue // Skip fully blocked nodes
			}

			// Score is higher for nodes with fewer open directions but more remaining bridges
			score := remainingBridges*10 + (4 - len(unblocked))

			if score > bestScore {
				bestScore = score
				bestNode = node
			}
		}
	}

	return bestNode
}

// AttemptSpeculativeSolve attempts to solve the puzzle using speculative moves and backtracking
func AttemptSpeculativeSolve(puzzle *Puzzle, debug bool) (*Puzzle, error) {
	// Try to solve using logic first
	movesFound := true
	for movesFound {
		movesFound = false

		// Look at every node
		for i := 0; i < puzzle.Size; i++ {
			for j := 0; j < puzzle.Size; j++ {
				node := puzzle.Board[i][j]

				// Skip empty spaces or already satisfied nodes
				if node.Value <= 0 || node.TotalBridges == node.Value {
					continue
				}

				// Check for logical errors
				if node.NumBlocked == 4 && node.TotalBridges < node.Value {
					if debug {
						fmt.Println("Logical error - node blocked in all directions but still needs bridges")
					}
					return puzzle, errors.New("logical error - node blocked in all directions")
				}

				// Check for bridges that would block one edge of the node
				BridgeCheck(node)

				// If 3 directions are blocked, connect to the remaining one
				if node.NumBlocked == 3 && node.TotalBridges < node.Value {
					direction := node.UnblockedNode()
					neighbor := node.GetNeighbor(direction)

					if neighbor != nil {
						ConnectNodes(puzzle, node, neighbor, direction, false)

						// Make a double bridge if necessary
						if node.Value == node.TotalBridges+1 {
							ConnectNodes(puzzle, node, neighbor, direction, false)
						}

						movesFound = true
					}
				}

				// If remaining value equals total possible moves, all bridges must be fully connected
				if node.Value-node.TotalBridges == node.TotalPossibleMoves() {
					unblocked := node.UnblockedNodes()
					for _, dir := range unblocked {
						neighbor := node.GetNeighbor(dir)

						if neighbor == nil {
							continue
						}

						// Don't add a double bridge to a 1 or a node with remaining value of 1
						if node.BridgesInDirection(dir) == 0 && neighbor.Value-neighbor.TotalBridges > 1 {
							ConnectNodes(puzzle, node, neighbor, dir, false)
							ConnectNodes(puzzle, node, neighbor, dir, false)
						} else {
							ConnectNodes(puzzle, node, neighbor, dir, false)
						}
					}
					movesFound = true
				}

				// If remaining value equals remaining possible moves - 1
				// All edges must have at least one bridge
				if node.Value-node.TotalBridges == node.TotalPossibleMoves()-1 {
					unblocked := node.UnblockedNodes()
					for _, dir := range unblocked {
						// Check if any bridges already exist in that direction
						// If not, connect one
						if node.BridgesInDirection(dir) < 1 {
							neighbor := node.GetNeighbor(dir)
							if neighbor != nil {
								ConnectNodes(puzzle, node, neighbor, dir, false)
								movesFound = true
							}
						}
					}
				}

				// Check if adding a bridge in any direction would create an island
				unblocked := node.UnblockedNodes()
				for _, dir := range unblocked {
					if CheckForIsland(puzzle, node, dir, 1) {
						movesFound = true
					}
				}

				// Check the island condition for double bridges
				if node.NumBlocked == 2 && node.Value-node.TotalBridges == 2 {
					unblocked := node.UnblockedNodes()
					if len(unblocked) == 2 { // Make sure we have exactly 2 unblocked directions
						for k, dir := range unblocked {
							neighbor := node.GetNeighbor(dir)
							if neighbor == nil {
								continue
							}

							if neighbor.Value >= 2 && neighbor.TotalBridges == 0 {
								if CheckForIsland(puzzle, node, dir, 2) {
									movesFound = true
									// Add a bridge in the other direction
									var otherDir int
									if k == 0 {
										otherDir = unblocked[1]
									} else {
										otherDir = unblocked[0]
									}
									otherNeighbor := node.GetNeighbor(otherDir)
									if otherNeighbor != nil {
										ConnectNodes(puzzle, node, otherNeighbor, otherDir, false)
									}
								}
							}
						}
					}
				}

				// If a node has two unblocked edges and one is not enough to satisfy it
				if node.NumBlocked == 2 && node.Value-node.TotalBridges >= 2 {
					unblocked := node.UnblockedNodes()
					if len(unblocked) == 2 { // Make sure we have exactly 2 unblocked directions
						for k, dir := range unblocked {
							neighbor := node.GetNeighbor(dir)
							if neighbor == nil {
								continue
							}

							if neighbor.Value-neighbor.TotalBridges == 1 {
								movesFound = true

								// Connect to the other direction
								var otherDir int
								if k == 0 {
									otherDir = unblocked[1]
								} else {
									otherDir = unblocked[0]
								}
								otherNeighbor := node.GetNeighbor(otherDir)
								if otherNeighbor != nil {
									ConnectNodes(puzzle, node, otherNeighbor, otherDir, false)
								}
							}
						}
					}
				}
			}
		}

		if debug && movesFound {
			fmt.Println("Found moves in this iteration, continuing...")
		}
	}

	// Check if the puzzle is completely solved using just logic
	if puzzle.IsComplete() {
		if debug {
			fmt.Printf("Solution complete: %d/%d bridges placed\n", puzzle.BuiltBridges, puzzle.FullBridges/2)
		}
		return puzzle, nil
	}

	// If we get here, we need to use speculation
	if debug {
		fmt.Println("Using speculative solving...")
	}

	// Find a good candidate node for speculation
	candidateNode := puzzle.FindCandidateNode()
	if candidateNode == nil {
		return puzzle, errors.New("no candidate node found for speculation")
	}

	// Try each possible direction
	unblocked := candidateNode.UnblockedNodes()
	for _, dir := range unblocked {
		neighbor := candidateNode.GetNeighbor(dir)
		if neighbor == nil {
			continue
		}

		// Try adding a single bridge
		if debug {
			fmt.Printf("Trying a single bridge from (%d,%d) in direction %d\n",
				candidateNode.YPos, candidateNode.XPos, dir)
		}

		// Create a clone for speculative solving
		speculativePuzzle := puzzle.Clone()
		speculativeNode := speculativePuzzle.Board[candidateNode.YPos][candidateNode.XPos]
		speculativeNeighbor := speculativePuzzle.Board[neighbor.YPos][neighbor.XPos]

		// Add a single bridge
		ConnectNodes(speculativePuzzle, speculativeNode, speculativeNeighbor, dir, true)

		// Recursively attempt to solve
		newPuzzle, err := AttemptSpeculativeSolve(speculativePuzzle, debug)
		if err == nil && newPuzzle.IsComplete() {
			return newPuzzle, nil
		}

		// If we can add a double bridge, try that too
		if candidateNode.Value-candidateNode.TotalBridges >= 2 &&
			neighbor.Value-neighbor.TotalBridges >= 2 {

			if debug {
				fmt.Printf("Trying a double bridge from (%d,%d) in direction %d\n",
					candidateNode.YPos, candidateNode.XPos, dir)
			}

			// Create another clone for double bridge speculation
			speculativePuzzle2 := puzzle.Clone()
			speculativeNode2 := speculativePuzzle2.Board[candidateNode.YPos][candidateNode.XPos]
			speculativeNeighbor2 := speculativePuzzle2.Board[neighbor.YPos][neighbor.XPos]

			// Add two bridges
			ConnectNodes(speculativePuzzle2, speculativeNode2, speculativeNeighbor2, dir, true)
			ConnectNodes(speculativePuzzle2, speculativeNode2, speculativeNeighbor2, dir, true)

			// Recursively attempt to solve
			newPuzzle2, err2 := AttemptSpeculativeSolve(speculativePuzzle2, debug)
			if err2 == nil && newPuzzle2.IsComplete() {
				return newPuzzle2, nil
			}
		}

		// Try blocking this direction
		if debug {
			fmt.Printf("Trying blocking direction %d from (%d,%d)\n",
				dir, candidateNode.YPos, candidateNode.XPos)
		}

		// Create a clone for blocking speculation
		speculativePuzzle3 := puzzle.Clone()
		speculativeNode3 := speculativePuzzle3.Board[candidateNode.YPos][candidateNode.XPos]

		// Block the direction
		speculativeNode3.DirectionBlocked(dir)

		// Recursively attempt to solve
		newPuzzle3, err3 := AttemptSpeculativeSolve(speculativePuzzle3, debug)
		if err3 == nil && newPuzzle3.IsComplete() {
			return newPuzzle3, nil
		}
	}

	// If we've tried all possibilities and none worked, there's no solution
	return puzzle, errors.New("no solution found with speculation")
}

// Solve attempts to solve the hashiwokakero puzzle from the input reader
func Solve(input io.Reader, debug bool) (*Puzzle, error) {
	scanner := bufio.NewScanner(input)

	// Read the puzzle from the input
	lines := []string{}
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		if len(line) > 0 {
			lines = append(lines, line)
		}
	}

	if err := scanner.Err(); err != nil {
		return nil, fmt.Errorf("error reading input: %v", err)
	}

	if len(lines) == 0 {
		return nil, errors.New("no input provided")
	}

	// Determine board size - equal to the number of lines
	boardSize := len(lines)

	if debug {
		fmt.Printf("Board size: %dx%d\n", boardSize, boardSize)
	}

	// Initialize the puzzle
	puzzle := &Puzzle{
		Size:         boardSize,
		Board:        make([][]*Node, boardSize),
		BuiltBridges: 0,
		FullBridges:  0,
	}

	// Parse each line of the puzzle
	for i, line := range lines {
		puzzle.Board[i] = make([]*Node, boardSize)

		for j, char := range line {
			if j >= boardSize {
				break
			}

			var value int
			if char == '.' {
				value = 0
			} else if char >= '1' && char <= '9' {
				value = int(char - '0')
				puzzle.FullBridges += value
			} else {
				// If it's not a number or a dot, assume it's empty space
				value = 0
			}

			puzzle.Board[i][j] = NewNode(value, j, i)
		}
	}

	// Find neighbors for each node
	for i := 0; i < boardSize; i++ {
		for j := 0; j < boardSize; j++ {
			if puzzle.Board[i][j].Value <= 0 {
				continue
			}

			// Find right neighbor
			for k := j + 1; k < boardSize; k++ {
				if puzzle.Board[i][k].Value > 0 {
					puzzle.Board[i][j].RightNeighbor = puzzle.Board[i][k]
					break
				}
			}

			// Find left neighbor
			for k := j - 1; k >= 0; k-- {
				if puzzle.Board[i][k].Value > 0 {
					puzzle.Board[i][j].LeftNeighbor = puzzle.Board[i][k]
					break
				}
			}

			// Find down neighbor
			for k := i + 1; k < boardSize; k++ {
				if puzzle.Board[k][j].Value > 0 {
					puzzle.Board[i][j].DownNeighbor = puzzle.Board[k][j]
					break
				}
			}

			// Find up neighbor
			for k := i - 1; k >= 0; k-- {
				if puzzle.Board[k][j].Value > 0 {
					puzzle.Board[i][j].UpNeighbor = puzzle.Board[k][j]
					break
				}
			}
		}
	}

	// Set up initial blockages
	for i := 0; i < boardSize; i++ {
		for j := 0; j < boardSize; j++ {
			if puzzle.Board[i][j].Value <= 0 {
				continue
			}

			// Assign obvious blockages - edge nodes and a 1 connecting to a 1
			if puzzle.Board[i][j].LeftNeighbor == nil ||
				(puzzle.Board[i][j].Value == 1 && puzzle.Board[i][j].LeftNeighbor != nil && puzzle.Board[i][j].LeftNeighbor.Value == 1) {
				puzzle.Board[i][j].LeftBlocked = true
				puzzle.Board[i][j].NumBlocked++
			}

			if puzzle.Board[i][j].RightNeighbor == nil ||
				(puzzle.Board[i][j].Value == 1 && puzzle.Board[i][j].RightNeighbor != nil && puzzle.Board[i][j].RightNeighbor.Value == 1) {
				puzzle.Board[i][j].RightBlocked = true
				puzzle.Board[i][j].NumBlocked++
			}

			if puzzle.Board[i][j].UpNeighbor == nil ||
				(puzzle.Board[i][j].Value == 1 && puzzle.Board[i][j].UpNeighbor != nil && puzzle.Board[i][j].UpNeighbor.Value == 1) {
				puzzle.Board[i][j].UpBlocked = true
				puzzle.Board[i][j].NumBlocked++
			}

			if puzzle.Board[i][j].DownNeighbor == nil ||
				(puzzle.Board[i][j].Value == 1 && puzzle.Board[i][j].DownNeighbor != nil && puzzle.Board[i][j].DownNeighbor.Value == 1) {
				puzzle.Board[i][j].DownBlocked = true
				puzzle.Board[i][j].NumBlocked++
			}
		}
	}

	// Solve the puzzle using the enhanced solver with speculation
	return AttemptSpeculativeSolve(puzzle, debug)
}

// PrintMap prints the solved puzzle to stdout
func PrintMap(puzzle *Puzzle) {
	for i := 0; i < puzzle.Size; i++ {
		for j := 0; j < puzzle.Size; j++ {
			node := puzzle.Board[i][j]

			switch node.Value {
			case 0:
				fmt.Print(" ")
			case -1:
				fmt.Print("|") // Vertical single bridge
			case -2:
				fmt.Print("\"") // Vertical double bridge
			case -3:
				fmt.Print("-") // Horizontal single bridge
			case -4:
				fmt.Print("=") // Horizontal double bridge
			default:
				if node.Value > 0 {
					fmt.Print(node.Value)
				} else {
					fmt.Print(" ") // Unknown value
				}
			}
		}
		fmt.Println()
	}
}