text:
Leonhard loves labyrinths
The background
My son Leonhard (4 years old) loves labyrinths. I don't know where he knows labyrinths from, but he paints them and knows quite well how they work:

Recently, he started making a game from his paintings. These are his rules:

a black square denotes the starting point.
a hook denotes the exit of the labyrinth (that's where you get pulled out).
you can collect crowns.
you can collect gold nuggets (the round things).
you can go a way forth and back, but not more than that.
arrows may guide you to the exit. (If he paints a labyrinth for me to solve, they are often misleading).

Annotated version:

blue: starting point
orange: crowns
yellow: area with gold nuggets
green: hook (exit)
pink: arrows (mostly misleading)

The Task
Maybe you know, at the age of 4, kids start telling porky-pies and sometimes he does not follow his own rules, especially if he finds out that he cannot reach the end of the maze any more.
That's where you come into play: since I'm looking for games for kids anyway, you turn his idea into a game where cheating is not possible.
Well, we need some more definitions I'd say:

the playing field is a n*m rectangle of equally sized squares.
a square can have 0 to 4 walls, one on each side.
a crown is worth 50 points.
a gold nugget is worth 20 points.
walking on a square that has already been walked subtracts 1 point.
squares are marked in a way to identify how often the player walked on it (0, 1 or 2 times)
the player can walk in 4 directions, except if there is a wall.
Input device can be anything. Please consider keyboard support.
The labyrinth must be solvable. I.e. it must be possible to reach the hook from the starting point and it must be possible to collect all the valuables (even if that does not result in the highest possible score).
If the player gets stuck, the game ends.
The player must not die by falling off the board. You may put a wall around the complete maze or wrap around edges, whatever you like.
the program takes an word (0-65535) argument as input. This is the seed for the random number generator. Calling the program with the same seed again results in the same labyrinth.

Bonus:

calculate the maximum points that can be collected. Consider that due to -1 points it might be better to not collect all items.
Show the best solution (shortest way to get maximum points)

The Rules
This is a popularity contest, since I want to be able to read and understand the code and perhaps adapt to new ideas of my son. Sorry, code golfers, maybe you want to create a copy of this question with rules more suitable for golfing, e.g. a console version with all the characters defined.
The most popular game on 3rd of May will become the accepted answer. And, hey, why not publish it in an app store?

I feel as though this may come under fire for being too much of an art competition vs a programming one. Since all of these games should behave in a nearly identical way, what reason would I have to vote for one over another besides how nice it looks? There doesn't seem to be much potential creativity in making this maze game. That said, I'm more of a golfer, so I'll let people who more frequently participate in pop-cons decide if this is on topic.

There are two separate parts to this challenge: one is the labyrinth design (but it is difficult to algorithmically produce a satisfactory game labyrinth) and the other is the game engine (which is rather easier). I think it would be better if you restricted the challenge to the game engine (and made it a code golf.) You would need to post some sample labyrinths (to be taken as input from text file) in the question (possibly designed with your son's help.)

Related (and perhaps a partial duplicate of the labyrinth design part) http://codegolf.stackexchange.com/q/25967/15599

I think this is an excellent challenge. It has several problems to solve and room for creativity. More challenges like this please +1. [back to building a solution...]

Are we required to generate "arrows". Do they allow the player to cross them the other way?

@steveverrill Is there a reason you would say the game engine should be a code-golf? The original poster explicitly states he doesn't want golf-code.

@TheNumberOne: sorry for the late answer. a) there needn't be arrows, they are optional. b) Arrows can be helpful or misleading. The problem is, you don't know in advance. c) You can generate arrows in any direction. The player is allowed to cross them in any direction as often as the rest of the rules allow (i.e. walk on the tile twice)

is there any way you can extend this? i've been working on something but it's not finished yet...

never mind, i can't get it to work... :(

@sirpercival: I put a bounty on this to get more answers. Usually I participate in the puzzles myself, but I didn't find time for this one. I have no idea how hard it really is.

