My attempt at http://www.reddit.com/r/dailyprogrammer/comments/1eyipq/052413_challenge_123_hard_snakefill/

sample.txt

10 10
5
3 0
3 1
3 2
4 1
5 1

sample.txt.stdout

$ ./snakefill.py < sample.txt 
95 / 95
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 9
1 8
1 7
1 6
1 5
1 4
1 3
1 2
1 1
1 0
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 9
3 8
3 7
3 6
3 5
3 4
3 3
4 3
4 2
5 2
5 3
5 4
4 4
4 5
4 6
4 7
4 8
4 9
5 9
5 8
5 7
5 6
5 5
6 5
6 4
6 3
6 2
6 1
7 1
7 2
7 3
7 4
7 5
7 6
6 6
6 7
6 8
6 9
7 9
8 9
9 9
9 8
8 8
7 8
7 7
8 7
9 7
9 6
8 6
8 5
9 5
9 4
8 4
8 3
9 3
9 2
8 2
8 1
9 1
9 0
8 0
7 0
6 0
5 0
4 0

snakefill.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
import heapq
from copy import deepcopy

import numpy as np

# Constants for the various cell states
#
EMPTY = 0           # Cell is empty
OBSTACLE = 1        # Cell contains an obstacle
HEAD = 2            # Cell contains the snakes head
UP = (-1, 0)        # Cell contains snake body exiting upwards
DOWN = (+1, 0)      # Cell contains snake body exiting downwards
LEFT = (0, -1)      # Cell contains snake body exiting left
RIGHT = (0, +1)     # Cell contains snake body exiting right


class Snake(np.ndarray):
    """Class that holds a snake game state, represented as grid."""

    def __new__(cls, width, height, obstacles, start=(0, 0)):
        obj = np.ndarray.__new__(cls, (height, width), object, None, 0, None, 'C')
        obj.fill(EMPTY)
        for pos in obstacles:
            obj[pos] = OBSTACLE
        obj[start] = HEAD
        obj.head = obj.start = start
        return obj

    def __array_finalize__(self, obj):
        if obj is not None:
            self.head = getattr(obj, 'head', None)
            self.start = getattr(obj, 'start', None)

    def __nonzero__(self):
        # heapq doesn't expect truthiness to produce an iterable, which breaks
        # comparison unless we introduce the following hack
        return any(self)

    def __unicode__(self):
        rep = {EMPTY: u'·', OBSTACLE: u'█', UP: u'↑', DOWN: u'↓', LEFT: u'←', RIGHT: u'→', HEAD: u'•'}
        return u'\n'.join(u' '.join(rep[cell] for cell in row) for row in self)

    def can_move(self, direction):
        """Get whether or not the snake can move in the specified direction."""
        try:
            new_head = self.head[0] + direction[0], self.head[1] + direction[1]
            return new_head[0] >= 0 and new_head[1] >= 0 and self[new_head] == EMPTY
        except IndexError:
            return False

    def move(self, direction):
        """Move the snake in the specified direction."""
        assert self.can_move(direction)
        new_head = self.head[0] + direction[0], self.head[1] + direction[1]
        self[self.head] = direction
        self.head = new_head
        self[new_head] = HEAD
        return self

    def path(self):
        """Reconstitute the snake path as a list of co-ordinates."""
        pos = self.start
        result = []
        while self[pos] != HEAD:
            result.append(pos)
            pos = pos[0] + self[pos][0], pos[1] + self[pos][1]
        result.append(pos)
        return result

    def n_obstacles(self):
        """Get the number of obstacles in the board state."""
        return sum(cell is OBSTACLE for row in self for cell in row)

    def n_cells(self):
        """Get the total number of cells in the board."""
        return self.shape[0] * self.shape[1]

    def is_free(self, idx):
        """Get whether or not the cell at the given index is free (empty or head)."""
        return (0 <= idx[0] < self.shape[0]
                and 0 <= idx[1] < self.shape[1]
                and self[idx] in {EMPTY, HEAD})


def read_initial_state(fp=sys.stdin):
    """Read a board state from the given file-pointer"""
    width, height = tuple(map(int, fp.readline().split()))
    n_obstacles = int(fp.readline())
    obstacles = [tuple(map(int, fp.readline().split())) for _ in xrange(n_obstacles)]
    # Convert the row-order
    obstacles = [(row, col) for col, row in obstacles]
    return Snake(width, height, obstacles)


def inaccessibility_heuristic(snake):
    """Board state fitness heuristic based on how accessible empty cells are; i.e
    how many directions they can move to."""
    inaccessibility = 0
    for col in xrange(snake.shape[1]):
        for row in xrange(snake.shape[0]):
            if snake[row, col] is EMPTY:
                n_free_neighs = (snake.is_free((row - 1, col))
                                 + snake.is_free((row + 1, col))
                                 + snake.is_free((row, col + 1))
                                 + snake.is_free((row, col - 1)))
                inaccessibility += 1.0 / (1.0 + n_free_neighs ** 2)
    return inaccessibility


def find_longest_path(initial_state, cost=inaccessibility_heuristic):
    """
    Find the longest possible snake from the given initial configuration.

    Board states are evaluated in order of a static analysis heuristic; specified by cost.
    """

    min_cost, best = float('inf'), None
    # Initialise the queue to contain just the initial state
    remaining = [(cost(initial_state), initial_state)]

    while min_cost > 0:

        # Read the next (best) state from the queue
        current_cost, current = heapq.heappop(remaining)

        # If it's better than out current best then save
        if current_cost <= min_cost:
            min_cost, best = current_cost, current

        # Add all child states (found by moving in all possible directions) to the queue.
        for direction in UP, DOWN, LEFT, RIGHT:
            if current.can_move(direction):
                child = deepcopy(current).move(direction)
                heapq.heappush(remaining, (cost(child), child))

    return best


if __name__ == '__main__':
    start = read_initial_state(fp=sys.stdin)
    result = find_longest_path(start)
    print '%d / %d' % (len(result.path()), start.n_cells() - start.n_obstacles())
    for row, col in result.path():
        print col, row