Randomised Path on graph - set length, no crossing, no dead ends

Question

I am working on a game with a 8 wide 5 high grid. I have a 'snake' feature which needs to enter the grid and "walk" around for a set distance (20 for example). There are certain restrictions for the movement of the snake:

• It needs go over the predetermined amount of blocks (20)
• It cannot go over itself or double back (no dead ends)

Currently I am using a Randomised Depth First search, however I have found that it occasionally goes back over itself (crosses its own path) and am not sure if this is the best way to go about it.

Options considered: I have looked at using A*, but am struggling to figure out a good way to do it without a predetermined goal and the conditions above. I have also considered adding a heuristic to favour blocks that are not on the outside of the grid - but am not sure either of these will solve the issue at hand.

Any help is appreciated and I can add more detail or code if necessary:

public List<GridNode> RandomizedDepthFirst(int distance, GridNode startNode)
{
    Stack<GridNode> frontier = new Stack<GridNode>();
    frontier.Push(startNode);
    List<GridNode> visited = new List<GridNode>();
    visited.Add(startNode);
    while (frontier.Count > 0 && visited.Count < distance)
    {
        GridNode current = frontier.Pop();

        if (current.nodeState != GridNode.NodeState.VISITED)
        {
            current.nodeState = GridNode.NodeState.VISITED;

            GridNode[] vals = current.FindNeighbours().ToArray();
            List<GridNode> neighbours = new List<GridNode>();
            foreach (GridNode g in vals.OrderBy(x => XMLReader.NextInt(0,0)))
            {
                neighbours.Add(g);
            }
            foreach (GridNode g in neighbours)
            {
                frontier.Push(g);
            }

            if (!visited.Contains(current))
            {
                visited.Add(current);
            }
        }

    }
    return visited;
}

Answer 1

An easy way to account for back tracking is using a recursive dfs search.
Consider the following graph:

And a java implementation of a dfs search, removing nodes from the path when backtracking (note the comments. Run it online here) :

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Graph {

    //all graph nodes 
    private Node[] nodes;

    public Graph(int numberOfNodes) {

        nodes = new Node[numberOfNodes];
        //construct nodes
        for (int i = 0; i < numberOfNodes; i++) {
            nodes[i] = new Node(i);
        }
    }

    // add edge from a to b
    public Graph addEdge(int from, int to) {
        nodes[from].addNeighbor(nodes[to]);
        //unless unidirectional: //if a is connected to b
        //than b should be connected to a
        nodes[to].addNeighbor(nodes[from]);
        return this; //makes it convenient to add multiple edges
    }

    //returns a list of path size of pathLength.
    //if path not found : returns an empty list 
    public List<Node> dfs(int pathLength, int startNode) {

        List<Node> path = new ArrayList<>(); //a list to hold all nodes in path 
        Stack<Node> frontier = new Stack<>();
        frontier.push(nodes[startNode]);
        dfs(pathLength, frontier, path);
        return path;
    }

    private boolean dfs(int pathLength, Stack<Node> frontier, List<Node> path) {

        if(frontier.size() < 1) { 
            return false; //stack is empty, no path found 
        }

        Node current = frontier.pop();
        current.setVisited(true);
        path.add(current);

        if(path.size() == pathLength) {
            return true;  //path size of pathLength found 
        }

        System.out.println("testing node "+ current); //for testing 
        Collections.shuffle(current.getNeighbors());  //shuffle list of neighbours 
        for(Node node : current.getNeighbors()) {
            if(! node.isVisited()) {
                frontier.push(node);
                if(dfs(pathLength, frontier, path)) { //if solution found 
                    return true; //return true. continue otherwise  
                }
            }
        }
        //if all neighbours tested and no solution found, current node 
        //is not part of the path
        path.remove(current);      // remove it 
        current.setVisited(false); //this accounts for loops: you may get to this node 
                                   //from another edge
        return false;
    }

    public static void main(String[] args){

        Graph graph = new Graph(9); //make graph
        graph.addEdge(0, 4)  //add edges 
        .addEdge(0, 1)
        .addEdge(1, 2)
        .addEdge(1, 4)
        .addEdge(4, 3)
        .addEdge(2, 3)
        .addEdge(2, 5)
        .addEdge(3, 5)
        .addEdge(1, 6)
        .addEdge(6, 7)
        .addEdge(7, 8);

        //print path with length of 6, starting with node 1 
        System.out.println( graph.dfs(6,1));
    }
}

class Node {

    private int id;
    private boolean isVisited;
    private List<Node>neighbors;

    Node(int id){
        this.id = id;
        isVisited = false;
        neighbors = new ArrayList<>();
    }

    List<Node> getNeighbors(){
        return neighbors;
    }

    void addNeighbor(Node node) {
        neighbors.add(node);
    }

    boolean isVisited() {
        return isVisited;
    }

    void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

    @Override
    public String toString() {return String.valueOf(id);} //convenience 
}

Output:

testing node 1
testing node 6
testing node 7
testing node 8
testing node 2
testing node 5
testing node 3
testing node 4
[1, 2, 5, 3, 4, 0]

Note that nodes 6,7,8 which are dead-end, are tested, but not included in the final path.