i've been working on a maze app w/ kivy, but i can't get my flood fill algorithm to work.

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] < 9 && maze[plPos+move*2] < 9);
        break;
    case 39:
        (move = 1, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 38:
        (move = -rowOfs, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 40:
        (move = rowOfs, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    }
    if (playing && ok)
    {
        pxy = getXY(plPos)
        mz = maze[plPos] < 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 && maze[plPos-1]==9
        && maze[plPos+rowOfs]==9 && 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]>8) {
                maze[p+s] = 1, Fill(p+s+s)
            }
        }
    }
    rowOfs = (columns + 1) * 2
    maze = Array(rowOfs * (rows*2+1))
    for (i=0; i < 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]<2 && maze[p+t+t]<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 > 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]<9 && maze[p+t+t]<8)
            {
                ++nw
                s += size[i] = Go(p+t+t)
            }
        }
        if (nw > 2) // triple way, block the smallest
        {
            for(i=0,min=1e6; d[i]; i++)
                size[i] && size[i] < min && (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 < rows; y++)
    {
        q.push('
')
        for (x = 0; x < columns; i += 2, x++)
        {
            tcl = 'm'+(maze[i]|0)
            maze[i-1]>8 && (tcl += ' wl')
            maze[i+1]>8 && (tcl += ' wr')
            maze[i-rowOfs]>8 && (tcl += ' wu')
            maze[i+rowOfs]>8 && (tcl += ' wb')
            q.push('	')
        }
        q.push('
')
        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(https://i.stack.imgur.com/QUInh.png) -21px 0}
td.m6 { background: #efe url(https://i.stack.imgur.com/QUInh.png) -1px 0}
td.m5 { background: #ddf url(https://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;  }

ID:<input id=SEED>
Rows:<input id=ROWS>
Columns:<input id=COLS>
<button id=BNEW>New</button>
<button id=BREP>Replay</button>

⛄

Score: <input readonly id=PTS>

Well done, impressive.  I do not get the 'logic' on how you create the maze. How does that part work?

@CousinCocaine The Build function use a recursive fill, it's the more 'classic' way to build a simply connected maze - see http://en.wikipedia.org/wiki/Maze_generation_algorithm

My son loves it. While he wants me to print larger size mazes, he plays the smaller ones online. According to the rules, your answer was the best on 3rd of May, so I've accepted it now. Since it is also the only answer, you get the bounty. Well done, it's amazing.

Thank you very much, glad that your son likes it. Now it's time to raise the biddings.

Java
I never complained about GolfScript or CJam, but here's a Java answer for you anyway. This was a really enjoyable challenge. ;)
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.geom.Ellipse2D;
import java.util.*;
import javax.swing.*;

public class MazeMaker {
    int row, col, exitRow, exitCol, numCells, score, array[][];
    final int SQWIDTH = 20;
    boolean gameOver = true;
    Ellipse2D.Double ellipse;
    JFrame frame;
    JPanel mazePanel;
    JLabel scoreLabel;

    public MazeMaker() {
        frame = new JFrame("Maze");
        frame.setLayout(new BorderLayout());
        JPanel topPanel = createTopPanel();
        frame.add(topPanel,BorderLayout.NORTH);

        createMazePanel();
        frame.add(new JScrollPane(mazePanel),BorderLayout.CENTER);

        setKeyActions();

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
    }

    private void constructArray(int seed, int rows, int cols) {
        array = new int[rows*2-1][cols*2-1];
        for (int[] a : array)
            Arrays.fill(a,-1);
        numCells = (array.length / 2 + 1) * (array[0].length / 2 + 1);
        Random rand = new Random(seed);
        int row = rand.nextInt(array.length / 2 + 1) * 2;
        int col = rand.nextInt(array[0].length / 2 + 1) * 2;
        array[row][col] = 0;
        boolean first = true, a = false, exitFound = false;

        while (true) {
            if (first) {
                int direction = rand.nextInt(4);
                if (direction == 0 && row != 0) {
                    array[row-1][col] = 0;
                    array[row-2][col] = 0;
                    row -= 2;
                    first = false;
                }
                else if (direction == 1 && col != array[0].length - 1) {
                    array[row][col+1] = 0;
                    array[row][col+2] = 0;
                    col += 2;
                    first = false;
                }
                else if (direction == 2 && row != array.length - 1) {
                    array[row+1][col] = 0;
                    array[row+2][col] = 0;
                    row += 2;
                    first = false;
                }
                else if (direction == 3 && col != 0) {
                    array[row][col-1] = 0;
                    array[row][col-2] = 0;
                    col -= 2;
                    first = false;
                }
            }
            else {
                int availableCells = 0;
                boolean up = false, down = false, left = false, right = false;
                if (row != 0 && array[row-2][col] == -1) {
                    availableCells++;
                    up = true;
                }

                if (col != array[0].length-1 && array[row][col+2] == -1) {
                    availableCells++;
                    right = true;
                }

                if (row != array.length-1 && array[row+2][col] == -1) {
                    availableCells++;
                    down = true;
                }

                if (col != 0 && array[row][col-2] == -1) {
                    availableCells++;
                    left = true;
                }

                if (availableCells != 0) {
                    a = true;
                    while (true) {
                        boolean[] b = {up,right,down,left};
                        int i = rand.nextInt(4);
                        if (b[i]) {
                            if (i == 0) {
                                array[row-1][col] = 0;
                                array[row-2][col] = 0;
                                row -= 2;
                            }
                            else if (i == 1) {
                                array[row][col+1] = 0;
                                array[row][col+2] = 0;
                                col += 2;
                            }
                            else if (i == 2) {
                                array[row+1][col] = 0;
                                array[row+2][col] = 0;
                                row += 2;
                            }
                            else if (i == 3) {
                                array[row][col-1] = 0;
                                array[row][col-2] = 0;
                                col -= 2;
                            }
                            break;
                        }
                    }
                }
                else {
                    array[row][col] = 1;
                    if (!exitFound && a) {
                        if (new Random().nextInt(5) == 0) {
                            exitFound = true;
                            exitRow = row;
                            exitCol = col;
                        }
                    }
                    a = false;
                    if (row != 0 && array[row-1][col] == 0 && (array[row-2][col] == 0 || array[row-2][col] == 1)) {
                        array[row-1][col] = 1;
                        array[row-2][col] = 1;
                        row -= 2;
                    }
                    else if (col != array[0].length-1 && array[row][col+1] == 0 && (array[row][col+2] == 0 || array[row][col+2] == 1)) {
                        array[row][col+1] = 1;
                        array[row][col+2] = 1;
                        col += 2;
                    }
                    else if (row != array.length-1 && array[row+1][col] == 0 && (array[row+2][col] == 0 || array[row+2][col] == 1)) {
                        array[row+1][col] = 1;
                        array[row+2][col] = 1;
                        row += 2;
                    }
                    else if (col != 0 && array[row][col-1] == 0 && (array[row][col-2] == 0 || array[row][col-2] == 1)) {
                        array[row][col-1] = 1;
                        array[row][col-2] = 1;
                        col -= 2;
                    }
                }
                if (checkDone()) {
                    if (!exitFound) {
                        exitRow = row;
                        exitCol = col;
                    }
                    break;
                }
            }
        }
    }

    private boolean checkDone() {
        int count = 0;
        for (int k = 0; k < array.length; k+=2) {
            for (int l = 0; l < array[0].length; l+=2) {
                if (array[k][l] == 0 || array[k][l] == 1)
                    count++;
            }
        }
        return count == numCells;
    }

    private JPanel createTopPanel() {
        GridBagLayout l = new GridBagLayout();
        GridBagConstraints c = new GridBagConstraints();
        c.fill = GridBagConstraints.BOTH;

        JPanel panel = new JPanel(l);
        JLabel inputLabel = new JLabel("ID:");
        c.gridwidth = 1;
        l.setConstraints(inputLabel,c);
        panel.add(inputLabel);

        JTextField inputField = new JTextField(5);
        l.setConstraints(inputField,c);
        panel.add(inputField);

        JLabel rowLabel = new JLabel("Rows:");
        l.setConstraints(rowLabel,c);
        panel.add(rowLabel);

        JTextField rowField = new JTextField(3);
        l.setConstraints(rowField,c);
        panel.add(rowField);

        JLabel colLabel = new JLabel("Columns:");
        l.setConstraints(colLabel,c);
        panel.add(colLabel);

        JTextField colField = new JTextField(3);
        l.setConstraints(colField,c);
        panel.add(colField);

        JButton applyButton = new JButton("Apply");
        applyButton.addActionListener(ev -> {
            try {
                int seed = Integer.parseInt(inputField.getText()),
                    rows = Integer.parseInt(rowField.getText()),
                    cols = Integer.parseInt(colField.getText());
                if (seed >= 0 && rows >= 3 && cols >= 3) {
                    gameOver = false;
                    scoreLabel.setText("Score: " + (score = 0));
                    constructArray(seed,rows,cols);
                    row = (int) (Math.random() * (array.length / 2 + 1)) * 2;
                    col = (int) (Math.random() * (array[0].length / 2 + 1)) * 2;
                    frame.setSize((1+SQWIDTH * array[0].length)/2 > 750 ? (1+SQWIDTH * array[0].length)/2 : 750,
                            75+(1+SQWIDTH * array.length)/2);
                    mazePanel.setPreferredSize(new Dimension(
                            (1+SQWIDTH * array[0].length)/2 > 750 ? (1+SQWIDTH * array[0].length)/2 - 15 : 750,
                            15+(1+SQWIDTH * array.length)/2));
                    ellipse = new Ellipse2D.Double(col*SQWIDTH/2+3,row*SQWIDTH/2+3,10,10);
                    setItems();
                    mazePanel.repaint();
                }
            } catch (NumberFormatException ignore) {}
        });
        l.setConstraints(applyButton,c);
        panel.add(applyButton);

        scoreLabel = new JLabel("Score: ");
        c.gridwidth = GridBagConstraints.REMAINDER;
        l.setConstraints(scoreLabel,c);
        panel.add(scoreLabel);

        return panel;
    }

    private void createMazePanel() {
        mazePanel = new JPanel() {
            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);
                int x = 0, y = 0;
                if (!gameOver) {
                    for (int k = 0; k < array.length; k+=2) {
                        for (int l = 0; l < array[0].length; l+=2) {
                            int n = array[k][l];
                            if (n == 0 || n == 1 || n == 4 || n == 5 || n == 6)
                                g.setColor(Color.white);
                            else if (n == 2)
                                g.setColor(Color.green);
                            else if (n == 3)
                                g.setColor(Color.red);
                            g.fillRect(x, y, SQWIDTH, SQWIDTH);
                            if (n == 4) {
                                g.setColor(new Color(245,209,34));
                                g.fillOval(x+3, y+3, 10, 10);
                            }
                            else if (n == 5) {
                                g.setColor(new Color(255,223,55));
                                g.fillPolygon(new int[]{x,x+3,x+8,x+13,x+16,x+14,x+2},new int[]{y+2,y+6,y+2,y+6,y+2,y+16,y+16},7);
                                g.setColor(new Color(12,234,44));
                                g.fillOval(x+7,y+6,4,7);
                            }
                            else if (n == 6) {
                                Graphics2D g2 = (Graphics2D) g.create();
                                g2.setStroke(new BasicStroke(2,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND));
                                g2.setColor(new Color(108,225,119));
                                g2.drawOval(x+5, y+1, 8, 8);
                                g2.drawLine(x+5, y+3, x+5, y+11);
                                g2.drawArc(x+5, y+8, 7, 7, 180, 180);
                            }
                            g.setColor(Color.black);
                            if (k != array.length-1 && array[k+1][l] == -1)
                                g.fillRect(x-3, y+SQWIDTH-3, SQWIDTH+3, 3);
                            if (l != array[0].length-1 && array[k][l+1] == -1)
                                g.fillRect(x+SQWIDTH-3,y,3,SQWIDTH);
                            x += SQWIDTH;
                        }
                        x = 0;
                        y += SQWIDTH;
                    }
                    g.setColor(Color.red);
                    ((Graphics2D) g).fill(ellipse);
                }
            }
        };
    }

    private void setKeyActions() {
        InputMap im = mazePanel.getInputMap(JComponent.WHEN_IN_FOCUSED_WINDOW);
        ActionMap am = mazePanel.getActionMap();

        im.put(KeyStroke.getKeyStroke("pressed UP"), "up");
        am.put("up", new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (row != 0 && array[row-1][col] != -1 && array[row-2][col] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    row -= 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.y = row * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed RIGHT"), "right");
        am.put("right",new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (col != array[0].length-1 && array[row][col+1] != -1 && array[row][col+2] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    col += 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.x = col * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed DOWN"), "down");
        am.put("down", new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (row != array.length-1 && array[row+1][col] != -1 && array[row+2][col] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    row += 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.y = row * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed LEFT"), "left");
        am.put("left",new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (col != 0 && array[row][col-1] != -1 && array[row][col-2] != -1 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    col -= 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.x = col * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });
    }

    private void setItems() {
        array[exitRow][exitCol] = 6;
        Random r = new Random();
        for (int k = 1; k < (array.length * array[0].length) / 20; k++) {
            int row = r.nextInt(array.length / 2 + 1) * 2,
                col = r.nextInt(array[0].length / 2 + 1) * 2;
            if ((row == this.row && col == this.col) || array[row][col] == 4 || array[row][col] == 5 || array[row][col] == 6)
                k--;
            else
                array[row][col] = r.nextInt(2) + 4;
        }
    }

    private boolean checkGameOver() {
        if (row == 0 && col == 0)
            return (array[row+2][col] == 3 && array[row][col+2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col+1] == -1);
        else if (row == 0 && col == array[0].length-1)
            return (array[row+2][col] == 3 && array[row][col-2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-1] == -1);
        else if (row == array.length-1 && col == 0)
            return (array[row-2][col] == 3 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col+1] == -1);
        else if (row == array.length-1 && col == array[0].length-1)
            return (array[row-2][col] == 3 && array[row][col-2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-1] == -1);
        else if (row == 0)
            return (array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row+1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
        else if (col == 0)
            return (array[row][col+2] == 3 && array[row-1][col] == -1 && array[row+1][col] == -1) ||
                   (array[row][col+1] == -1 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col+1] == -1 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col+1] == -1 && array[row-2][col] == 3 && array[row+2][col] == 3) ||
                   (array[row][col+2] == 3 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col+2] == 3 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col+2] == 3 && array[row-2][col] == 3 && array[row+2][col] == 3);
        else if (row == array.length-1)
            return (array[row-2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
        else if (col == array[0].length-1)
            return (array[row][col-2] == 3 && array[row-1][col] == -1 && array[row+1][col] == -1) ||
                   (array[row][col-1] == -1 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col-1] == -1 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col-1] == -1 && array[row-2][col] == 3 && array[row+2][col] == 3) ||
                   (array[row][col-2] == 3 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col-2] == 3 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col-2] == 3 && array[row-2][col] == 3 && array[row+2][col] == 3);
        else
            return (array[row-2][col] == 3 && array[row][col+1] == -1 && array[row+1][col] == -1 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+2] == 3 && array[row+1][col] == -1 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+1] == -1 && array[row+2][col] == 3 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+1] == -1 && array[row+1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row-1][col] == -1 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(MazeMaker::new);
    }
}

The process of creating the actual maze uses the depth-first search algorithm, but with an iterative approach. Here's how it works.
We start with a 2D array of int values, each element being a -1. A random element with even indices is chosen, and its value becomes 0:
-1 -1 -1 -1 -1 -1  0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1

Then the program enters a loop, checking for available cells until it reaches a state where there are no available cells. This can happen several times, and is when it begins to backtrack. At this time all 0s that it comes across become 1s. Also during this time is when it determines whether an exit should be placed at that location. So at the end of it all, the array could look like this:
 0  0  0  0  0  0  1  1  1
 0 -1 -1 -1 -1 -1  0 -1  1
 0  0  0  0  0 -1  0 -1  1
-1 -1 -1 -1 -1 -1  0 -1  1
 0  0  0  0  0  0  0 -1  1
 0 -1 -1 -1 -1 -1 -1 -1  1
 0 -1  1  1  1  1  1 -1  1
 0 -1  1 -1  1 -1 -1 -1  1
 0 -1  1 -1  1  1  1  1  1

When there are a predetermined number of 1s or 0s at certain spots in the array, the loop exits. Then, using the array, the resulting maze is drawn:

It's easy to see that the -1s in the array represent walls, and the 0s and 1s are corridors. Items are randomly distributed throughout the maze. The red ellipse is the "player" that you control.
The maze is wrapped in a scroll pane for convenience so that if the size exceeds the frame's maximum size you can scroll to see the rest of the maze.
I'd say the only problem with this is how the end of game check is carried out. I thought about several ways to go about doing it, but I ended up resorting to hard-coding it all. I'm open to suggestions on how it can be done.

This doesn't compile. MazeMaker.java:168: error: cannot find symbol         printArray();         ^   symbol:   method printArray()   location: class MazeMaker

@edc65 Thanks for letting me know. I did have a method called printArray that I used to output the array, but deleted it and forgot to remove the method call.

Ok, I have it running now. It's nice. I'm trying to restart the same maze keeping the same id, but does not seem to work.

I have it so that the start and end positions are randomized each time the Apply button is pressed, but the layout of the maze remains the same. Should it not be that way?

I thought that as a way to start again with the exactly the same challenge. My main concern is to verify that the challenge is always solvable (a constraint of original questione that I found hard)

Great! I'm happy to see another answer. I'll try it tomorrow in the office where I have Eclipse installed (using Visual Studio at home).

I was hoping for a bigger return on my investement, but anyay, one good answer is better than nothing. The bounty is yours

@edc65 Verifing solvable is often a question of generating a maze "backwards": 1. Random maze, 2. Start from the end and move backwards until start, 3. Cut wall holes if neccesary. That way you know it is solvable when done.

 Python
I realize I'm late for the party, but here is my take on this challenge. I went text based as I haven't gotten around to learning pygame, yet.  It is Python 3.  Change input to raw_input and it should work in python2 also.
The Hook (exit) is represented by "J". "W" is crowns (50).  "G" is Gold nuggets (20).  The Player is "O". I experimented with using "P" for the player, but I found "O" easier to Identify.
I used standard depth first maze generation, then add the gold, crowns, hook, and current player position.  I did not implement the criteria that all treasure can be obtained.

import random

direcs = {'n':[0,-1],
          's':[0,1],
          'w':[-1,0],
          'e':[1,0]}
dirs = ['n','s','e','w']

class maze_space(object):
    def __init__(self):
        self.n = 0
        self.s = 0
        self.e = 0
        self.w = 0
        self.visited = 0
        self.contents = ' '

    def mirror(self,drct,val):
        if drct == 'n' : self.s = val
        if drct == 's' : self.n = val
        if drct == 'e' : self.w = val
        if drct == 'w' : self.e = val

class MazeGame(object):

    def __init__(self,horiz=12,vert=8):
        self.completed = 0
        self.score = 0
        self.grid = [[maze_space() for x in range(horiz)] for y in range(vert)]

        def walk(y,x):
            self.grid[y][x].visited = 1
            drs = self.make_dir_list(y, x)
            random.shuffle(drs)
            for dr in drs:
                yy = y + direcs[dr][1]
                xx = x + direcs[dr][0]
                if not self.grid[yy][xx].visited:
                    setattr(self.grid[y][x], dr, 1)
                    self.grid[yy][xx].mirror(dr, 1)
                    walk(yy, xx)

        y, x = self.pick_row_col()
        walk(y, x)
        self.maze_populate()
        self.printmaze()

    def main_loop(self):
        while not self.completed:
            move = get_move(self.grid, self.cury, self.curx)
            self.make_move(move)
            self.printmaze()

    def pick_row_col(self):
        '''pick a random cell in the grid'''
        row = random.randint(0, len(self.grid) - 1)
        col = random.randint(0, len(self.grid[0]) - 1)
        return row, col

    def make_dir_list(self, y, x):
        '''return list of available move directions'''
        drs = dirs[:]
        if x == 0 : drs.pop(drs.index('w'))
        if y == 0 : drs.pop(drs.index('n'))
        if x == len(self.grid[0]) - 1 : drs.pop(drs.index('e'))
        if y == len(self.grid) - 1 : drs.pop(drs.index('s'))
        return drs

    def maze_populate(self):
        # populate maze with crowns and gold nuggets
        for treasure in ['G', 'W']:
            for _ in range(random.randint(1, len(self.grid[0]))):
                yy, xx = self.pick_row_col()
                self.grid[yy][xx].contents = treasure

        self.cury, self.curx = self.pick_row_col() # start position
        exity, exitx = self.pick_row_col() # hook (exit) position
        #make sure start is not on top of exit
        while self.cury == exity and self.curx == exitx :
            exitx = random.randint(0, len(self.grid[0]) - 1)

        self.grid[self.cury][self.curx].contents = 'O'
        self.grid[exity][exitx].contents = 'J'

    def make_move(self,dr):
        self.grid[self.cury][self.curx].visited += 1
        self.grid[self.cury][self.curx].contents = '.'
            # player has walked twice -> disable
        if self.grid[self.cury][self.curx].visited >= 3:
            self.grid[self.cury][self.curx].contents = 'X'
            drs = self.make_dir_list(self.cury, self.curx)
            for d in drs:
                yyy = self.cury + direcs[d][1]
                xxx = self.curx + direcs[d][0]
                self.grid[yyy][xxx].mirror(d,0)

        yy = self.cury + direcs[dr][1]
        xx = self.curx + direcs[dr][0]
        if self.grid[yy][xx].contents == 'J': self.completed = 1
        if self.grid[yy][xx].contents == 'W': self.score += 50
        if self.grid[yy][xx].contents == 'G': self.score += 20
        if self.grid[yy][xx].contents == '.': self.score -= 1
        self.grid[yy][xx].contents = 'O'
        self.cury, self.curx = yy, xx

    def printmaze(self):
        if self.completed: print('\nMaze complete.  Good job!')
        print('Score: %d'%self.score)
        print('|'+''.join('---' for _ in self.grid[0]))
        for line in self.grid:
            print('|' + ''.join(' %s '%x.contents if x.e else ' %s|'%
                                x.contents for x in line))
            print('|' + ''.join('  -' if x.s else '---' for x in line))

def get_params():
    hor = input('width (default=12): ')
    hor = int(hor) if hor else 12
    ver = input('height (default=8): ')
    ver = int(ver) if ver else 8
    rseed = input('seed : ')
    rseed = int(rseed) if rseed else random.randint(1,65535)
    print(rseed)
    random.seed(rseed)
    print("'J' = hook (exit)\n'O' = Player")
    print("'G' = gold nugget (20 points)\n'W' = Crown (50 points)")
    print('Player may only tread on a given tile twice')
    return hor,ver

def get_move(grid, y, x):
    choice = input('where do you want to move %s q to quit: '%dirs)
    if choice == 'q' : exit()
    if choice in dirs and getattr(grid[y][x],choice): return choice
    return get_move(grid, y, x)

def main():
    hor,ver = get_params()
    maze = MazeGame(hor,ver)
    maze.main_loop()

if __name__ == '__main__':
    main()


text:
Compute the Hausdorff Distance
Introduction
The Hausdorff distance measures the difference between two subsets of a metric space.
Intuitively, a metric space is just some set with a built-in distance function; in this challenge, we will use natural numbers with the ordinary distance d(a, b) := abs(a - b).
The Hausdorff distance between two non-empty finite sets A and B is given by
max(max(min(d(a, b) for b in B) for a in A),
    max(min(d(a, b) for a in A) for b in B))

in Python-like notation.
The Hausdorff distance can be computed by finding the element of A for which the distance to the nearest element of B is maximal, and the element of B for which the distance to the nearest element of A is maximal, and then taking the maximum of these distances.
In other words, if the Hausdorff distance is d, then every element of A is within distance d of some element of B, and vice versa.
Input
Your input is a single list of integers.
It only contains the elements 0,1,2,3, which signify whether the given index of the list is an element of neither A nor B, only A, only B, or both A and B.
For example, the input [0,1,1,0,2,3] means that A = {1,2,5} and B = {4,5}, if we use 0-based indexing (which makes no difference, as our metrics are translation invariant).
Output
Your output is the Hausdorff distance between A and B; in the above example, it is 3.
If either set is empty, then the distance is not defined, and you shall return -1.
Rules
You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
[] -> -1
[0] -> -1
[0,1,0] -> -1
[2,0,0,2] -> -1
[0,1,2,3] -> 1
[0,3,3,0,0,0,0,3] -> 0
[1,0,0,1,0,0,1,3,1] -> 7
[1,0,0,0,0,3,0,0,0,0,2] -> 5
[0,1,1,3,1,3,2,1,1,3,0,3] -> 2
[2,2,2,1,2,0,3,1,3,1,0,3] -> 3
[1,3,0,2,0,2,2,1,0,3,2,1,1,2,2] -> 2
[1,0,1,1,2,0,1,2,3,1,0,0,0,1,2,0] -> 4

In your equation, I believe that it is much too long, as max(max(min(d(a, b) for b in B) for a in A)) should be sufficient. This is because d(a,b) returns the absolute value, and therefore both max functions will return the same number every time.

@NathanMerrill It may be that every element of A is very close to one of B, but there are elements of B very far from A (for example, if A is a subset of B). In that case, the short formula is incorrect.

CJam, 53 52 46 38 37 bytes
3,q~f{f&:L,{L=},}$~ff{-z}_z+::e<W+:e>

Takes input on STDIN as a CJam style array:
[0 1 2 3]

Here is a test harness which converts all the test cases to this format and runs the code on them. Although the results are in the input field, they are not used by the code (remove them if you don't trust me :)).
Explanation
First, we parse the input to get the two sets A and B:
3,q~f{f&:L,{L=},}$~
3,                  "Push [0 1 2]. 1 is for A, 2 is for B, and 0 we can luckily ignore
                     as we'll see later.";
  q~                "Read and evaluate the input.";
    f{          }   "Map this block onto the [0 1 2] array, copying in the input for
                     each iteration.";
      f&:L          "Take the bitwise AND with each element of the input and store the
                     result in L.";
          ,{  },    "Get the length N, and filter the range [0 .. N-1] by evaluating
                     the block for each element.";
            L=      "Check if the bitwise AND at that index yielded something non-zero.
                     This gives an empty array for 0, A for 1 and B for 2.";
                 $  "Sort the three arrays. This has two important effects: a) it moves
                     the empty array resulting from 0 to the front, and b) if only one
                     of A and B is empty, it moves the non-empty one to the end.";
                  ~ "Unwrap the array, dumping all three sets on the stack.";

And now we find the absolute differences and select the max of the mins:
ff{-z}_z+::e<W+:e>
ff{-z}             "Turn A and B into a matrix of absolute differences.";
      _z           "Duplicate and transpose.";
        +          "Add the two together, so I've got one row of distances for
                    each element in either A or B.";
         ::e<      "Find the minimum of each row.";
             W+    "Add a -1 in case one set was empty.";
               :e> "Get the overall maximum.";

Note that we've kept the empty array resulting from the initial 0 at the bottom of the stack all the time, but empty arrays don't contribute anything to the output.

CJam, 57 56 52 bytes
I think this can be golfed a bit, but here goes:
q~ee_{W=2%},\{W=1>},]0ff=_W%]{~ff-{:z$1<~}%W+$W=}/e>

Input goes in like a CJam styled list, eg.
[1 0 0 0 0 3 0 0 0 0 2]

5

How it works:
The code is split in two parts:
Parsing the input into the lists A and B:
q~ee_{W=2%},\{W=1>},]0ff=_W%]
q~                               "Eval the input array";
  ee                             "Enumerate and prepend index with each element. For ex:
                                  [5 3 6]ee gives [[0 5] [1 3] [2 6]]";
    _{W=2%},                     "Make a copy and filter out elements with value 1 or 3";
            \{W=1>},             "On the original, filter elements with value 2 or 3";
                    ]            "Wrap stack in an array. Stack right now contains
                                  enumerated A and B in an array";
                     0ff=        "Get the index of the enumerated arrays. Stack is [A B]";
                         _W%     "Make a copy and swap order. Stack is now [A B] [B A]";
                            ]    "Wrap this in an array";

