248. Mine Field

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to find the mines. There is a 9 by 9 minefield, in which each cell could have a mine. Now you are given for each cell, the sum of mines of all (up to eight) neighboring cells and the cell itself, and you need to determine the locations of all mines. For example, if you know the sum of number of mines as follows.

1 1 2 1 1 1 1 1 0
2 2 3 2 2 3 2 2 0
2 2 3 2 2 3 3 3 1
2 3 2 2 1 2 3 3 2
2 3 1 2 2 3 5 4 3
4 6 3 3 3 4 5 4 3
5 7 4 3 3 4 4 4 3
6 9 6 4 2 2 1 3 3
4 6 4 3 1 1 0 2 2

Then the locations of mines will be like the following.

0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 1 0 0
0 1 0 0 1 0 1 0 0
0 0 0 0 0 0 0 1 0
1 0 1 0 0 0 0 1 0
1 0 0 0 1 1 1 1 0
1 1 1 0 0 1 0 0 1
1 1 1 0 0 0 0 0 1
1 1 1 0 1 0 0 0 1

Note that we do not guarantee that there are solutions. If there are no solution then output "no solution\n". If there are multiple solutions, output the one that has the minimum value, i.e., if you consider the solution as an 81 bit unsigned integer, where bits are taken from top to bottom, from left to right.

Sample input

1 1 2 1 1 1 1 1 0
2 2 3 2 2 3 2 2 0
2 2 3 2 2 3 3 3 1
2 3 2 2 1 2 3 3 2
2 3 1 2 2 3 5 4 3
4 6 3 3 3 4 5 4 3
5 7 4 3 3 4 4 4 3
6 9 6 4 2 2 1 3 3
4 6 4 3 1 1 0 2 2

Sample output

0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 1 0 0
0 1 0 0 1 0 1 0 0
0 0 0 0 0 0 0 1 0
1 0 1 0 0 0 0 1 0
1 0 0 0 1 1 1 1 0
1 1 1 0 0 1 0 0 1
1 1 1 0 0 0 0 0 1
1 1 1 0 1 0 0 0 1

Discussion