Skip to content

Instantly share code, notes, and snippets.

@cafaxo
Last active March 29, 2021 00:25
Show Gist options
  • Save cafaxo/5c9bddf5d846b0b5896d083115d8eaec to your computer and use it in GitHub Desktop.
Save cafaxo/5c9bddf5d846b0b5896d083115d8eaec to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment