snake.jl

function count_snakes(n)
    c = 0

    for x in 1:n
        for y in 1:n
            c += count_snakes_from(n, x, y)
        end
    end

    return c
end

function count_snakes_from(n, x, y)
    grid = zeros(Int, n, n)

    # right = 1, up = 2, left = 3, down = 4
    x_diff = (1, 0, -1, 0)
    y_diff = (0, -1, 0, 1)

    stack = Int[]

    grid[x, y] = 1

    i = 1

    try_direction = 1

    c = 0

    while true
        # try the given direction
        x_try = x + x_diff[try_direction]
        y_try = y + y_diff[try_direction]

        if 1 <= x_try <= n && 1 <= y_try <= n && grid[x_try, y_try] == 0
            i_try = i < n ? i+1 : 1

            # incremental check of simplified sudoku rules (check only rows and columns)
            rules = true

            for pos in 1:n
                if grid[pos, y_try] == i_try || grid[x_try, pos] == i_try
                    rules = false
                    break
                end
            end

            if rules
                x = x_try
                y = y_try
                i = i_try
                grid[x, y] = i
                push!(stack, try_direction)
                try_direction = 1
                continue
            end
        end

        # failed to go the given direction
        if try_direction < 4
            try_direction += 1
            continue
        end

        if length(stack) == n*n-1
            # display(grid)
            c += 1
        end

        succ = false

        # go up the search tree
        while !isempty(stack)
            went_direction = pop!(stack)

            grid[x, y] = 0
            x -= x_diff[went_direction]
            y -= y_diff[went_direction]
            i = i > 1 ? i-1 : n

            if went_direction < 4
                try_direction = went_direction + 1
                succ = true
                break
            end
        end

        if !succ
            # we are done!
            return c
        end
    end
end