Tuesday, January 2, 2018

logical deduction - 5x5 statement table


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



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.



No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...