Performing the required actions on the two pairs of A and B:
{~ff-{:z$1<~}%W+$W=}/e>
{                  }/            "Run this loop for both the pairs, [A B] and [B A]"
 ~ff-                            "Unwrap [A B] and take difference of every pair";
     {      }%                   "For each row in the matrix difference";
      :z$                        "abs each term and then sort";
         1<~                     "Take only the first element of the array";
              W+                 "Add -1 to compensate for an empty array";
                $W=              "Take max";
                     e>          "Take max of the two maximums";

Try it online here

Lua, 235 bytes
Definitely not a winner, but at least a fun challenge.
A={}B={}c={}d={}m=math p=m.min q=m.max u=unpack for k=1,#arg do for h=0,1 do if
arg[k]/2^h%2>=1 then A[#A+1]=k for i=1,#B do l=m.abs(B[i]-k)d[i]=p(d[i]or
l,l)c[#A]=p(c[#A]or l,l)end end A,B=B,A c,d=d,c end end
print(q(q(-1,u(c)),u(d)))

Input works like so:
lua hausdorff.lua <space-separated-sequence>

...and here's a test script:
local testcase = arg[1] or 'hausdorff.lua'
print('testing '..testcase)
local function run(args)
    return function(expected)
        local result = tonumber(
            io.popen('lua.exe '..testcase..' '..args):read'*a':match'%S+')
        print(args..' -> '..expected..' :: '..result)
        assert(result == expected,
            ("for input %q expected %s but got %s"):format(
                args, expected, result))
    end
end
run''(-1)
run'0'(-1)
run'0 1 0'(-1)
run'2 0 0 2'(-1)
run'0 1 2 3'(1)
run'0 3 3 0 0 0 0 3'(0)
run'1 0 0 1 0 0 1 3 1'(7)
run'1 0 0 0 0 3 0 0 0 0 2'(5)
run'0 1 1 3 1 3 2 1 1 3 0 3'(2)
run'2 2 2 1 2 0 3 1 3 1 0 3'(3)
run'1 3 0 2 0 2 2 1 0 3 2 1 1 2 2'(2)
run'1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0'(4)

...produces...
testing hausdorff.lua
 -> -1 :: -1
0 -> -1 :: -1
0 1 0 -> -1 :: -1
2 0 0 2 -> -1 :: -1
0 1 2 3 -> 1 :: 1
0 3 3 0 0 0 0 3 -> 0 :: 0
1 0 0 1 0 0 1 3 1 -> 7 :: 7
1 0 0 0 0 3 0 0 0 0 2 -> 5 :: 5
0 1 1 3 1 3 2 1 1 3 0 3 -> 2 :: 2
2 2 2 1 2 0 3 1 3 1 0 3 -> 3 :: 3
1 3 0 2 0 2 2 1 0 3 2 1 1 2 2 -> 2 :: 2
1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0 -> 4 :: 4

Pyth, 43 40 39 38 bytes
J+m0yQQLq3.|Fb?eS.e&Yfy:J-kT+hkT0JyJ_1

My algorithm operates directly on the input string and never converts these number. It only calculate once a maximum and never a minimum.
Thanks to @isaacg for saving one byte.
Try it online: Pyth Compiler/Executor
Explanations:
First I'll insert a lot of zeros in front of the input.
          implicit: Q = input()
    yQ    powerset(Q)
  m0yQ    map each element of the powerset to 0 (creates 2^Q zeros, I said lots)
 +    Q   zeros + Q
J         assign to J

Then I define a helper function y, which tells if the indices of a list (like the input one) appear in both sets A and B. E.g. y([0, 1, 0, 0, 1, 1]) = False, but y([0, 1, 0, 2]) = y([3]) = True.
Lq3.|Fb
L          define a function y(b), which returns _
   .|Fb       fold b by bitwise or
 q3            == 3

Afterwards I first check if the result is -1.
?...yJ_1   print ... if numbers appear in both sets (`yJ`) else -1

Now to the interesting stuff:
  .e              J    map each pair k,Y in enumerate(J) to:
    &Y                   Y and ... (acts as 0 if Y == 0 else ...)
      f          0       find the first number T >= 0, where:
       y                    indices appear in both sets in the substring
        :J-kT+hkT           J[k-T:k+T+1]
eS                     sort and take last element (maximum)

Notice, that I will always find a number T, since I already know that indices appear in both sets in the list J. The number is maximal length(Q). This is also the reason for inserting the zeros. If there are at least length(Q) zeros inserted, k-T is always >= 0, which is necessary for the list slicing. So why do I insert 2^length(Q) zeros instead of length(Q) zeros? In the test-case [] I need at least 1 zero, otherwise yJ will return an error.

><Cab is the same as :Cba.

It's a good thing the test cases don't include a large input...

Mathematica, 88 bytes
Max[Min/@#,Min/@Thread@#,-1]/.∞->-1&@Outer[Abs[#-#2]&,p=Position;p[#,1|3],p[#,2|3],1]&

Very nice answer.  For more general finding of Hausdorff distance, one could use m=MaxValue;Max[m[RegionDistance[#[[1]],s],s\[Element]#[[2]]]/.m[__]->-1&/@{#,Reverse@c}]&  which can then be applied to multidimensional objects like so %@{Sphere[],Line[{{1,1,0},{3,3,3}}]}

Haskell, 145 126 124 bytes
s t x=[e|(e,i)<-zip[0..]x,t i]
d#e=maximum[minimum[abs$i-j|j<-e]|i<-d]
[]%_= -1
_%[]= -1
d%e=max(d#e)$e#d
f x=s(>1)x%s odd x

Test run:
*Main> map f [[], [0], [0,1,0], [2,0,0,2], [0,1,2,3],
              [0,3,3,0,0,0,0,3], [1,0,0,1,0,0,1,3,1],
              [1,0,0,0,0,3,0,0,0,0,2], [0,1,1,3,1,3,2,1,1,3,0,3],
              [2,2,2,1,2,0,3,1,3,1,0,3],
              [1,3,0,2,0,2,2,1,0,3,2,1,1,2,2],
              [1,0,1,1,2,0,1,2,3,1,0,0,0,1,2,0]]

[-1,-1,-1,-1,1,0,7,5,2,3,2,4]

s filters the natural numbers according to a predicate t and the input list x. # calculates the maximum distance of it's parameters d and e. % catches empty sets A or B or takes the final maximum of d#e and e#d. f is the main function which calls % with set A and B.
Edit: @Zgarb found lots of bytes to save; @ali0sha another 2. Thanks!

The mod 2 seems unnecessary. You may also benefit from not defining a and b explicitly.

you can save 2 bytes with []%_= -1 - but you beat my attempt hands down on this :)

Perl, 56 55
Added +2 for -lp.
The input list should be given on stdin without spaces, e.g.:
echo 1011201231000120 | perl -lp hausdorf.pl

hausdorf.pl:
s%%$z=$_&=$p|=$'|P.$p;$q+=!!y/12/3/%eg;$_=$z=~3?$q:-1

To support spaces between the elements of the input list just divide the final $q by 2 for a cost of 2 strokes

Python 2, 124
This definitely feels suboptimal. Oh well.
lambda a,E=enumerate:-min([1]+[~l*(n<3)for i,n in E(a)for l,_ in E(a)if{0}|set(n*a+n/3*[5])>{0,n}>=set(a[max(i-l,0):i-~l])])

APL (49)
{(⊂⍬)∊∆←(↓2 2⊤⍵)/¨⊂⍳⍴⍵:¯1⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆}

Testcases:
      ({(⊂⍬)∊∆←(↓2 2⊤⍵)/¨⊂⍳⍴⍵:¯1⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆} ¨ testcases) ,⍨ '→',⍨ ↑ ⍕¨testcases
                               → ¯1
0                              → ¯1
0 1 0                          → ¯1
2 0 0 2                        → ¯1
0 1 2 3                        →  1
0 3 3 0 0 0 0 3                →  0
1 0 0 1 0 0 1 3 1              →  7
1 0 0 0 0 3 0 0 0 0 2          →  5
0 1 1 3 1 3 2 1 1 3 0 3        →  2
2 2 2 1 2 0 3 1 3 1 0 3        →  3
1 3 0 2 0 2 2 1 0 3 2 1 1 2 2  →  2
1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0→  4

Explanation:

⍳⍴⍵: get a list of numbers from 1 to the length of the input list
↓2 2⊤⍵: for each value in the input list, get the first byte and the second byte
∆←(...)/⊂⍳⍴⍵: for both lists of bytes, select the corresponding values from ⍳⍴⍵. Store these in ∆.
(⊂⍬)∊∆...:¯1: if this list contains the empty list, return -1. Otherwise:
|∘.-/∆: get the absolute difference between every pair of values, giving a matrix
(+,⍉¨): get a rotated and a non-rotated copy of that matrix
{⌈/⌊/⍵}: for both matrices, get the maximum of the minimums of the rows
⌈/: then get the maximum of that

@Optimizer: I somehow managed to copy the test output from an earlier version which had a bug. The code itself was correct and still is. If you don't believe me, try here. (Note that you have to enter a one-element list as ,X, to distinguish it from the scalar X.)

Ah I see. lazy of me to not go to an online compiler and test..

Perl, 189 176 157B
Now with 500% more state.
use List::Util qw'max min';@I=<>;sub f{$n=($n%2)+1;map{$I[$_]&$n?$_:()}0..$#I}sub i{@t=f;max map{$b=$_;min map{abs$_-$b}@t}f}$r=max i,i;print defined$r?$r:-1

Legible:
use List::Util qw'max min';
@I=<>;
sub f {
    $n = ($n%2) + 1;
    map { $I[$_] & $n ? $_ : () } 0..$#I
}
sub i {
    @t = f;
    max map {
        $b = $_;
        min map { abs $_ - $b } @t
    } f
}
$r = max i,i;
print defined $r ? $r : -1

Example usage:
input
0
1
2
3

perl golf.pl < input

Clojure, 167 bytes
#(let[P apply F(fn[I](filter(fn[i](I(% i)))(range(count %))))A(F #{1 3})B(F #{2 3})d(fn[X Y](P min(for[x X](P max(for[y Y](P -(sort[x y])))))))](-(min(d A B)(d B A))))

There should be a shorter way... Is there?

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Smoothing out a list
You should write a program or function which takes a non-negative integer k and a sorted integer list Las input and outputs or returns a smoothed list M.
M is created from the ascending list L by inserting at most k integer elements while keeping the list sorted. The inserted integers should be chosen in a way that the maximum forward difference of M will be as small as possible. We will call this smallest value "smoothness".
The forward differences of the list -1 3 8 11 15 are 4 5 3 4 and the maximum forward difference is 5.
With 2 insertions the smoothness of 2 10 15 is 4 and a possible output is 2 6 10 11 15 with forward differences 4 4 1 4.
Input

A non-negative integer k.
An ascending integer list L with at least 2 elements.

Output

The ascending integer list M.
If multiple correct answers exists output exactly one of them (any one is sufficient).
Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Examples
Input (k, L) => A possible output and the maximum forward difference (which is not part of the output) in parentheses
0, 10 20 => 10 20 (10)

2, 1 10 => 1 4 7 10 (3)

2, 2 10 15 => 2 6 10 11 15 (4)

3, 2 10 15 => 2 5 8 10 12 15 (3)

5, 1 21 46 => 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 => 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 => 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 => 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 => -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 => 3 3 3 3 (0)

This is code-golf so the shortest entry wins.

Pyth, 28 27 bytes
S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Input given like:
3
[2, 10, 15]

Demonstration. Test harness.
Note: At the time the question was asked, there was a small bug in Pyth related to using rFd inside u, which I just fixed. The bug rendered it impossible to ever use F inside u, which was definitely not intended.
S+Qu?smt%hHrFdC,QtQ>GvzGhvz

                               Implicit:
                               z is the number of insertions, in string form.
                               Q is the input list.
              C,QtQ            Pairs of elements, e.g. [(2, 10), (10, 15)]
           rFd                 d = (a, b) -> range(a, b)
        %hH                    Take every H+1th element of that range
       t                       And throw out the first one.
      m                        Perform this process for each element pair
     s                         And combine the results into one list.

                               The above is a minimal set of additional elements
                               To reduce the maximal difference to H+1.

  u                     hvz    Repeat until the result stops changing, where
                               the prior result is G, H starts at 0 and
                               increases by 1 each repetition, and
                               G is initialized to eval(z)+1.
   ?               >GvzG       If not G[eval(z):], return G. In other words,
                               if the prior result was short enough, stop.
                               Also, this is always false on the initial call.
    smt%hHrFdC,QtQ             Otherwise, recalculate with H incremented.
S+Q                            Take the result, add the original list, and sort.

Here's a version which would have worked with the interpreter at the time the question was asked. It's 28 bytes, and works exactly the same way:
S+Qu?smt%hHr.udC,QtQ>GvzGhvz

Demonstration.
Git commit of the appropriate version, f6b40e62

I never thought of using rF<seq> to unpack two-element tuples.

@orlp It's a great trick, and I've used it way back in the day when u worked differently and e didn't exist, urGHd was shorter than rhd@d1. I'll put it on the Pyth tricks page.

You can shave off a character, you don't need the U.

@orlp Thanks. Actually, yvz fails when vz = 0, but hvz does the trick.

As the code wouldn't work with the Pyth version which was available when the question was asked I chose not to accept this solution. If you give an answer which doesn't rely on the bugfix, ping me and I will accept it.

@randomra Added a solution that works on the interpreter that existed when the question was asked.

Python 2, 104
def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)

Tries different maximum increments d, starting from 1 and counting up. Fills in gaps of each pair (p,x) of successive elements by taking every d'th number in the gap. If M is longer than the quota allows, recurses to try a higher d. Otherwise, returns a list of the added and original elements, sorted.
This does all the test cases without delay on my machine.

Did you try something like 1, 1000000000?

@edc65 That would take this algorithm really, really long, but I run of stack depth way before that.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Word fractal plotter
Iterated Function Systems
An Iterated Function System (IFS) is a method of constructing self-similar fractals. Each fractal is defined recursively as the union of several copies of itself, with each copy obtained by applying a transformation function to the whole. The functions are usually affine transformations of the form x↦Mx+b: i.e. a linear transformation such as a rotation, scaling or reflection, followed by a translation. Given a set of transformations, the fractal can then be obtained iteratively as follows: begin with a point (for example the origin) and repeatedly apply a randomly-selected transformation from the set. The sequence of points generated, which converges to the fixed point of the IFS, is then plotted.
The most famous example of an IFS is the Barnsley Fern. This is produced from four affine transformations, shown in the diagram below (taken from Wikipedia).

The affine transformations used in this questions involve only uniform scaling, rotation by a multiple of 90°, and translation. They can be implemented as follows, where n is the scale factor, θ is the rotation angle in radians and b is the translation in 'plot units' (e.g. pixels):

Seven-segment displays
A seven-segment display (SSD) is a cheap and simple electronic display device often used in clocks, meters and calculators to display decimal numerals. Though it wasn't designed to display letters, it is sometimes used to do so. The resulting alphabet is often ambiguous and sometimes unintuitive, but is sufficient for certain status messages (e.g. "nO dISC" or "gOOdbYE"). Below is one way to represent the 26 letters and 10 numerals on a seven-segment display.

Task
The aim of this challenge is to produce word fractals using IFSs and the SSD alphabet above.

The input is a string of multiple alphanumeric characters. The string may contain both upper and lower case letters, though the SSD alphabet is case insensitive. The program need not support punctuation or whitespace characters.
The output should be an IFS plot representing the string as rendered in the SSD alphabet above. Each lit segment in each character should correspond to an additional affine transformation mapping the bounding box of the rendered word to that of the segment. Horizontal segments should remain facing upwards, while vertical segments should face 'outwards' (i.e. left-side up on the left, right-side up on the right). The precise alignment/overlap of segments is left up to the solver, as long as the output is legible. For an example output showing one possible alignment, see below.
There should be a constant non-empty gap between the letters, to make the output legible.
The plot should contain enough points to be legible.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. The output should be drawn either to screen or to a file in any standard graphic format. As part of the answer you should include a screenshot of your output for the word "COdEgOLF". Standard code golf restrictions apply.
Example

Scoring
Shortest code (in bytes) wins. Standard rules apply.
Miscellania
For a good mathematical introduction to IFSs (including fractal compression) see these PDF lecture notes.
For a similar challenge concerning self-similar text see Words within words within words within words . . ..

Sigh, this could have been an [tag:ascii-art] instead...

@Optimizer: You mean like the linked challenge at the end? ASCII art works well with rewriting systems (like L-system) but I can't see how you would make it work for IFSs?

It looks like the majority of the code is needed for encoding the alphabet, so i expect it to turn into a competition of who can write a shorter version of exec(base64decode("VeryLongStringOfGibberish")). How about letting us declare a minimal representation with 7 bit per character (for example letters=[[1,1,1,1,1,1,0], [0,1,0,1,1,1,1],[1,1,0,1,1,0,1], ...[1,1,1,1,0,1,1]]) for "free"? that would result in more logic and less compression.

@DenDenDo Do you think so? I assumed that most people would go for 1 byte per letter plus some decoding logic, and that it would end up being about half compression half logic. I even thought it might be too 'boring' if the alphabet is passed in as a parameter. Is that not what you're finding?

If that was your intention from the beginning, then its fine of course. Its just my personal preference to have challenges focus on one aspect.

Python (518)
from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',[map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))
def T(A,C):y,x=A.shape;M=zeros((2*x-1,x+y));p=A[::-1].T;q=A.T[::-1];M[:y,:x]=C[0]*A;M[:x,:y]=C[1]*p;M[:x,-2*y:-y]=C[2]*q;M[x-1:x-1+y,:x]=C[3]*A;M[x-1:,:y]=C[4]*p;M[x-1:,-2*y:-y]=C[5]*q;M[2*x-1-y:2*x-1,:x]=C[6]*A;return M
def R(S,N):
 V=ones((1,3))
 for i in range(N):V=concatenate([T(V,D[C])for C in S],1)
 ion();imshow(V)

Call as R('CODEGOLF', 3)
first i make a dictionary that maps letters to their 7-bit SSD-representaion, where each bit stands for one bar, the .-corners are simply overwritten by the most recent bar
.000.
1   2
1   2
1   2
.333.
4   5
4   5
4   5
.666.

The function T(BaseArray, BooleanArray) makes a big empty array for one letter and puts rotated copies of BaseArray along the bars as indicated by BooleanArray. Finally R(String, N_levels) connects all the letters form the input and uses the result as BaseArray for the next iteration.
While technically correct, the result is quite ugly because of interpolation and the default colourmap

Unglofed
from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
           [map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))

def T(A,C):
    y,x = A.shape
    M = zeros((2*x-1,x+y))
    if C[0]: M[:y,           :x] = A
    if C[1]: M[:x,           :y] = A[::-1].T
    if C[2]: M[:x,      -2*y:-y] = A.T[::-1]
    if C[3]: M[x-y+y/2:x+y/2,:x] = A # middle bar shifted upwards by half thickness
    if C[4]: M[x-1:,         :y] = A[::-1].T
    if C[5]: M[x-1:,    -2*y:-y] = A.T[::-1]
    if C[6]: M[2*x-1-y:2*x-1,:x] = A
    return M

def R(S,N):
    V = ones((1,3))
    for i in range(N):
        V = concatenate([T(V, D[C]) for C in S], 1)
    imsave('%s_%s.png'%(S,N), V ,cmap='gray')

The initial seed V kinda controls the font on the deepest level. [1 1 1] make the smallest possible 3x5 letters

With V = ones((1,11)) you get long and thin letters

And with
V=array([[0,1,1,1,1,1,1,1,1,0],
         [1,0,0,0,0,0,0,0,0,1],
         [0,1,1,1,1,1,1,1,1,0]])

you can make hollow letters

You can save 6 bytes by using int(0xfcbf29fdbb3dbe245dea51ddbbfcf4335ad6edc3be7777b92bb6dd6bdf4bffb) instead of 7145037215283832782017591362181079009730769141301710950254702714880607436795

@mbomb007 Even better: int("e6960af16emx8y1bwvphxs0dtjuoss3z140s2kh98sq44ny0r",36)


text:
Determining the rotation of square given a list of points
In this challenge, you will be given a list of points.  These points lie on the perimeter of an imaginary square.  Your goal is to:

If possible, print out the rotation of the square, which will be a value from [0, 90) where 0 represents a square with lines vertical and horizontal.  The rotation is to be given in degrees counted counter-clockwise.
If the rotation of the square is ambiguous (such as only being given 2 points), print out "Unknown"
If creating a square given the points is impossible, print out "Impossible"

The points you are given are guaranteed to be unique, and are in no particular order.  You can use any format you wish to input the list, but for my examples, my points will be in the format x,y, and space separated.  The numbers are floating-point numbers, and you can assume they are within a range that your language can handle.  Your output should be accurate to at least 3 decimal places, and assume your language handles floating point numbers with perfect accuracy.
Here are some test cases (I have made most of these using whole numbers for easy visualizing, but your program should handle floating points):
Unknown:
0,0
0,0 1,0
0,0 1,0 0,1
0,0 1,0 0,1 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2

Impossible:
0,0 1,0 2,0 3,1 4,2
0,0 1,0 2,0 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2
2,0 0,1 2,2 0,3
0,0 2,1 0,2 2,2 -1,1

Possible (if not designated, should return 0):
0,0 1,0 2,0
0,0 0.3,0.3 0.6,0.6  (should return 45)
0,0 0.1,0.2 0.2,0.4  (should return appx 63.435 (the real value is arctan(2)))
0,0 0,1 2,1 2,2
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3

I may have missed some interesting test cases.  If so, please comment to add them.
This is code-golf, so the shortest-code wins!

Is there a minimum required accuracy? How far from the correct answer can the output be before it counts as wrong?

@trichoplax be as accurate as your language's implementation of floating-point number allows.

Does this mean that if there are 2 possible approaches and one gives a slightly more accurate result in your language, the most accurate approach must be used?

@trichoplax yes.

@NathanMerrill How will I (or anyone) know if a more accurate approach exists? I think it would make more sense to just require a fixed minimum accuracy, like 4 or 6 decimal places. Although I'm not even sure if the inaccuracies of floating-point representation of the input make many examples impossible. Maybe rational or integer input would have been better for that.

Hmm.  I'll just require minimum of 3 digit accuracy, and allow the assumption that their language has a perfect representation of floating points.

@NathanMerrill For example, I think SageMath has the ability to support arbitrary precision, so what would they use? That's why a fixed precision is necessary.

@mbomb007 whatever is necessary for 3 digit accuracy (assuming perfect representation)

@NathanMerrill I think this challenge is somewhat too 'big' for being a nice golf challenge especially considering that we have to use floating point numbers it is almost impossible to say whether it is 'not possible' or 'not accurate enough'. Using float often means we just can say something is true within an accuracy of some value. So my suggestion is that you just allow inputs that result in one exact square which would simplify the task and make the challenge more appealing=)

Could you post a more detailed explanation as how to form the square given the points, and how to find the rotation, because at the moment I'm lost...

@BetaDecay consider the 4th "unknown" example I have listed.  The 4 points form a perfect square.  Because we know the points are on the perimeter, we know that the square is either rotated 0 degrees (and the points are on the corners) or it is at 45 degrees (and the points are halfway on each of the sides).

@NathanMerrill Oh, wow sorry I didn't realise the inputs were coordinates.... Wow I feel stupid now hahaha

To be exact, in the 4th "Unknown" example the square can be rotated by any angle, not just 45° or 0°

Some cases might be ambiguous: see http://www.mathematische-basteleien.de/square.htm#Square%20inside%20a%20Square. Even with 3 or 4 points, some special cases might correspond to multiple squares.

What does "3 digits of precision" mean? Does it mean 1 decimal place as in 00.0 ... 89.9? 3 decimal places as in 0.000 ... 89.999? Because 3 significant figures is impossible for very small angles, you'd have to differentiate between 1E-n and 1.01E-n where n is an arbitrary number.

@steveverrill 3 decimal places.  If your angle is super small, rounding is certainly acceptable.

Rev 1: Ruby, 354 bytes
further golfing thanks to blutorange.
->a{t=s=Math::PI/18E4
d=r=c=0
a=a.map{|e|e-a[0]}
0.upto(36E4){|i|b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose
m,n=b
if n.min>=f=0
l=[m.max-x=m.min,n.max].max
a.each_index{|j|f+=((l-w=n[j])*(x+l-v=m[j])*(x-v)*w)**2}
(1E-9>q=f/l**8)&&(c>0&&(i-d)%9E4%89E3>1E3?c=9E9:0;c+=1;d=i)
q<t&&(r=i)&&t=q;end}
c<101&&a[1]?c<1?'impossible':r%9E4/1.0E3:'unknown'}

Ruby, 392 bytes
->(a){
s=Math::PI/18E4
t=1
d=r=c=0
a=a.map{|e|e-a[0]}
(0..36E4).each{|i|
b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose
m=b[0]
n=b[1]
x=m.min
if n.min>=0
l=[m.max-x,n.max].max
f=0
a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}
q=f/l**8
if q<1E-9
c>0&&(i-d)%9E4%89E3>1E3?(c=9E9):0
c+=1
d=i
end
if q<t
r=i
t=q
end
end
}
c>100||a.size<2?'unknown':c<1? 'impossible':r%9E4/1.0E3
}

The algorithm is as follows:
-Pick an arbitrary point (the first one) and move that to the origin (subtract the coordinates of this point from all points in the list.)
-Try all rotations of the square about the origin in 0.001 degree increments, through 360 degrees.
-For a given rotation, if all points are above the y axis, draw the smallest possible square around all the points, incorporating the lowest and leftmost point.
-Check if all points are on the edge. This is done with a soft calculation that takes each point, finds the squared distances from all edges, and multiplies them together. This gives a good fit rather than a yes/no answer. It is interpreted that a solution is found if this product divided by sidelength^8 is less than 1E-9. In practice this is less than a degree of tolerance.
-The best fit is taken mod 90 degrees and reported as the correct angle.
Currently the code returns a value of ambiguous if over 100 solutions are found (at 0.001 degree resolution. That's 0.1 degrees of tolerance.)
first fully working function, in test program
I left the resolution at 1/10th of the required resolution to make the speed reasonable. There is an error of 0.01 degress on the very last test case.
g=->(a){
 s=Math::PI/18000
 t=1
 d=r=-1
 c=0
 a=a.map{|e| e-a[0]}

 (0..36000).each{|i|
    b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose

    m=b[0]
    n=b[1]
    x=m.min

    if n.min>=0

       l=[m.max-x,n.max].max
       f=0
       a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}
       q=f/l**8

       if q<1E-9

         j=(i-d)%9000
         c>0&&j>100&&j<8900?(c=9E9):0
         c+=1
         d=i
       end

       if q<t
         r=i
         t=q
       end

     end
  }

 print "t=",t,"   r=",r,"     c=",c,"    d=",d,"\n"
 p c>100||a.size<2?'unknown':c<1? 'impossible':r%9000/100.0
}

#ambiguous
#g.call([Complex(0,0)])
#g.call([Complex(0,0),Complex(1,0)])
#g.call([Complex(0,0),Complex(1,0),Complex(0,1)])
#g.call([Complex(0,0),Complex(1,0),Complex(0,1),Complex(1,1)])
#g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2)])

#impossible
#g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(3,1),Complex(4,2)])
#g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(1,1)])
#g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2),Complex(2,2)])
#g.call([Complex(2,0),Complex(0,1),Complex(2,2),Complex(0,3)])
#g.call([Complex(0,0),Complex(2,1),Complex(0,2),Complex(2,2),Complex(-1,1)])

#possible
g.call([Complex(0,0),Complex(1,0),Complex(2,0)])
g.call([Complex(0,0),Complex(0.3,0.3),Complex(0.6,0.6)]) #(should return 45)
g.call([Complex(0,0),Complex(0.1,0.2),Complex(0.2,0.4)]) #(should return appx 63.435 (the real value is arctan(2)))
g.call([Complex(0,0),Complex(0,1),Complex(2,1),Complex(2,2)])
g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,4),Complex(2,0),Complex(2,4),Complex(4,1),Complex(4,3)])

