Minesweeper

Description
In this challenge you will come up with an algorithm to solve the classic game of Minesweeper. The brute force approach is impractical since the search space size is anywhere around 1020 to 10100 depending on the situation, you'll have to come up with something clever.

Formal Inputs & Outputs
Input description
The current field state where each character represents one field. Flags will not be used. Hidden/unknown fields are denoted with a '?'.
'Zero-fields' with no mines around are denoted with a space.

Example for a 9x9 board:

    1????
    1????
    111??
      1??
1211  1??
???21 1??
????211??
?????????
?????????
Output description
A list of zero-based row and column coordinates for the fields that you have determined to be SAFE. For the above input example this would be:

0 5
1 6
1 7
2 7
3 7
5 1
5 7
6 2
6 7
The list does not need to be ordered.

Challenge input
As suggested by /u/wutaki, this input is a greater challenge then the original input

??????
???2??
???4??
?2??2?
?2222?
?1  1?
Notes/Hints
If you have no idea where to start I suggest you play the game for a while and try to formalize your strategy.

Minesweeper is a game of both logic and luck. Sometimes it is impossible to find free fields through logic. The right output would then be an empty list. Your algorithm does not need to guess.

Solution
in C

#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define MAX_SIZE 256
static char grid[MAX_SIZE][MAX_SIZE];

static int
count_or_assign(int x, int y, char c, char a)
{
    static const uint16_t dirs[] = {
        0xffff, 0xff00, 0xff01, 0x00ff, 0x0001, 0x01ff, 0x0100, 0x0101
    };
    unsigned count = 0;
    for (unsigned i = 0; i < 8; i++) {
        int8_t dx = dirs[i] & 0xff;
        int8_t dy = dirs[i] >> 8;
        if (x + dx >= 0 && y + dy >= 0) {
            if (grid[y + dy][x + dx] == c) {
                count++;
                if (a)
                    grid[y + dy][x + dx] = a;
            }
        }
    }
    return count;
}

static int
deduce(int x, int y)
{
    char c = grid[y][x];
    if (c >= '0' && c <= '9') {
        int n = c - '0';
        int unknown = count_or_assign(x, y, '?', 0);
        int bombs = count_or_assign(x, y, '*', 0);
        if (unknown == n - bombs)
            return count_or_assign(x, y, '?', '*');
        if (bombs == n)
            return count_or_assign(x, y, '?', 'S');
    }
    return 0;
}

int
main(void)
{
    int height = 0;
    while (fgets(grid[height], sizeof(grid[0]), stdin))
        height++;

    int changes;
    do {
        changes = 0;
        for (int y = 0; y < height; y++)
            for (int x = 0; x < MAX_SIZE; x++)
                changes += deduce(x, y);
    } while (changes);

    for (int y = 0; y < height; y++)
        for (int x = 0; x < MAX_SIZE - 1; x++)
            if (grid[y][x] == 'S')
                printf("%d %d\n", y, x);
    return 0;
}