6
$\begingroup$

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 !

$\endgroup$
  • 1
    $\begingroup$ @lois6b so it is False (F) $\endgroup$ – Jamal Senjaya Sep 20 '16 at 8:08
  • 2
    $\begingroup$ I' dont get it, in your example, the 3 is only surrounded by 2 trues, and the 0 is surrounded by 2 trues...Am I missing something? $\endgroup$ – Mario Garcia Sep 20 '16 at 11:01
  • 1
    $\begingroup$ Does "surrounded by" mean among the four neighbours north, south, east and west, or among the eight neighbours including north-east, south-west etc.? (I'm assuming the latter because it seems impossible otherwise, but it would be helpful to clarify in the question.) $\endgroup$ – Nathaniel Sep 20 '16 at 12:10
  • 1
    $\begingroup$ Thanks - you should edit that into the question so people don't have to read through the comments to find out. $\endgroup$ – Nathaniel Sep 20 '16 at 13:55
  • 1
    $\begingroup$ By the way, I'm curious: did you intend this to be solvable without a computer? I can think of some fun ways to solve it algorithmically, but I can't see a way to get anywhere with pen and paper. $\endgroup$ – Nathaniel Sep 20 '16 at 13:56
1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ what process did you follow? $\endgroup$ – lois6b Sep 20 '16 at 9:33
  • $\begingroup$ You mean you don't see it instantly? :o $\endgroup$ – RobAu Sep 20 '16 at 15:07
6
$\begingroup$

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();
$\endgroup$
  • $\begingroup$ This method is highly inefficient for larger arrays, I think already starting from 6x6. The problem with your approach is that you are re-evaluating already dead cases over-and-over again: indeed, if something is wrong in the upper left corner, then any changes in the lower right part not going to fix it. $\endgroup$ – Matsmath Sep 20 '16 at 9:39
  • 1
    $\begingroup$ I totally agree with you. This is a quick an dirty way of solving it. I wrote it just to get it out there. Thanks for the code review. $\endgroup$ – Marius Sep 20 '16 at 10:01
  • $\begingroup$ In my defense, I said that this is the brute force approach since there are not that many combinations. for 6x6 grids the number of combinations increases a lot and this may not be a good approach. $\endgroup$ – Marius Sep 20 '16 at 10:48
4
$\begingroup$

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]
$\endgroup$
  • 1
    $\begingroup$ Seem to be quite a challenge to adapt this to the 6x6 case. $\endgroup$ – Matsmath Sep 20 '16 at 10:20
  • $\begingroup$ 1 more request, I will create it tomorrow $\endgroup$ – Jamal Senjaya Sep 20 '16 at 10:56
  • 1
    $\begingroup$ So how many solutions were there? $\endgroup$ – yitzih Sep 20 '16 at 15:27
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Puzzling.SE! Take the tour, you will earn a badge. $\endgroup$ – Matsmath Sep 21 '16 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.