golfed version, resolution compliant with spec, takes about a minute per call, in test program.
There's still a pesky error of 0.001 degrees on the last test case. Increasing resolution further would probably eliminate it.
g=->(a){                                                            #take an array of complex numbers as input
  s=Math::PI/18E4                                                   #step size PI/180000
  t=1                                                               #best fit found so far
  d=r=c=0                                                           #angles of (d) last valid result, (r) best fit; c= hit counter
  a=a.map{|e|e-a[0]}                                                #move shape so that first point coincides with origin
  (0..36E4).each{|i|                                                #0..360000
    b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose             #rotate each element by dividing by unit vector of angle i*s, convert to array...
    m=b[0]                                                          #...transpose array [[x1,y1]..[xn,yn]] to [[x1..xn],[y1..yn]]...
    n=b[1]                                                          #...and assign to variables m and n
    x=m.min                                                         #find leftmost point
    if n.min>=0                                                     #if all points are above x axis
       l=[m.max-x,n.max].max                                        #find the sidelength of smallest square in which they will fit
       f=0                                                          #f= accumulator for errors. For each point
       a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}   #...add to f the product of the squared distances from each side of the smallest square containing all points
       q=f/l**8                                                     #q= f normalized with respect to the sidelength.
       if q<1E-9                                                    #consider a hit if <1E-9
         c>0&&(i-d)%9E4%89E3>1E3?(c=9E9):0                          #if at least one point is already found, and the difference between this hit and the last exceeds+/-1 deg (mod 90), set c to a high value
         c+=1                                                       #increment hit count by 1 (this catches infinitely varible cases)
         d=i                                                        #store the current hit in d
       end
       if q<t                                                       #if current fit is better than previous one
        r=i                                                         #store the new angle
        t=q                                                         #and revise t to the new best fit.
       end
    end
  }
  c>100||a.size<2?'unknown':c<1? 'impossible':r%9E4/1.0E3           #calculate and return value, taking special care of case where single point given.
}
#ambiguous
puts g.call([Complex(0,0)])
puts g.call([Complex(0,0),Complex(1,0)])
puts g.call([Complex(0,0),Complex(1,0),Complex(0,1)])
puts g.call([Complex(0,0),Complex(1,0),Complex(0,1),Complex(1,1)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2)])

