5x5 statement table

Question

Statement table.

3 2 1 4 1
2 3 3 3 3
3 4 6 4 4
2 3 4 4 3
1 1 2 4 3

Above 5x5 table contains numbers.
A number at each cell represent a statement.

x : This cell is surrounded by (among 8 neighbour) x True statements.

So if the number is 3 means the cell is surrounded by 3 True statement
We can say all statemets are false, but this is not what I want.
Some statements are true and some are not.

Create another 5x5 table with boolean (T/F) input,
to show which statements are true, and which statements are false.

example for 2x2 table.

1 3    ->  T F
0 1        F T

I have checked there is only 1 solution.
Find the solution !

Answer 1

The truth table you seek is as follows (credits to these beautiful formatting goes to @humn):

          truth               true            false counts
          table              counts            ( . = T )

        F F T F T              1   1           3 2 . 4 .
        T T F F T          2 3     3           . . 3 3 .
        F T F T T            4   4 4           3 . 6 . .
        T T F T T          2 3   4 3           . . 4 . .
        F F T F F              2               1 1 . 4 3

You solve these kind of problems by computers (as you can see some code in other posts). The basic idea is

depth-first search with pruning (what is colloquially called as backtracking, but I personally dislike this phrase as it is really shallow). You fill out the upper left 2x2 block with T and F letters in one way, and you check if the upper 1x1 block contains a T, then the number of T positions in the surrounding 3 cells matches the given count (provided by the OP). If it is happens to be an F, then you check if the number of surrounding T positions does not agree with this number. If something is wrong, then you discard this particular 2x2 block, and take a new one. If everything is fine, then you move on to the next cell, and fill out the T/F values at positions (1,3) and (2,3), and do the same kind of test for the entry at position (1,2). If everything is OK, then you move on to the next cell, otherwise you step back. I do not wish to post lengthy (let alone inelegant, or inefficient) code as it is extremely unlikely that anyone would like to browse it.

I would also like to remark that

this problem can also be formulated as a search for a fixpoint.

Answer 2

I know this has already been answered, but I've been working on it before the answer appeared so I just want to leave this here.
Since there are $2^{25} - 1$ combinations (excluding the all false combination) I thought of brute forcing it.

Solution: (0=F, 1=T)

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

The idea:

Every combination can be written a s 25 digit binary number by concatenating the rows of the matrix.

My weapon of choice is PHP.

<?php
set_time_limit(0);
class TrueOrFalse
{
    protected $setup;
    protected $size;
    protected $around = array();
    //set the setup matrix.
    public function __construct($setup)
    {
        $this->setup = $setup;
        $this->size = count($setup);
    }
    //get the neighbors of a cell 
    protected function getSuroundings($x, $y)
    {
        if (!isset($this->around[$x][$y])) {
            $around = array();
            for ($i=-1; $i<=1; $i++) {
                for ($j=-1; $j<=1; $j++) {
                    if ($i == 0 && $j==0) {
                        continue;
                    }
                    if ($x+$i >=0 && $y+$j >=0 &&
                        $x+$i<$this->size && $y+$j<$this->size) {
                        $around[] = array($x+$i, $y+$j);
                    }
                }
            }
            $this->around[$x][$y] = $around;
        }
        return $this->around[$x][$y];
    }
    //generate a matrix with 0's an 1's based on a base 2 number
    protected function generateMatrix($number)
    {
        $matrix = array();
        $binary = base_convert($number, 10, 2);
        $string = str_pad($binary, $this->size * $this->size, '0', STR_PAD_LEFT);
        for ($i=0;$i<strlen($string);$i++) {
            $x = (int)($i/$this->size);
            $y = $i%$this->size;
            if (!isset($matrix[$x])) {
                $matrix[$x] = array();
            }
            $matrix[$x][$y] = $string[$i];
        }
        return $matrix;
    }
    //check the validity of the TF matrix
    protected function checkMatrix($matrix)
    {
        for ($x = 0;$x<$this->size;$x++) {
            for ($y = 0;$y<$this->size;$y++) {
                $around = $this->getSuroundings($x, $y);
                $sum = 0;
                foreach ($around as $point) {
                    $sum += $matrix[$point[0]][$point[1]];
                }
                if (($sum != $this->setup[$x][$y] && $matrix[$x][$y] == 1) ||
                    ($sum == $this->setup[$x][$y] && $matrix[$x][$y] == 0)) {
                    return false;
                }
            }
        }
        return true;
    }
    //go through all the possible numbers between 1 and 2^25 until we find a solution
    public function run()
    {
        for ($i = 1; $i<pow(2, $this->size * $this->size) - 1; $i++) {
            $matrix = $this->generateMatrix($i);
            if ($this->checkMatrix($matrix)) {
                echo "<pre>"; print_r($matrix);exit;
            }
        }
    }
}
$setup = array(
    array(3, 2, 1, 4, 1),
    array(2, 3, 3, 3, 3),
    array(3, 4, 6, 4, 4),
    array(2, 3, 4, 4, 3),
    array(1, 1, 2, 4, 3),
);
$tf = new TrueOrFalse($setup);
$tf->run();

