View unanswered posts | View active topics It is currently Sat Dec 16, 2017 10:57 am



← Back to the Calcudoku puzzle page




Reply to topic  [ 1 post ] 
 Step by step solution of an 8x8 "bitwise OR" 
Author Message

Posted on: Mon Oct 17, 2011 11:45 am




Posts: 694
Joined: Fri May 13, 2011 6:51 pm
Post Step by step solution of an 8x8 "bitwise OR"
Step by step solution of an 8x8 “bitwise OR”.

For this example I will use the tuesday Aug 30, 2011, 8x8 difficult puzzle (8 points) (Puzzle id: 336700). This puzzle was solved by only 47 players (around the 12% of the active players in that moment, 415). A comment: In this puzzle there are 10 cages “7|” (the most complex theorically) however we will verify that this fact does not really increase the difficulty of the puzzle.

In the post “Full tables: the “mod function” and the “bitwise OR” (in the 8x8’s)”, in the Section “Solving strategies and tips” of the English Forum, we can find all possible combinations for the function “bitwise OR” as well as an appendix explaining how this function works and the binary expression of all numbers involved.

I will use pairs of numbers (in black and small size in the lower part of the cell) when those are the final candidates for that cage, in big size (in the center of the cell) for the final solution for that cell, and I will use colors in general (and in one side of the cages to show the different options discussed). The small numbered “ellipses” refer to the steps along the procedure.

Step by step solution of an 8x8 “bitwise OR”.

For this example I will use the tuesday Aug 30, 2011, 8x8 difficult puzzle (8 points) (Puzzle id: 336700). This puzzle was solved by only 47 players (around the 12% of the active players in that moment, 415). A comment: In this puzzle there are 10 cages “7|” (the most complex theorically) however we will verify that this fact does not really increase the difficulty of the puzzle.

In the post “Full tables: the “mod function” and the “bitwise OR” (in the 8x8’s)”, in the Section “Solving strategies and tips” of the English Forum, we can find all possible combinations for the function “bitwise OR” as well as an appendix explaining how this function works and the binary expression of all numbers involved.

I will use pairs of numbers (in black and small size in the lower part of the cell) when those are the final candidates for that cage, in big size (in the center of the cell) for the final solution for that cell, and I will use colors in general (and in one side of the cages to show the different options discussed). The small numbered “ellipses” refer to the steps along the procedure.

Image

Step 1. We first situate all numbers shown: the pair of candidates in a1-b1 is 28 (only combination for “16x”); since 17 is the pair of candidates in a2-b2, f1 = 1 and f2 = 8 (“7-“ is only made by 1-8); since 35 is the pair of candidates in c2-d2, e1 = 3 and e2 = 6 (“18x” is only made by 3-6).
The pair 24 occupies the cells g2-h2, since the other option, 18, is not possible due to the 1 in a2-b2, so observing the 2 in g5, g2 = 4 and h2 = 2.
Row 3: g3-h3 must be 17 (obviously) so a3-b3 is 38 (the cage “5-“ would initially have 3 possibilities, 1-6, 2-7 and 3-8 but now 1-6 and 2-7 are not possible).
The cage “6-“ in e4-e5 has two possibilities (1-7 and 2-8) but the 1 in e8 forces the candidates to be the pair 28 then e4 = 2 and e5 = 8 (observing the 2 in g5).
The cage “9|” has the unique combination 18 (see the referenced post) so now c4 = 8 and c5 = 1 (due to the 8 in e5).
Row 7: We know that an 8 must be inside the cage “14|” in b7-d7-c7. This 8 must go to d7 because there is an 8 in column c (in c4) and the cell b7 can not be an 8 due to the pairs 28 in a1-b1 and 38 in a3-b3 “erasing” columns a and b.
Row 8: The cage “6+” in c8-d8 must be 24 (1-5 not possible due to the 1 in e8). In these conditions the cage “8+” in a8-b8 (three possibilities1-7, 2-6 or 3-5) has necessarily the pair 35. As we know, the cage “14|” (g8-h8) is made by the pair 68 (certainly the 8 must be inside this cage but also 14| in two cells is always 68). Finally, the 7 of the row 8 must go to the only empty place f8.

Image

Step 2 (shown in red). In the row 6, the 8 can only be placed in h6 (with h5 = 3) (we know that an 8 can never be inside a cage “n|” if n < 8 and all cages “entering” this row 6 are of that type). And, consequently, g8 = 8 and h8 = 6.

