Leonhard loves labyrinths
JavaScript
Work in progress. Unfortunately the maze is not always solvable - the limit on back-forward is the real hurdle.
Edit 1 Cosmetic
Edit 2 Better gameplay, but the big problem is still there


var rows, columns, rowOfs, maze, plPos, points, playing

$('#BNEW').on('click', function() {
    NewMaze();
});
$('#BREP').on('click', function() {
    Start();
});

$(document).on('keydown', function(e) {
    var ok, move, pxy, mz, $td
    switch (e.which)
    {
    case 37:
        (move = -1, ok = maze[plPos+move] &lt; 9 &amp;&amp; maze[plPos+move*2] &lt; 9);
        break;
    case 39:
        (move = 1, ok = maze[plPos+move] &lt; 9 &amp;&amp; maze[plPos+move*2] &lt; 9);
        break;
    case 38: 
        (move = -rowOfs, ok = maze[plPos+move] &lt; 9 &amp;&amp; maze[plPos+move*2] &lt; 9);
        break;
    case 40: 
        (move = rowOfs, ok = maze[plPos+move] &lt; 9 &amp;&amp; maze[plPos+move*2] &lt; 9);
        break;
    }
    if (playing &amp;&amp; ok)
    {
        pxy = getXY(plPos)
        mz = maze[plPos] &lt; 8 ? 8 : 9;
        $td = $('#Field table tr').eq(pxy.y).find('td').eq(pxy.x)
        $td.addClass("m"+mz);
        maze[plPos] = mz;
        maze[plPos+move] = mz;
        plPos += move*2;
        mz = maze[plPos];
        PTS.value = mz==7 ? points += 20 : mz==6 ? points += 50 : mz == 8 ? points -= 1 : points;
        
        pxy = getXY(plPos)
        $td = $('#Field table tr').eq(pxy.y).find('td').eq(pxy.x)
        $td.removeClass("m6 m7")
        $('#Player').finish().animate(playerCss(pxy.x,pxy.y));
        CheckEndGame();
    }
    return !move
});

function CheckEndGame()
{
  var msg = ''
  if (maze[plPos] == 5)
  {
      msg = "Maze completed!";
  }
  else if (maze[plPos+1]==9 &amp;&amp; maze[plPos-1]==9
        &amp;&amp; maze[plPos+rowOfs]==9 &amp;&amp; maze[plPos-rowOfs]==9)
  {
      msg = "You are stuck, try again!";
  }
  if (msg) {
    $("#Msg").text(msg).show();
    playing=false
  }
}

function seed(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

function Build()
{
    var i
    var Fill = function(p)
    {
        var d=[rowOfs,-rowOfs,1,-1], i, s, l
        maze[p] = 1
        while(d[0])
        {
            i = random()*d.length|0
            s = d[i]
            if (s != (l=d.pop())) d[i]=l
            if (maze[p+s+s]&gt;8) {
                maze[p+s] = 1, Fill(p+s+s)
            }
        }
    }
    rowOfs = (columns + 1) * 2
    maze = Array(rowOfs * (rows*2+1))
    for (i=0; i &lt; maze.length; i++)
        maze[i] = i % rowOfs? 9 : 0
    Fill(rowOfs+2)
}

function NewMaze()
{
    SEED.value = Math.random()*65536 | 0
    Start()
}
    
function Start()
{
    var sd = SEED.value || 1
    columns = COLS.value |0 || 18
    rows = ROWS.value | 0 || 12
    COLS.value = columns
    ROWS.value = rows
    random = seed(sd)
    PTS.value = points = 0
    $("#Msg").hide();

    Build()
    
    plx = random()*columns|0;
    ply = random()*rows|0;
    setPlayer(plx,ply);
    plPos = getPos(plx,ply);
    BlockTriples(plPos);
    AddItems(plPos);
    Draw();
    playing = true;
  
}

function AddItems(p)
{
    var d=[rowOfs,-rowOfs,1,-1]
    var cells=[]
    // scan all reachable cells and calc distance from start
    var Go = function(p,l)
    {
        var i,t,mark,r
        ++l
        cells.push([p,l])
            
        maze[p] = 8;
        for(i=0; d[i]; i++)
        {
            t = d[i]
            if (maze[p+t]&lt;2 &amp;&amp; maze[p+t+t]&lt;2) 
            {
                Go(p+t+t, l)
            }
        }
        maze[p] = 0;
    } 
    Go(p,0)
    cells.sort(function(a,b){return a[1]-b[1]})
    cells=cells.slice(10) // cut the shortest distances 
    r = random()*10|0; //exit
    r = cells.length-r-1
    maze[cells[r][0]] = 5;
    console.log(r)
    cells = cells.slice(0,r)
    var ncr = rows, nnu = columns
    for(i = ncr+nnu; i; i--) 
    {
        r = random()*cells.length|0
        maze[cells[r][0]] = (i &gt; ncr ? 7 : 6);
        cells[r] = cells.pop();
    }
    
    
}

function BlockTriples(p)
{
    var d=[rowOfs,-rowOfs,1,-1]
    var Go = function(p)
    {
        var i,t,size=[0,0,0,0],s=1,nw=0,min,minp
        maze[p] = 8
        for(i=0; d[i]; i++)
        {
            t = d[i]
            if (maze[p+t]&lt;9 &amp;&amp; maze[p+t+t]&lt;8) 
            {
                ++nw
                s += size[i] = Go(p+t+t)
            }
        }
        if (nw &gt; 2) // triple way, block the smallest
        {
            for(i=0,min=1e6; d[i]; i++)
                size[i] &amp;&amp; size[i] &lt; min &amp;&amp; (min = size[minp = i])
            maze[p + d[minp]] = 5;
        }
        maze[p]=0
        return s
    } 
    Go(p)
}
    
function Draw()
{    
    var q=[], i, x, y;
    for(i = rowOfs+2, y = 0; y &lt; rows; y++)
    {
        q.push('&lt;tr&gt;')
        for (x = 0; x &lt; columns; i += 2, x++)
        {
            tcl = 'm'+(maze[i]|0)       
            maze[i-1]&gt;8 &amp;&amp; (tcl += ' wl')
            maze[i+1]&gt;8 &amp;&amp; (tcl += ' wr')
            maze[i-rowOfs]&gt;8 &amp;&amp; (tcl += ' wu')
            maze[i+rowOfs]&gt;8 &amp;&amp; (tcl += ' wb')
            q.push('&lt;td class="'+tcl+'"&gt;&lt;/td&gt;')
        }
        q.push('&lt;/tr&gt;')
        i += rowOfs+2
    }
    $("#TOUT").html(q.join(''));
    $("#Field").show();
}

function setPlayer(posx, posy)
{
    $('#Player').css(playerCss(posx, posy));
}    

function getXY(pos)
{
    return { x: (plPos % rowOfs)/2-1, y: plPos / rowOfs / 2 | 0}
}

function getPos(x, y)
{
   return (x+y*rowOfs)*2 + rowOfs+2;
}

function playerCss(posx, posy)
{
    return{ left: 6+posx*21, top: posy*21+2};
}
input { width: 3em; margin-right:1em }
table { 
  border: 2px solid #000; 
  border-collapse: collapse;
  font-size: 8px }
#Field { 
  margin: 10px; 
  position: relative;
  display: none;
}
td { 
    width: 19px; height: 19px; 
    padding: 0; margin: 0; 
    text-align: center;
}
td.wl { border-left: 2px solid #444; background: #fff }
td.wr { border-right: 2px solid #444; background: #fff }
td.wt { border-top: 2px solid #444;; background: #fff }
td.wb { border-bottom: 2px solid #444; background: #fff }
td.m7 { background: #ffd url(http://i.stack.imgur.com/QUInh.png) -21px 0}
td.m6 { background: #efe url(http://i.stack.imgur.com/QUInh.png) -1px 0}
td.m5 { background: #ddf url(http://i.stack.imgur.com/QUInh.png) -40px 0}
td.m8 { background: #eed }
td.m9 { background: #f55 }
#Player { position: absolute; top:0; left:0; color: #007; background: #fcb; font-size:12px }
#Msg { color: red; font-size:40px; display:none;  }
&lt;script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"&gt;&lt;/script&gt;
ID:&lt;input id=SEED&gt;
Rows:&lt;input id=ROWS&gt;
Columns:&lt;input id=COLS&gt;
&lt;button id=BNEW&gt;New&lt;/button&gt;
&lt;button id=BREP&gt;Replay&lt;/button&gt;
&lt;div id=Msg&gt;&lt;/div&gt;
&lt;div id=Field&gt;
&lt;table id=TOUT border=0 cellspacing=0 cellpadding=0&gt;
&lt;/table&gt;
&lt;span id=Player&gt;⛄&lt;/span&gt;    
&lt;/div&gt;
Score: &lt;input readonly id=PTS&gt;