#impossible
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(3,1),Complex(4,2)])
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(1,1)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2),Complex(2,2)])
puts g.call([Complex(2,0),Complex(0,1),Complex(2,2),Complex(0,3)])
puts g.call([Complex(0,0),Complex(2,1),Complex(0,2),Complex(2,2),Complex(-1,1)])

#possible
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0)])
puts g.call([Complex(0,0),Complex(0.3,0.3),Complex(0.6,0.6)]) #(should return 45)
puts g.call([Complex(0,0),Complex(0.1,0.2),Complex(0.2,0.4)]) #(should return appx 63.435 (the real value is arctan(2)))
puts g.call([Complex(0,0),Complex(0,1),Complex(2,1),Complex(2,2)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,4),Complex(2,0),Complex(2,4),Complex(4,1),Complex(4,3)])

Note that for about 30% more code this algorithm could be adapted to work fast: it is obvious that in cases with a finite number of solutions, one of the edges lies flat along a a cube, so all we really have to try is those angles that correspond to each pair of vertices.  It would also be necessary to do a bit of wiggling to check there aren't there aren't infinitely many solutions.

I fixed the second test case, thank you

@NathanMerrill the revised case 0,0 1,0 2,0 1,2 is still possible for a square of diagonal 0,0...2,2. I've tried that, and also 0,0 1,0 2,0 1,1 (the latter is indeed impossible.) Another  point: do you consider it acceptable or unacceptable that my code returns impossible rather than unknown when only a single point is given? I'd appreciate an answer before I start golfing.

