How to find the Longest Snake in a Matrix

Question

Imagine we have a snake contained in a matrix that is matrix[a][b]: it is a tall and b wide. Cells in the matrix can be considered neighbors if they are directly, above, below, or to the left or right of another cell. Diagonal cells are not neighbors. The snake within the matrix must be continuous and its length is calculated by the number of cells it occupies. The snake is 1 cell wide and it can occupy any cells within the matrix but cannot leave the matrix. The snake can make 90 degree turns within the matrix but it cannot touch itself. What this means is that each cell within the snake must have exactly two neighbors, while the head the tail must have only 1 neighbor.

In the example, the snake is in a blue, 3 by 9 matrix.

An invalid snake would look like this: The red circle highlights the location that the snake touches itself.

A valid snake would look like this:

This snake is 19 cells long.

The snake doesn't need to start on the corners. In some cases, it results in a longer snake:

This snake is 20 cells long.

The question is, what is length of a longest snake found within any given matrix[a][b]? Is there an graph traversal algorithm to find the length? Can we find the length using a formula without traversing through the graph?

We tried to brute force this problem but it seems like the solution is inefficient. We are interested in whether there is a mathematical formula or a known algorithm to solve this problem. Any links to papers or articles on this topic would be helpful!

Answer 1

I haven't thoroughly searched the internet (example article after quick scan; other article). So I can't tell if there is a widely known algorithm for this question.

The following MiniZinc constraint programming model also arrives at length 20 for the given example.

include "globals.mzn";

%  problem dimensions
int: rows = 3;
int: cols = 9;
set of int: Rows = 1..rows;
set of int: Cols = 1..cols;

%  crude upper bound for snake length
%  it would speed up search to lower this bound
int: len = rows * cols;
set of int: Len = 1..len;

%  a cell with true value belongs to a snake
array[Rows, Cols] of var bool: cells;

%  row/col values of the snake
%  entries beyond snake end are 0
array[Len] of var 0..rows: snake_row;
array[Len] of var 0..cols: snake_col;
var Len: snake_len;

function var bool: has_neighbour(int: row, int: col, int: dRow, int: dCol) =
  ((row + dRow) in Rows) /\ ((col + dCol) in Cols) /\ cells[row + dRow, col + dCol];

function var 0..4: no_of_neighbours(Rows: row, Cols: col) =
  (has_neighbour(row, col, -1, 0) +
   has_neighbour(row, col, +1, 0) +
   has_neighbour(row, col, 0, -1) +
   has_neighbour(row, col, 0, +1));
     
function var bool: one_apart(var int: a, var int: b) =
  (a - b) in {-1, 1};
  
%  a snake cell can have one or two neighbors 
%  (this disallows snakes with length 1)
constraint forall(row in Rows, col in Cols) (
  (not cells[row, col]) \/
  (2 >= no_of_neighbours(row, col))
);

%  there must be exactly one head and one tail
constraint 2 == sum(row in Rows, col in Cols) (
   cells[row, col] /\
   (1 == no_of_neighbours(row, col))
);

%  row/col values beyond the snake are 0
constraint forall(x in Len) (
  ((snake_row[x] == 0) == (x > snake_len)) /\
  ((snake_col[x] == 0) == (x > snake_len))
);

%  adjacent snake cells are neighbours
constraint forall(x in Len) (
  (x >= snake_len) \/
  (cells[snake_row[x], snake_col[x]] /\
  (one_apart(snake_row[x], snake_row[x+1]) !=
   one_apart(snake_col[x], snake_col[x+1])) /\
   ((snake_row[x] == snake_row[x+1]) != 
    (snake_col[x] == snake_col[x+1])))
);

%  every true cell must be part of the snake
constraint forall(row in Rows, col in Cols) (
  cells[row, col] ==
  exists([(snake_row[x] == row) /\ (snake_col[x] == col) | x in Len])
);

%  all non-null cells of the snake have to be different
%  we compare the cell numbers
constraint 
  all_different_except_0([snake_row[x] * cols + snake_col[x] | x in Len]);

solve maximize snake_len;

function string: ite(bool: cond, string: sYes, string: sNo) =
  if cond then sYes else sNo endif;
  
output 
  ["length \(snake_len)"] ++
  [ ite(col == 1, "\n", "") ++ 
    ite(fix(cells[row, col]), "X ", "  ") 
  | row in Rows, col in Cols ] ++
  ["\n"] 
  % ++ [ ite(x <= fix(snake_len), "\(fix(snake_row[x]));\(fix(snake_col[x])) ", "") | x in Len ];
         
        

Output:

length 20
X X X X X   X X X 
X         X X   X 
X X X X X X   X X 

Output for 9x6 example:

length 36
X X X X X   
X       X X 
X X X X   X 
      X   X 
X X X   X X 
X   X   X   
X   X   X X 
X   X X   X 
X X   X X X 

Output for 6x9 example (intermediate solution after 90s):

length 36
X X X   X X X X X 
X   X   X       X 
X   X   X X X X   
X   X X       X X 
X       X X X   X 
X X X X X   X X X 

Answer 2

When the height ( H ) of the matrix is a multiple of 6 and the width ( W ) is greater than 3

1. Start snake in top right and move along top row to top left
2. Move down 3
3. Move along row from left to right
4. Move down 3
5. Move along row from right to left
6. Repeat steps 2 to 5 until bottom row reached
7. Move along bottom row from left to right

This gives a snake of length

( H * W ) / 6 + 2 * W + 6 where H - ( H / 6 ) * 6 = 0

For the case of a 6 by 9 matrix, the snake length is 33.

Answer 3

My intuition is that this problem is actually an NP-Complete problem and there should be a reduction from Longest Path Problem defined here to the Longest Snake Problem. I don't have a proof though but I would encourage you to think about it.