Step 3. Observing the row 3, the cages “5-“, “9+”, “12+” and “7:” have a sum of 11 + 9 + 12 + 8 = 40 so, since the sum of all numbers in any row or column of this puzzle must be 36, we have an excess of 4 (1 + 3) for the addition of the two cells d4 and f4 and since there is already a 1 in f1, f4 = 3 and d4 = 1.

Once we have a 1 in d4 the cage “5|” in g4-h4 must contain the pair 45 (5| in two cells admits only the combinations 1-4, 1-5 and 4-5). Then, being g2 = 4, g4 must be 5 and h4 = 4. And now the cage “7|” in a4-b4 contains necessarily the pair 67.

Step 4 (shown in orange). The 4’s in g2 and h4 force the 4 of row 1 to be inside the cage “7|” in c1-d1 but to produce a 7| the roommate of the 4 must be 3 or 7 (4 equals “100” in binary so to obtain “111” = 7| we need to activate the last two bits and the numbers that do that are the 3 = “011” and the 7 = “111”; also, in the referenced post, we can see that for a 7| in two cells there are only two combinations containing a 4, the 47 and the 34, among the twelve possible combinations). Since a 3 is already present in e1, the pair of candidates for c1-d1 must be 47. Consequently, g1-h1 must be 56 and then (because of the 6 in h8) g1 = 6 and h1 = 5.

Step 5 (shown in green). We assign the pair of candidates 45 to the cells e3-f3 (to complete, with a sum of 9, the cage “12+”, being impossible the pairs 18, 27 or 36). And then the pair 26 goes to c3-d3 (inversely we could have started determining first this pair c3-d3, with a sum of 8, necessarily 26, being the pairs 17 and 35 impossible).

Row 5: The 7 of this row must be placed in d5 because f5 is inhibited by the 7 in f8 and the pairs 17 in a2-b2 and 67 in a4-b4 inhibit a 7 in a5-b5 (“erasing” both columns a and b simultaneously). This7 in d5 produces these consequences: c1 = 7, d1 = 4, c8 = 4, d8 = 2, c3 = 2, d3 = 6.

Now, in row 5, the 4 can not be inside “7|” in a5-b5 because the required roommates, 3 or 7 (discussed in step 4) are already placed outside the cage, in h5 and d5, respectively, so the 4 goes to f5 then producing e3 = 4 and f3 = 5. The pair 56 goes to a5-b5.

This is the actual situation:

Image

Now let’s continue with the following graphic:

Image

Step 6 (shown in blue).

1) First we complete the column e assigning the pair 57 to e6-e7. Now let’s see the cage “5|” in a6-a7: Since this cage can not contain a 5 (there are pairs with a 5 in a5-b5, 56, and a8-b8, 35, so saturating the number of 5’s in columns a and b) it must be 14 (5| has only the three possible combinations 1-4, 1-5 and 4-5 as we know). After writing the candidates, 14, in a6-a7 we proceed to define a2 = 7, b2 = 1, a4 = 6, b4 = 7, a5 = 5, b5 = 6, a8 = 3, b8 = 5, a3 = 8, b3 = 3, a1 = 2, b1 = 8.

2) Now the 3 of row 7 must go to g7 (a 3 is forbidden inside a cage 14| = “1110”, because it activates the last bit, and the cells e7, f7 and h7 are inhibited, respectively, by the 3’s in e1, f4 and h5). We have arrived to an interesting point: Where to place the 7 in row 7, in e7 or in h7? and, Who is the roommate of the 3 in the cage g7-h7?. To complete the cage “7|” in g7-h7 we may think as follows: Since a 3 = “011” we need to activate the bit position number 3 in order to obtain the “111” = 7|; this bit is activated with a 4 = “100”, a 5 = 101”, a 6 = “110” and a 7 = “111” (see these four combinations 34, 35, 36 and 37, among the twelve possible combinations for 7| in two cells, in the referenced post). But it is not possible to place any additional 4, 5 or 6, in columns g and h (these columns already contain two 4’s, two 5’s and two 6’s) so h7 = 7. Now g3 = 7, h3 = 1.

Step 7 (shown in green). The 7 in h7 forces e6 = 7 and e7 = 5. We need a 1 in column g that must go to g6 (the only empty place).and then a6 = 4, a7 = 1, b6 = 2, b7 = 4, f6 = 6, f7 = 2 and, finally, c7 = 6.

Step 8 (shown in violet). We arrive to the end of the puzzle with this interesting (and key point): Who, the 3 or the 5, goes to the cage “7|” in b6-c6, to the cell c6?. The 5 is the solution since 2 bitwise OR 3 = 3| but not 7|. Then c6 = 5 and d6 = 3. Finished: c2 = 3 and d2 = 5.

And here is the “official” solution:

Image


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 1 post ] 

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.