wu :: forums « wu :: forums - Execution strategy in a matrix, with constraints » Welcome, Guest. Please Login or Register. Nov 28th, 2024, 9:14pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    hard (Moderators: Eigenray, Icarus, Grimbal, SMQ, ThudnBlunder, towr, william wu)    Execution strategy in a matrix, with constraints « Previous topic | Next topic » Pages: 1 2  Reply Notify of replies Send Topic Print    Author  Topic: Execution strategy in a matrix, with constraints  (Read 3224 times) yappuzzler Guest Execution strategy in a matrix, with constraints   « on: May 1st, 2005, 10:35pm » Quote Modify Remove hi,     This one is an interesting problem, i couldnt locate a solution on the forum. apologies if it is redundant.   There is a 5X5 matrix   1   2   3   4   5 6   7   8   9   10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25   Assume each number represents a prisoner to be executed. These guys are superhumans, so if u kill any person, his neighbours(only linear, not diagonal neighbours) are also affected. So if u kill any prisoner, the adjacent neighbours who are alive, will also die, and those who are dead will come to life. Find algorithm to give different permutation in which to carry out execution so that each one is executed. U can execute them in any order.U can also try minimizing the number of executions, required to effectively kill all. IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Execution strategy in a matrix, with constrain   « Reply #1 on: May 2nd, 2005, 3:51am » Quote Modify Can you kill a dead person?  If yes, do you unkill him (just the way neighbours get unkilled)? IP Logged yapppuzzler Guest Re: Execution strategy in a matrix, with constrain   « Reply #2 on: May 2nd, 2005, 4:43am » Quote Modify Remove No u cannot kill a dead person.Nor can u explicitly unkill someone. A dead peron may come to life only as an effect of the neighbours killing. IP Logged yappuzzler Guest Re: Execution strategy in a matrix, with constrain   « Reply #3 on: May 2nd, 2005, 5:16am » Quote Modify Remove to explain the same problem in an easier way..   T-> TRUE F-> FALSE assume there is a boolean array b[5][5] which is     T, T, T, T, T T, T, T, T, T T, T, T, T, T T, T, T, T, T T, T, T, T, T   U have to convert it to the array below.   The constraints are   F, F, F, F, F F, F, F, F, F F, F, F, F, F F, F, F, F, F F, F, F, F, F   -> U can Toggle any element b[i][j] from T to F, but not F back to T   -> All adjacent neighbours of the element also get toggled along with it(exclude diagonal neighbours and do not assume that the matrix wraps around... i:e element b[0][0] is not the neighbour of b[0][4])   -> This is the function to toggle an element   toggle(i,j){     if(b[i][j]=false;   return; // cannot toggle already false element     b[i][j]=false;     // conditions to check boundary conditions   if(i<5)      b[i+1][j]=!b[i+1][j];   if(i>0)      b[i-1][j]=!b[i-1][j];   if(j>5)      b[i][j+1]=!b[i][j+1];   if(j<0)      b[i][j-1]=!b[i][j-1];   }   So all one has to do is to find a set of i,j pairs on which u call toggle(i,j) to convert the initial array to final array.   This is exactly the above problem put down mathematically. IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Execution strategy in a matrix, with constrain   « Reply #4 on: May 2nd, 2005, 5:47am » Quote Modify This should do the trick.   1, 7, 9, 13, 15, 17, 19, 23, 25, 2, 6, 10, 14, 18, 22.   It's not really an algorithm, but since there is no variable in the problem, printing the known solution is just as good as any algorithm. IP Logged yappuzzler Guest Re: Execution strategy in a matrix, with constrain   « Reply #5 on: May 2nd, 2005, 6:14am » Quote Modify Remove works,   but i am looking for a non brute force algorithm which could work that out, and other solutions using som logic.Since the problem has more than one solutions. IP Logged asterex Guest Re: Execution strategy in a matrix, with constrain   « Reply #6 on: May 2nd, 2005, 1:15pm » Quote Modify Remove Another way to state it is to create an array of ones and zeros in which each element, when considered with its four neighbors, gives you an odd number of ones. For a 3x3 array there is one solution 101 010 101 For 4x4, every top row permutation gives a solution. For 5x5 there is only one solution if you eliminate rotations and mirror images. 9, 11 ,14 ,16 ,17 all have multiple solutions. The only solution for other numbers start out as   101101 1101011 11000011 1010000101 101000000101 1101011101011 101100101001101   I don't see any way you could find these things other than brute force. IP Logged asterex Guest Re: Execution strategy in a matrix, with constrain   « Reply #7 on: May 2nd, 2005, 1:37pm » Quote Modify Remove I went as high as 21. It seems strange that there's always at least one solution, and if there's more than one it's always a power of 4 (counting all rotations separately). 4 has 16 solutions 5 has 4 9 has 256 11 has 64 14 has 16 16 has 256 17 has 4 19 has 65536 The fact that the rest all have exactly one solution makes me think there should be some forced way to generate it, but I can't imagine how. IP Logged Deedlit Senior Riddler     Posts: 476 Re: Execution strategy in a matrix, with constrain   « Reply #8 on: May 2nd, 2005, 9:02pm » Quote Modify Now, this is quite interesting!  Note that the function mapping the matrix of who gets shot, to the matrix of who is finally killed, is a group endomorphism on (Z2)n^2.  So every preimage has the same size as the kernel, which must be a power of 2.  I don't see why it should be a power of 4, though.   I don't see the pattern, but I noticed we have new "records" at 4, 9 and 19 - maybe 39 gives 232 possibilities?   Also, I would be intereted in seeing your code - a complete brute force search is of course impossible for the larger values! IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Execution strategy in a matrix, with constrain   « Reply #9 on: May 3rd, 2005, 2:52am » Quote Modify Here's a java-applet implementing almost the same game (but without the restriction you can only toggle one color)   http://grid.let.rug.nl/~vannoord/bertspel/java.html   Years ago I wrote a program to solve that version, but I think it was just brute force. « Last Edit: May 3rd, 2005, 3:11am by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Execution strategy in a matrix, with constrain   « Reply #10 on: May 3rd, 2005, 2:56am » Quote Modify I hacked a javascript simulation of the game according to specifications.  You can not unkill the dead.   http://florian.net/puzzle/killinggame/ IP Logged SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Execution strategy in a matrix, with constrain   « Reply #11 on: May 3rd, 2005, 5:52am » Quote Modify asterex can correct me if I'm wrong, but I think I see how the search code must work:   Assign each cell a binary value indicating whether or not to toggle that cell as part of a solution.  Now construct a matrix where every set of a cell and its up-to-four neighbors contains an odd number of ones.  Toggling all the cells with a one will be a solution as it is gurarnteed to toggle every cell an odd number of times (and since each cell with a one must have an even number of neighbors it is guaranteed to be togglable at some point in the solution sequence.)   To find all possible such N x N matrices it is only necessary to test 2N possibilities rather than 2N*N -- any edge uniquely determines the entire matrix.   So, I believe, asterex's program loops through all possible bainary values for the top row of the matrix, and for each one attempts to construct a complete matrix of binary values, noting how many times it succedes and how many times it encounters a contradiction.  The success numbers are what he has given.   I'm going to try to extend the search to higher N's and eliminate rotations and mirrors and report back later.     --SMQ IP Logged --SMQ yappuzzler Guest Re: Execution strategy in a matrix, with constrain   « Reply #12 on: May 3rd, 2005, 6:39am » Quote Modify Remove asterx,     do u mean to say, that there is a possible solution without wrapping over the matrix. The pattern which u and SQM are talking about, of being surrounded by odd number of ones including itself, does not seem to be applying on the solution posted by grimbal earlier 1, 7, 9, 13, 15, 17, 19, 23, 25, 2, 6, 10, 14, 18, 22.   Or am i missing something. If possible attach code IP Logged yappuzzler Guest Re: Execution strategy in a matrix, with constrain   « Reply #13 on: May 3rd, 2005, 7:05am » Quote Modify Remove Sorry first of all to asterex and SMQ for misspelling there names.   and sorry, i dint observe, the solution above does satisfy the criteria. IP Logged asterex Guest Re: Execution strategy in a matrix, with constrain   « Reply #14 on: May 3rd, 2005, 7:32am » Quote Modify Remove SMQ has described my program pretty well. I won't post it because it's a pretty ugly, down and dirty program in basic, and there's nothing special or complicated in it. The power of 4 seems to derive from the fact that in every grid that has one solution it's completely symmetrical. Every multiple solution has only non-symnmetrical patterns. So they're all divisible by 4. But I can't explain the powers of 4. Maybe I should print out the 4 different patterns of the 14x14 grid to see if they are somehow related. IP Logged asterex Guest Re: Execution strategy in a matrix, with constrain   « Reply #15 on: May 3rd, 2005, 8:03am » Quote Modify Remove I meant to say the multiple solution patterns are symmetrical, but not completely so. It turns out that 14x14 has 5 solutions (2 of them had an extra axis of symmetry   What I noticed immediately is that the fifth and tenth line of every one is exactly the same, all 0's except for where the lines intersect. That splits up the region into 4x4 grids that are completely surrounded by 0's.   The 4x4 solutions are inserted into those sectors. THere is still a restraint on how they cross the line of zeros, but it may help explain the power of 4. IP Logged asterex Guest Re: Execution strategy in a matrix, with constrain   « Reply #16 on: May 3rd, 2005, 9:52am » Quote Modify Remove One final observation before I go to work. Every grid that I looked at which has only a single solution, other than 8x8, is formed by inserting all 1's across the two diagonals.   Don't ask me why it works or whether it implies that every grid will have a solution. The diagonals are not enough to force a complete solution the way a filled top line does. IP Logged SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Execution strategy in a matrix, with constrain   deadmatrix1.txt « Reply #17 on: May 3rd, 2005, 10:08am » Quote Modify Here's a quick summary through N = 32 based on my optimized C implementation of asterex's algorithm:   N = 1: 1 execution N = 2: 4 executions N = 3: 5 executions N = 4   least: 4 executions, 2 solutions, 1 unique   total: 16 solutions, 5 unique N = 5: 15 executions, 4 solutions, 1 unique N = 6: 28 executions N = 7: 33 executions N = 8: 40 executions N = 9   least: 25 executions, 6 solutions, 2 unique   total: 256 solutions, 43 unique N = 10: 44 executions N = 11   least: 55 executions, 20 solutions, 3 unique   total: 64 solutions, 10 unique N = 12: 72 executions N = 13: 105 executions N = 14   least: 56 executions, 2 solutions, 1 unique   total: 16 solutions, 5 unique N = 15: 117 executions N = 16   least: 104 executions, 2 solutions, 1 unique   total: 256 solutions, 43 unique N = 17: least: 147 executions, 4 solutions, 1 unique N = 18: 188 executions N = 19   least: 141 executions, 28 solutions, 4 unique   total: 65536 solutions, 8356 unique N = 20: 224 executions N = 21: 245 executions N = 22: 276 executions N = 23   least: 231 executions, 8 solutions, 1 unique   total: 16384 solutions, 2080 unique N = 24   least: 270 executions, 4 solutions, 1 unique   total: 16 solutions, 5 unique N = 25: 353 executions N = 26: 356 executions N = 27: 405 executions N = 28: 416 executions N = 29   least: 345 executions, 8 solutions, 1 unique   total: 1024 solutions, 136 unique N = 30   least: 376 executions, 4 solutions, 1 unique   total: 1048576 solutions, 131720 unique N = 31: 553 executions N = 32   least: 428 executions, 8 solutions, 2 unique   total: 1048576 solutions, 131720 unique   I've attached the complete output of the run for those who want a bit more depth; unfortunately I didn't think of having the program output the actual matrices...  maybe I'll update this post in an hour or so.   Edit: updated attached file with sample matrices   --SMQ « Last Edit: May 3rd, 2005, 11:40am by SMQ » IP Logged --SMQ Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: Execution strategy in a matrix, with constrain   « Reply #18 on: May 3rd, 2005, 11:50am » Quote Modify on May 3rd, 2005, 2:52am, towr wrote: Here's a java-applet implementing almost the same game (but without the restriction you can only toggle one color)   http://grid.let.rug.nl/~vannoord/bertspel/java.html   Years ago I wrote a program to solve that version, but I think it was just brute force.   Yes it looks very similar to the lights out/on puzzle. In fact the existence of a solution (unconstrained version) for every NxN matrix (in fact a random arrangement of the cells) has been proven in a thread in the CS forum:  http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1096040444 (The induction version of the proof can be used to give an algorithm)   Also, given a solution where unkilling the dead is allowed we can get a solution to this problem (unkilling not allowed) as follows: colour the matrix in the chessboard pattern. Now given a solution to the 'unkilling allowed' problem, pick the white squares first and then the black squares.   This gives an algorithm to find at least one solution. A well known algorithm to solve the lights out puzzle is to solve AX = 0, where A is an N2xN2 boolean matrix. « Last Edit: May 3rd, 2005, 12:05pm by Aryabhatta » IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Execution strategy in a matrix, with constrain   « Reply #19 on: May 3rd, 2005, 3:15pm » Quote Modify 39x39 has 2^32 solutions, 61x61 has 2^40. IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: Execution strategy in a matrix, with constrain   « Reply #20 on: May 3rd, 2005, 5:40pm » Quote Modify If you're interested, a while ago I wrote a little C program to solve lights out, and output the solution as an NxN image, white pixels corresponding to toggled lights.  (It outputs .pgm files because of their simple file format; they're big but easily converted.)   Files and sample images are available here (see 74 for the source of my avatar). "foo.out N" will find two solutions with maximal and minimal number of toggles, starting from a solid NxN board.  This can be quite slow when the number of solutions to check is huge. "bar.out state [first] [last]" will start from a number of preset states, e.g., a checkerboard pattern, main diagonals, the four corners, etc.  It computes at most two solutions for each N between first and last, setting all the free variables to the same value, 0 or 1.   (foo.c solves the system of N2 equations in N2 unknowns with a simple O(N6) Gaussian elimination.  But the solution is really determined by one row; bar.c uses this to create, in O(N3), an equivalent set of N equations in N unknowns, solves this in O(N3), and then translates this back to the original N2 variables.) « Last Edit: May 3rd, 2005, 7:54pm by Eigenray » IP Logged yappuzzler Guest Re: Execution strategy in a matrix, with constrain   « Reply #21 on: May 3rd, 2005, 6:27pm » Quote Modify Remove well,     its clear till here. Getting a solution is max complexity. 0(2^N). But this just gives us the combination. We need to traverse this in the right order to be able to achieve the purpose. I wrote a code which works generically till N = 8. to show the actual sequence. However it fails at 9. Thus hinting my logic is not the one which follows..!   Any comments, on optimisation of this last part IP Logged Deedlit Senior Riddler     Posts: 476 Re: Execution strategy in a matrix, with constrain   « Reply #22 on: May 3rd, 2005, 8:40pm » Quote Modify Thanks for the link, Aryabhatta!   yappuzzler, Aryabhatta gave an algorithm for picking the order.  Color the matrix as in a checkerboard;  pick the white squares first, then the black squares.  Since squares of the same color cannot affect each other, the prisoners in the white squares will remain alive until you shoot them.  Further, since the black squares cannot affect each other, the prisoners you need to shoot in the black squares are precisely those who are still alive.  It's simple once you hear it.   IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Execution strategy in a matrix, with constrain   « Reply #23 on: May 4th, 2005, 12:58am » Quote Modify Yep.  That is how I built my solution (5th post or so).     Eigenray: AAh.  I always wondered what your avatar was.  I even fed it in a Game of Life applet to see if it does something.   My code to find a solution looks close to what Eigenray did.  I start with the top line empty, do the elimination from the second row and look what remains on the last row.  Then, for each cell in the top row I check how changing it affects the last row.  It makes a nice set of linear equations.  I then solve the system with Gaussian elimination to zero the last row.  After the elimination, the equations with non-zero coefficients are used to get a solution, and each equation with zero coefficients doubles the number of solutions.   Of course this doesn't address the question of the "number of toggle" optimization. « Last Edit: May 4th, 2005, 1:02am by Grimbal » IP Logged Deedlit Senior Riddler     Posts: 476 Re: Execution strategy in a matrix, with constrain   « Reply #24 on: May 4th, 2005, 6:14pm » Quote Modify on May 3rd, 2005, 3:15pm, Grimbal wrote: 39x39 has 2^32 solutions, 61x61 has 2^40.   So my conjecture that 5*2n-1 has 22^(n+2) is still holding.    More generally, from the scant evidence we can clearly see that f(2n+1) = [f(n)]2 or 4[f(n)]2.  I had some vague ideas about dividing 2n+1 into groups of n,1, and n, and using the solutions for n on the n groups, but I couldn't get it to work...   Also, does anyone see why it's always 4n? IP Logged Pages: 1 2  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board