Answer 3

After creating the puzzle,
I use Haskell to check how many solution it have.
This code is very effective, it find the answer less than a second.

cek angka logic himp = if logic == 1
                     then angka == sum himp
                     else angka /= sum himp


findit =  [[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y]|
       let hmp = [0,1],
       let aa = 3, let bb = 2, let cc = 1, let dd = 4, let ee = 1,
       let ff = 2, let gg = 3, let hh = 3, let ii = 3, let jj = 3,
       let kk = 3, let ll = 4, let mm = 6, let nn = 4, let oo = 4,
       let pp = 2, let qq = 3, let rr = 4, let ss = 4, let tt = 3,
       let uu = 1, let vv = 1, let ww = 2, let xx = 4, let yy = 3,
       a<-hmp, b<-hmp,f<-hmp,g<-hmp,
       cek aa a [b,f,g],
       c<-hmp,h<-hmp,
       cek bb b [a,f,g,h,c],
       d<-hmp, i <-hmp,
       cek cc c [b,g,h,i,d],
       e<-hmp, j<-hmp,
       cek dd d [c,h,i,e,j],
       cek ee e [d,i,j],
       k<-hmp,l<-hmp,
       cek ff f [a,b,g,k,l],
       m<-hmp,
       cek gg g [a,b,c,f,h,k,l,m],
       n<-hmp,
       cek hh h [b,c,d,g,i,l,m,n],
       o<-hmp,
       cek ii i [c,d,e,h,j,m,n,o],
       cek jj j [d,e,i,n,o],
       p<-hmp,q<-hmp,
       cek kk k [f,g,l,p,q],
       r<-hmp,
       cek ll l [f,g,h,k,m,p,q,r],
       s<-hmp,
       cek mm m [g,h,i,l,n,q,r,s],
       t<-hmp,
       cek nn n [h,i,j,m,o,r,s,t],
       cek oo o [i,j,n,s,t],
       u<-hmp,v<-hmp,
       cek pp p [k,l,q,u,v],
       w<-hmp,
       cek qq q [k,l,m,p,r,u,v,w],
       x<-hmp,
       cek rr r [l,m,n,q,s,v,w,x],
       y<-hmp,
       cek ss s [m,n,o,r,t,w,x,y],
       cek tt t [n,o,s,x,y],
       cek uu u [p,q,v],
       cek vv v [p,q,r,u,w],
       cek ww w [q,r,s,v,x],
       cek xx x [r,s,t,w,y],
       cek yy y [s,t,x],
       True]

Answer 4

I decided that it would be more fun to take a pen/paper approach. It wasn't as fun to type out, but I thought some of you might like it.

My method was to choose a value which, when assumed true, would limit the number of subsequent possible cases. From there, I would either be able to prove a value is false, or would have to make another assumption.

The shortest case being this:

Assume (0,0) All of its
is true: neighbors
. must be true

T 2 ... T T ...
2 3 ... T T ...
. . ... . . ...

Neither (0,1) nor (1,0) can have more than 2 true neighbors.
Therefore, (0,0) must be false.

Using the same method:

Assume (0,4) One of its neighbors
is true: must be true. Assume
. (0,3) is true:

. 4 T . T T
. 3 3 . F F
. . . . . .

(0,3) must have at least 4 true neighbors so it must be false (if (0,4) is true).
Now, I'm not going to draw it all out, but if you assume (3,1) to be true and follow the same steps, you end with a contradiction and learn that (3,1) is false when (4,0) is true. So, if (4,0) is true, then (4,1) must also be true. This forces its two lower neighbors to be true which, in turn, force their two neighbors to be true. Cross out neighbors of values that cannot be true. The '4' at (3,3) needs another true neighbor, so (2,4) is true. This gets us to the following:

F 2 1 F T
2 3 F F T
3 4 F T T
2 3 F T T
1 1 T F F

If you assume the '1' at (1,4) to be true, you find the '4' cannot be true which snowballs into the whole thing being untrue. So, (1,4) is false which forces the '3' at (1,3) to be true. From here you could pretty much do trial and error.

I'm sure there are many paths to use to get the same result, but this was the best I could find.