I meant to do 1,1.  Not sure how 1,2 got there.  Its not acceptable.

You should be able to get it down to at least 354 bytes like this: http://pastebin.com/jsgwMKQF

@blutorange thanks for the tips! I'm new to Ruby and have some difficulties golfing. I left a lot of if..ends because i have terrible trouble with nested ternary operators in Ruby. I see you got round that by using &&.

@blutorange actually there was a bug: the wrong results are returned for the possible cases. The second last line has to be q<t&&(r=i)&&t=q;end} . In other words () are required because of the order of operator precedence in Ruby. Adding the two bytes fixes the problems with the output. I then reduced the code by initialising t to s, so the length remains the same

Yes, you're right, sorry. That's why double-ckecking is good ; )

Perl
Hello, here is my humble soution.
Test cases are put in DATA stream at the bottom of the file.
The algorithm has grown by a try-error approach.
I admit that it is a broadly heuristic approach, but it is really fast: it resolves all the cases instantly.
I am aware there will be some bugs, but up to now it gives correct replies to all the test cases.
I am also aware that the shortest code wins, but I am sure this is among the shortest in the fastest meaning of the term.
Here is the algorithm

examine dots and for each segment between two dots record slope, length, x-intercept, y-intercept
find straight lines (i.e. three dots or two adjacent segments) and distinct possible slopes (say them rotations). Keep track of the longest segment available in each line.
find all the distances between a segment and a third point (this should be used to point 4). Keep track of minimum non-zero distance.
for any four dots (rougly a rectangle) find inner dots

Show solutions:
A. Say "Impossible" if there are one or more inner dots.
B. One Line:

In case of most of dots in a single line without inner dots, say "Possible"
In case of dots too close to line, say "Impossible"
C. Two lines:
Say "Possible" when there is only one possible rotation
Say "Impossible" when there are more than one rotation
D. No lines: find rotation that fits its 90° rotate segment
Say "Possible" if only one fits or as many as dots fit.
Say "Impossible" if more than one fits and not as many as dots
Say "Unknown" if as many as rotation fit.

Here is the code (all known bugs are resolved)
#!/usr/bin/perl
use strict ;
use warnings ;
my $PI = 4*atan2( 1, 1 ) ;
my $EPS = 0.000001 ;
while ( <DATA> ) {
    if ( /^\s*#/ ) { print ; next } # print comments
    chomp ;
    my @dot = split /\s+/ ;
    my $n = scalar @dot || next ; # skip empty lines

    # too few dots
    if ( $n < 3 ) {
        print "@dot : Unknown.\n" ;
        next
    }

    my %slop = () ; # segment --> its slope
    my %leng = () ; # segment --> its length
    my %x0   = () ; # segment --> its line's x-intercept
    my %y0   = () ; # segment --> its line's y-intercept
    my %side = () ; # slope   --> list of segments (with duplicates)

    # 1. examine dots
    for my $p (@dot) {
        my ($px,$py) = split /,/, $p ;
        for my $q (@dot) {
            next if $p eq $q ;
            next if defined ( $slop{ "$q $p" } ) ;
            my $segment_name = "$p $q" ;
            my ($qx,$qy) = split /,/, $q ;
            my $dx = $px - $qx ;
            my $dy = $py - $qy ;
            my $slope = "inf" ; $slope = $dy / $dx if abs($dx) > 0 ;
            my $sd = $dx*$dx+$dy*$dy ;
            my $x0 = ( $slope eq 'inf' ? $px : "nan" ) ;
            my $y0 = ( abs($slope) > 0 ? $px : "nan" ) ;
            $x0 = $qx - $qy / $slope if abs($slope) > 0 ;
            $y0 = $qy - $qx * $slope if $slope ne "inf" ;
            push @{ $side{ $slope } }, $segment_name ;
            $slop{ $segment_name } = $slope ;
            $leng{ $segment_name } = sqrt( $sd ) ;
            $x0{ $segment_name } = $x0 ;
            $y0{ $segment_name } = $y0 ;
        }
    }

    # 2. find straight lines and distinct possible slopes (rotation)
    my %line = () ;     # slope --> segment name
    my %rotation = () ; # slope --> slope itself
    my $a_rotation ;
    for my $slope ( keys %side ) {
        my %distinct = () ;
        for my $segment_name ( @{ $side{ $slope } } ) {
            $distinct{ $segment_name } = $slope ;
            my $rot = $slope eq 'inf' ? '0' : abs( $slope < 0 ? 1/$slope : $slope ) ;
            $rotation{ $rot } = $rot ;
            $a_rotation = $rot ;
        }
        for my $a_segm ( keys %distinct ) {
            for my $b_segm ( keys %distinct ) {
                next if $a_segm eq $b_segm ;
                # the two segment has to be adjacent
                my ($a1,$a2) = split / /, $a_segm;
                my ($b1,$b2) = split / /, $b_segm;
                next unless $a1 eq $b1 || $a1 eq $b2 || $a2 eq $b1 || $a2 eq $b2 ;
                # the two segment has to have same intercepts
                my $x0a = $x0{ $a_segm } ;
                my $x0b = $x0{ $b_segm } ;
                my $y0a = $y0{ $a_segm } ;
                my $y0b = $y0{ $b_segm } ;
                next unless $x0a eq $x0b && $y0a eq $y0b ;
                # keep the longest segment
                my $a_len = 0 ;
                $a_len = $leng{ $line{ $slope } } if defined( $line{ $slope } ) && defined( $leng{ $line{ $slope } } ) ;
                for my $segm ("$a1 $b1", "$a1 $b2", "$a2 $b1", "$a2 $b2",
                              "$b1 $a1", "$b2 $a1", "$b1 $a2", "$b2 $a2" ) {
                    next unless defined ( $leng{ $segm } ) ;
                    if ( $a_len < $leng{ $segm } ) {
                        $a_len = $leng{ $segm } ;
                        $line{ $slope } = $segm ;
                    }
                }
            }
        }
    }

    # 3. find distance between a segment and a third point
    my %distance = () ;            # segment-point --> distance
    my %distance_mani = () ;       # distance --> array of segment-point
    my %min_distance = () ;        # segment --> min distance to other dots
    for my $segment_name ( keys %slop ) {
        my $a = $slop{ $segment_name } ;
        my $b = -1 ;
        my $c = $y0{ $segment_name } ;
        my $z = $x0{ $segment_name } ;
        for my $p (@dot) {
            next if $segment_name =~ /$p/ ; # skip dots that are in the segment
            my ($px,$py) = split /,/, $p ;
            my $d = 0 ;
            if ( $a ne 'inf' ) {
                my $num = ($b * $py) + ($a * $px) + $c ;
                my $den = sqrt( $a*$a + $b*$b ) ;
                $d = abs( $num ) / $den ;
            }
            else {
                $d = abs( $px - $z );
            }
            $distance{ "$segment_name $p" } = $d ;
            push @{ $distance_mani{ $d } }, "$segment_name $p" ;
            if ( $d > 0 ) {
                $min_distance{ $segment_name } = $d if !defined ( $min_distance{ $segment_name } ) or $d < $min_distance{ $segment_name }
            }
        }
    }

    # 4. find inner dots: pick 4 dots to form a well shaped pseudo-rectangle
    #    and check for any other dot that is too close to all the 4 sides.
    my $fail = 0 ;
    RECTANGLE:
    for my $a ( @dot ) {
        for my $b ( @dot ) {
            next if $a eq $b ;
            my ($ax,$ay) = split /,/, $a ;
            my ($bx,$by) = split /,/, $b ;
            next if $ax > $bx || $ay > $by ;
            for my $c ( @dot ) {
                next if $c eq $a or $c eq $b ;
                my ($cx,$cy) = split /,/, $c ;
                next if $bx < $cx || $by > $cy ;
                for my $d ( @dot ) {
                    next if $d eq $a or $d eq $b or $d eq $c ;
                    my ($dx,$dy) = split /,/, $d ;
                    next if $cx < $dx || $cy < $dy  ;
                    next if $dx > $ax || $dy < $ay  ;
                    for my $e ( @dot ) {
                        next if $e eq $a or $e eq $b or $e eq $c or $e eq $d ;

                        my $abe = $distance{ "$a $b $e" } || $distance{ "$b $a $e" } || next ;
                        my $bce = $distance{ "$b $c $e" } || $distance{ "$c $b $e" } || next ;
                        my $cde = $distance{ "$c $d $e" } || $distance{ "$d $c $e" } || next ;
                        my $dae = $distance{ "$d $a $e" } || $distance{ "$a $d $e" } || next ;

                        my $abd = $distance{ "$a $b $d" } || $distance{ "$b $a $d" } || next ;
                        my $abc = $distance{ "$a $b $c" } || $distance{ "$b $a $c" } || next ;
                        my $bca = $distance{ "$b $c $a" } || $distance{ "$c $b $a" } || next ;
                        my $bcd = $distance{ "$b $c $d" } || $distance{ "$c $b $d" } || next ;
                        my $cdb = $distance{ "$c $d $b" } || $distance{ "$d $c $b" } || next ;
                        my $cda = $distance{ "$c $d $a" } || $distance{ "$d $c $a" } || next ;
                        my $dac = $distance{ "$d $a $c" } || $distance{ "$a $d $c" } || next ;
                        my $dab = $distance{ "$d $a $b" } || $distance{ "$a $d $b" } || next ;

                        if ( $abd > $abe && $abc > $abe &&
                             $bca > $bce && $bcd > $bce &&
                             $cdb > $cde && $cda > $cde &&
                             $dac > $dae && $dab > $dae) {
                            ## print "     $a $b $c $d --> $e\n";
                            $fail ++ ;
                            last RECTANGLE ;
                        }
                    }
                }
            }
        }
    }
    if ( $fail ) {
        print "@dot : Impossible.\n" ;
        next # DATA
    }

    my $m = scalar keys %rotation ; # how many distinct slopes
    my $r = scalar keys %line ; # how many lines i.e. >3 dots in a straight line

    print "@dot : " ;
    # most of dots lie in single line without inner dots
    if ( $r == 1 ) {
        $a_rotation = (keys %line)[0] ;
        my $a_segment = $line{ $a_rotation } ;
        my $a_dist = $min_distance{ $a_segment } || 0 ;
        if ( $a_dist && $a_dist < $leng{ $a_segment } ) {
            print "Impossible.\n"  ;
        }
        else {
            print "Possible. --> " . sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" ;
        }
        next # DATA
    }
    # two lines
    if ( $r == 2 ) {
        print "Impossible.\n" if $m > 1 ;
        print "Possible. --> " .
            sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" if $m == 1 ;  # never?
        next ; # DATA
    }
    # no lines
    if ( $r == 0 ) {
        # match between segment rotation and other side
        my $count = 0 ;
        my $numeros = 0 ;
        for my $slope ( keys %rotation ) {
            my $rot = $slope eq '0' ? 'inf' : -1/$slope ;
            if ( exists $side{ $rot } ) {
                $count++ ;
                my $u = scalar @{ $side{ $rot } } ;
                if ( $numeros < $u ) {
                    $numeros = $u ;
                    $a_rotation = $slope ;
                }
            }
        }
        print "Possible. --> " .
            sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" if $count < 2 or $count == $n ;
        print "Unknown.\n"    if $count == $m ;
        print "Impossible.\n"    if $count > 2 && $count != $n && $count != $m;
        next # DATA
    }
    # there are lines
    print "lines $r " ;
    my $shorter = 0 ;
    my $longer = 0 ;
    for my $slope ( keys %line ) {
        for my $dis ( keys %distance_mani ) {
            $shorter++ ;
            $longer++ ;
        }
    }
    print "ACK! WHAT IS THIS CASE! n=$n, m=$m, r=$r\n" ;
    1 ;
}

1;

__DATA__
# Unknown:

0,0
0,0 1,0
0,0 1,0 0,1
0,0 1,0 0,1 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2

# Impossible:

0,0 1,0 2,0 3,1 4,2
0,0 1,0 2,0 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2
2,0 0,1 2,2 0,3
0,0 2,1 0,2 2,2 -1,1

# Possible (if not designated, should return 0):

0,0 1,0 2,0 1,2
0,0 1,0 2,0 0.5,2.1

0,0 1,0 2,0
0,0 1,0 2,0 1,2
0,0 0.3,0.3 0.6,0.6
0,0 0.1,0.2 0.2,0.4
0,0 0,1 2,1 2,2
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3

And here is its ouptut
# Unknown:
0,0 : Unknown.
0,0 1,0 : Unknown.
0,0 1,0 0,1 : Unknown.
0,0 1,0 0,1 1,1 : Unknown.
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 : Unknown.
# Impossible:
0,0 1,0 2,0 3,1 4,2 : Impossible.
0,0 1,0 2,0 1,1 : Impossible.
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2 : Impossible.
2,0 0,1 2,2 0,3 : Impossible.
0,0 2,1 0,2 2,2 -1,1 : Impossible.
# Possible (if not designated, should return 0):
0,0 1,0 2,0 1,2 : Possible. --> 0.000 deg
0,0 1,0 2,0 0.5,2.1 : Possible. --> 0.000 deg
0,0 1,0 2,0 : Possible. --> 0.000 deg
0,0 1,0 2,0 1,2 : Possible. --> 0.000 deg
0,0 0.3,0.3 0.6,0.6 : Possible. --> 45.000 deg
0,0 0.1,0.2 0.2,0.4 : Possible. --> 63.435 deg
0,0 0,1 2,1 2,2 : Possible. --> 0.000 deg
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3 : Possible. --> 0.000 deg

Regards.
Matteo.

Here is the first bug: your case  0,0 1,0 2,0 1,1 (Impossible) is said "Possible. --> 0.000 deg" by my script. I have to fix

I really like this solution.  Don't worry about the code golf too much, that's not what the challenge is really about, and it isn't necessarily the person that will get the bounty.

Thank you Nathan.The output shows much more information: these are for debug purpose and I left them intentionally to be able to fix

Second bug: a spurious "Impossible. (no lines) n=8, m=6, r=0 c=6" is written just after the correct answer "0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 : Unknown. (no lines) n=8, m=6, r=0 c=6".

Two bugs fixed: all cases now run fine.

You should fix your output then :)

Ok. I will run my script without all these junkyard comments...

@NathanMerrill: done.