Initial Query

A binary 8x8 matrix is 'unholy' if there are no isolated 1s. A 1 is isolated if there isn't another 1 in any of the 4 direct cardinal directions. Write a C program that counts the total number of unholy 8x8 matricies.

LLM Generation

Query

A binary 8x8 matrix is 'unholy' if there are no isolated 1s. A 1 is isolated if there isn't another 1 in any of the 4 direct cardinal directions. Write a C program that counts the total number of unholy 8x8 matricies.

Output

To count the total number of "unholy" 8x8 binary matrices, where a matrix is defined as unholy if there are no isolated 1s (i.e., every `1` has at least one neighbor in the four cardinal directions: up, down, left, or right), we can use dynamic programming (DP) with bitmasking. ### Approach: 1. **Bitmask Representation:** - Each row of the matrix can be represented as an 8-bit number (`0` to `255`), where each bit denotes the presence (`1`) or absence (`0`) of a `1` in that position. 2. **Dynamic Programming State:** - **Current Row (`curr`):** The current row being processed. - **Previous Row (`prev`):** The row immediately above the current row. - **Valid State:** For each `1` in the `curr` row, there must be at least one adjacent `1` (left, right, or in the `prev` row). 3. **Transition:** - Iterate through all possible pairs of `prev` and `curr` rows. - For each pair, ensure that the `curr` row satisfies the unholy condition considering the `prev` row. - Use bitwise operations to efficiently check adjacency conditions. 4. **Initialization:** - Start with an initial state where the previous row is `0` (all `0`s). 5. **Final Count:** - After processing all rows, sum all valid configurations. ### Implementation: Below is a C program implementing the above approach. Due to the complexity of the state transitions and the need for efficiency, this program uses memoization and bitmask techniques to handle the large state space. 

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

// Number of possible states for a row
#define STATES 256

// DP table size: 8 rows, STATES for previous row
unsigned long long dp[8][STATES];

// Function to check if a given row is valid with respect to previous row
int isValid(int prev, int curr) {
    // For each bit in the current row
    for(int i = 0; i < 8; i++) {
        if((curr & (1 << i)) != 0) {
            // Check left, right, and up
            int has_neighbor = 0;
            // Left neighbor
            if(i > 0 && (curr & (1 << (i-1))))
                has_neighbor = 1;
            // Right neighbor
            if(i < 7 && (curr & (1 << (i+1))))
                has_neighbor = 1;
            // Up neighbor
            if(prev & (1 << i))
                has_neighbor = 1;
            if(!has_neighbor)
                return 0; // Isolated 1 found
        }
    }
    
    // Now check that in the previous row, any 1 has a neighbor in the current row
    for(int i = 0; i < 8; i++) {
        if((prev & (1 << i)) != 0) {
            int has_neighbor = 0;
            // Check up (which would be the row above prev, not tracked here, so skip)
            // Check left and right in prev
            if(i > 0 && (prev & (1 << (i-1))))
                has_neighbor = 1;
            if(i < 7 && (prev & (1 << (i+1))))
                has_neighbor = 1;
            // Check down (current row)
            if(curr & (1 << i))
                has_neighbor = 1;
            if(!has_neighbor)
                return 0; // Isolated 1 in previous row
        }
    }
    
    return 1;
}

int main() {
    // Initialize DP
    memset(dp, 0, sizeof(dp));
    
    // Initial state: no previous row
    // To handle the first row, previous row is 0
    for(int curr = 0; curr < STATES; curr++) {
        // Check validity with prev = 0
        // All 1s in current row must have a neighbor in the current row
        int valid = 1;
        for(int i = 0; i < 8; i++) {
            if((curr & (1 << i)) != 0) {
                int has_neighbor = 0;
                if(i > 0 && (curr & (1 << (i-1))))
                    has_neighbor = 1;
                if(i < 7 && (curr & (1 << (i+1))))
                    has_neighbor = 1;
                if(!has_neighbor)
                {
                    valid = 0;
                    break;
                }
            }
        }
        if(valid) {
            dp[0][curr] = 1;
        }
    }
    
    // Fill DP table
    for(int row = 1; row < 8; row++) {
        for(int prev = 0; prev < STATES; prev++) {
            if(dp[row-1][prev] == 0)
                continue;
            for(int curr = 0; curr < STATES; curr++) {
                if(isValid(prev, curr)) {
                    dp[row][curr] += dp[row-1][prev];
                }
            }
        }
    }
    
    // Now, we need to ensure that the last row's 1s are not isolated
    // Since there's no row below the last, check that last row's 1s have at least one neighbor in the row itself or in the previous row
    unsigned long long total = 0;
    for(int last = 0; last < STATES; last++) {
        // Validate last row with a virtual next row = 0
        int valid = 1;
        // Check each 1 in the last row
        for(int i = 0; i < 8; i++) {
            if((last & (1 << i)) != 0) {
                int has_neighbor = 0;
                // Left
                if(i > 0 && (last & (1 << (i-1))))
                    has_neighbor = 1;
                // Right
                if(i < 7 && (last & (1 << (i+1))))
                    has_neighbor = 1;
                // Up (from previous row)
                // We need to check all possible previous rows that lead to this state
                // But in our DP, the dp[7][last] already includes valid transitions
                // So here, no need to check further
                if(!has_neighbor) {
                    valid = 0;
                    break;
                }
            }
        }
        if(valid) {
            total += dp[7][last];
        }
    }
    
    printf("Total number of unholy 8x8 matrices: %llu\n", total);
    
    return 0;
}
### Explanation: 1. **Initialization:** - The DP table `dp[row][prev]` holds the number of valid configurations up to the current `row` with the previous row's state as `prev`. - For the first row (`row = 0`), we initialize `dp[0][curr]` for all `curr` that have no isolated `1`s within the row itself. 2. **DP Transition:** - For each subsequent row, iterate through all possible previous row states (`prev`) and current row states (`curr`). - Use the `isValid` function to check if the transition from `prev` to `curr` maintains the unholy condition. - If valid, update the DP table accordingly. 3. **Final Validation:** - After processing all 8 rows, ensure that the last row's `1`s are not isolated by themselves (since there's no row below them). - Sum up all valid configurations from the last row. 4. **Optimization:** - Bitmasking is used extensively to handle rows efficiently. - The `isValid` function ensures that both the current row and the previous row satisfy the non-isolation condition. ### Running the Program: Compile and run the program using a C compiler: 
1
2
gcc -o count_unholy count_unholy.c
./count_unholy
### Note: This program is optimized for the 8x8 matrix size. For larger matrices, more advanced techniques or optimizations would be necessary due to the exponential growth of state space.

Extract Code

I extracted the following code from that output: 

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

// Number of possible states for a row
#define STATES 256

// DP table size: 8 rows, STATES for previous row
unsigned long long dp[8][STATES];

// Function to check if a given row is valid with respect to previous row
int isValid(int prev, int curr) {
    // For each bit in the current row
    for(int i = 0; i < 8; i++) {
        if((curr & (1 << i)) != 0) {
            // Check left, right, and up
            int has_neighbor = 0;
            // Left neighbor
            if(i > 0 && (curr & (1 << (i-1))))
                has_neighbor = 1;
            // Right neighbor
            if(i < 7 && (curr & (1 << (i+1))))
                has_neighbor = 1;
            // Up neighbor
            if(prev & (1 << i))
                has_neighbor = 1;
            if(!has_neighbor)
                return 0; // Isolated 1 found
        }
    }
    
    // Now check that in the previous row, any 1 has a neighbor in the current row
    for(int i = 0; i < 8; i++) {
        if((prev & (1 << i)) != 0) {
            int has_neighbor = 0;
            // Check up (which would be the row above prev, not tracked here, so skip)
            // Check left and right in prev
            if(i > 0 && (prev & (1 << (i-1))))
                has_neighbor = 1;
            if(i < 7 && (prev & (1 << (i+1))))
                has_neighbor = 1;
            // Check down (current row)
            if(curr & (1 << i))
                has_neighbor = 1;
            if(!has_neighbor)
                return 0; // Isolated 1 in previous row
        }
    }
    
    return 1;
}

int main() {
    // Initialize DP
    memset(dp, 0, sizeof(dp));
    
    // Initial state: no previous row
    // To handle the first row, previous row is 0
    for(int curr = 0; curr < STATES; curr++) {
        // Check validity with prev = 0
        // All 1s in current row must have a neighbor in the current row
        int valid = 1;
        for(int i = 0; i < 8; i++) {
            if((curr & (1 << i)) != 0) {
                int has_neighbor = 0;
                if(i > 0 && (curr & (1 << (i-1))))
                    has_neighbor = 1;
                if(i < 7 && (curr & (1 << (i+1))))
                    has_neighbor = 1;
                if(!has_neighbor)
                {
                    valid = 0;
                    break;
                }
            }
        }
        if(valid) {
            dp[0][curr] = 1;
        }
    }
    
    // Fill DP table
    for(int row = 1; row < 8; row++) {
        for(int prev = 0; prev < STATES; prev++) {
            if(dp[row-1][prev] == 0)
                continue;
            for(int curr = 0; curr < STATES; curr++) {
                if(isValid(prev, curr)) {
                    dp[row][curr] += dp[row-1][prev];
                }
            }
        }
    }
    
    // Now, we need to ensure that the last row's 1s are not isolated
    // Since there's no row below the last, check that last row's 1s have at least one neighbor in the row itself or in the previous row
    unsigned long long total = 0;
    for(int last = 0; last < STATES; last++) {
        // Validate last row with a virtual next row = 0
        int valid = 1;
        // Check each 1 in the last row
        for(int i = 0; i < 8; i++) {
            if((last & (1 << i)) != 0) {
                int has_neighbor = 0;
                // Left
                if(i > 0 && (last & (1 << (i-1))))
                    has_neighbor = 1;
                // Right
                if(i < 7 && (last & (1 << (i+1))))
                    has_neighbor = 1;
                // Up (from previous row)
                // We need to check all possible previous rows that lead to this state
                // But in our DP, the dp[7][last] already includes valid transitions
                // So here, no need to check further
                if(!has_neighbor) {
                    valid = 0;
                    break;
                }
            }
        }
        if(valid) {
            total += dp[7][last];
        }
    }
    
    printf("Total number of unholy 8x8 matrices: %llu\n", total);
    
    return 0;
}

Run Code Interpreter

Running the following program: 

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

// Number of possible states for a row
#define STATES 256

// DP table size: 8 rows, STATES for previous row
unsigned long long dp[8][STATES];

// Function to check if a given row is valid with respect to previous row
int isValid(int prev, int curr) {
    // For each bit in the current row
    for(int i = 0; i < 8; i++) {
        if((curr & (1 << i)) != 0) {
            // Check left, right, and up
            int has_neighbor = 0;
            // Left neighbor
            if(i > 0 && (curr & (1 << (i-1))))
                has_neighbor = 1;
            // Right neighbor
            if(i < 7 && (curr & (1 << (i+1))))
                has_neighbor = 1;
            // Up neighbor
            if(prev & (1 << i))
                has_neighbor = 1;
            if(!has_neighbor)
                return 0; // Isolated 1 found
        }
    }
    
    // Now check that in the previous row, any 1 has a neighbor in the current row
    for(int i = 0; i < 8; i++) {
        if((prev & (1 << i)) != 0) {
            int has_neighbor = 0;
            // Check up (which would be the row above prev, not tracked here, so skip)
            // Check left and right in prev
            if(i > 0 && (prev & (1 << (i-1))))
                has_neighbor = 1;
            if(i < 7 && (prev & (1 << (i+1))))
                has_neighbor = 1;
            // Check down (current row)
            if(curr & (1 << i))
                has_neighbor = 1;
            if(!has_neighbor)
                return 0; // Isolated 1 in previous row
        }
    }
    
    return 1;
}

int main() {
    // Initialize DP
    memset(dp, 0, sizeof(dp));
    
    // Initial state: no previous row
    // To handle the first row, previous row is 0
    for(int curr = 0; curr < STATES; curr++) {
        // Check validity with prev = 0
        // All 1s in current row must have a neighbor in the current row
        int valid = 1;
        for(int i = 0; i < 8; i++) {
            if((curr & (1 << i)) != 0) {
                int has_neighbor = 0;
                if(i > 0 && (curr & (1 << (i-1))))
                    has_neighbor = 1;
                if(i < 7 && (curr & (1 << (i+1))))
                    has_neighbor = 1;
                if(!has_neighbor)
                {
                    valid = 0;
                    break;
                }
            }
        }
        if(valid) {
            dp[0][curr] = 1;
        }
    }
    
    // Fill DP table
    for(int row = 1; row < 8; row++) {
        for(int prev = 0; prev < STATES; prev++) {
            if(dp[row-1][prev] == 0)
                continue;
            for(int curr = 0; curr < STATES; curr++) {
                if(isValid(prev, curr)) {
                    dp[row][curr] += dp[row-1][prev];
                }
            }
        }
    }
    
    // Now, we need to ensure that the last row's 1s are not isolated
    // Since there's no row below the last, check that last row's 1s have at least one neighbor in the row itself or in the previous row
    unsigned long long total = 0;
    for(int last = 0; last < STATES; last++) {
        // Validate last row with a virtual next row = 0
        int valid = 1;
        // Check each 1 in the last row
        for(int i = 0; i < 8; i++) {
            if((last & (1 << i)) != 0) {
                int has_neighbor = 0;
                // Left
                if(i > 0 && (last & (1 << (i-1))))
                    has_neighbor = 1;
                // Right
                if(i < 7 && (last & (1 << (i+1))))
                    has_neighbor = 1;
                // Up (from previous row)
                // We need to check all possible previous rows that lead to this state
                // But in our DP, the dp[7][last] already includes valid transitions
                // So here, no need to check further
                if(!has_neighbor) {
                    valid = 0;
                    break;
                }
            }
        }
        if(valid) {
            total += dp[7][last];
        }
    }
    
    printf("Total number of unholy 8x8 matrices: %llu\n", total);
    
    return 0;
}
And got the output: Total number of unholy 8x8 matrices: 5152918862634818

Substring Evaluation

Testing if the previous output contains the string 1121231537486377866: False

Initial Query

A binary 8x8 matrix is 'unholy' if there are no isolated 1s. A 1 is isolated if there isn't another 1 in any of the 4 direct cardinal directions. Write a C program that counts the total number of unholy 8x8 matricies.

LLM Generation

Query

A binary 8x8 matrix is 'unholy' if there are no isolated 1s. A 1 is isolated if there isn't another 1 in any of the 4 direct cardinal directions. Write a C program that counts the total number of unholy 8x8 matricies.

Output

Certainly! Below is a C program that counts the total number of "unholy" 8x8 binary matrices. An "unholy" matrix is defined such that there are no isolated `1`s. A `1` is considered isolated if it doesn't have another `1` in any of the four direct cardinal directions (North, South, East, or West). ### Approach: To efficiently count the number of valid matrices without enumerating all \(2^{64}\) possibilities, we use **Dynamic Programming (DP)**. The idea is to process the matrix row by row, keeping track of the necessary constraints to ensure no `1` is isolated. **Key Points of the Approach:** 1. **State Representation:** - **`required` Mask:** For each row, we maintain a bitmask (`required`) that represents positions in the previous row that have `1`s requiring a neighboring `1` in the current row (to avoid isolation). 2. **Transition:** - For each possible configuration (`curr`) of the current row, we check: - **Satisfying `required` Constraints:** All positions marked in the `required` mask must have `1`s in the current row. - **Neighbor Constraints:** Every `1` in the current row must have at least one neighboring `1` either within the current row (left or right) or from the `required` mask (above). 3. **DP Table Update:** - If a configuration is valid, we update the DP table for the next row based on the current configuration. 4. **Final Calculation:** - After processing all rows, the final answer is the count of valid matrices where there are no pending `required` positions in the last row. ### C Program: 

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdint.h>
#include <string.h>

int main(){
    // Define DP arrays
    unsigned long long prev_dp[256];
    unsigned long long current_dp[256];

    // Initialize previous DP state: no required bits initially
    memset(prev_dp, 0, sizeof(prev_dp));
    prev_dp[0] = 1;

    // Iterate over each row
    for(int row=0; row <8; row++){
        // Reset current DP state
        memset(current_dp, 0, sizeof(current_dp));
        
        // Iterate over all possible required masks from the previous row
        for(int required=0; required <256; required++){
            if(prev_dp[required] == 0) continue; // Skip if no configurations lead to this state
            
            // Iterate over all possible current row configurations
            for(int curr=0; curr <256; curr++){
                // Check if current configuration satisfies the required mask
                if( (required & ~curr) !=0 ) continue; // Required bits must be set in current row

                // Validate that every '1' in current row has at least one neighbor
                int valid = 1;
                for(int i=0; i<8; i++){
                    if(curr & (1 << i)){
                        int has_neighbor = 0;

                        // Check left neighbor
                        if(i >0 && (curr & (1 << (i-1)))) has_neighbor =1;

                        // Check right neighbor
                        if(i <7 && (curr & (1 << (i+1)))) has_neighbor =1;

                        // Check upper neighbor
                        if( (required & (1 <<i)) ) has_neighbor =1;

                        if(!has_neighbor){
                            valid = 0;
                            break;
                        }
                    }
                }

                if(valid){
                    int new_required;
                    if(row <7){
                        // For rows 0 to 6, set new required bits based on current row
                        new_required = curr;
                    } else{
                        // For the last row, there are no rows below, so no required bits
                        new_required = 0;
                    }
                    // Update the current DP state
                    current_dp[new_required] += prev_dp[required];
                }
            }
        }
        // Move to the next row
        memcpy(prev_dp, current_dp, sizeof(prev_dp));
    }

    // The final answer is the number of configurations with no pending required bits
    printf("Total number of unholy 8x8 matrices: %llu\n", prev_dp[0]);

    return 0;
}
### Explanation of the Code: 1. **Initialization:** - `prev_dp[256]` and `current_dp[256]` are arrays used to store the number of valid configurations for each possible mask (0 to 255) of an 8-bit row. - `prev_dp[0] = 1;` initializes the DP with an empty previous row (no `1`s). 2. **Row-wise Processing:** - The outer loop iterates over each of the 8 rows. - For each row, we consider all possible configurations (`curr`) of `1`s and `0`s. - We ensure that the current configuration satisfies the `required` mask from the previous row. 3. **Validating Neighbors:** - For each `1` in the current row, we check if it has at least one neighbor either to its left, right, or above. - If a `1` does not have any such neighbor, the current configuration is invalid and skipped. 4. **Updating DP States:** - If a configuration is valid, we update the `current_dp` based on whether we are processing the last row or not. - For rows 0 to 6, the `required` mask for the next row is set to the current row's configuration. - For the last row, since there are no rows below, the `required` mask is set to `0`. 5. **Final Output:** - After processing all rows, the total number of valid (unholy) matrices is stored in `prev_dp[0]` and is printed out. ### Running the Program: To compile and run this program, follow these steps: 1. **Save the Code:** - Save the above code in a file named `count_unholy_matrices.c`. 2. **Compile:** - Use a C compiler like `gcc` to compile the program: 
1
2
     gcc -o count_unholy_matrices count_unholy_matrices.c
3. **Execute:** - Run the compiled program: 
1
2
     ./count_unholy_matrices
### Performance: This program uses efficient bitmasking and dynamic programming to handle the computation within a reasonable time frame, despite the large state space. It leverages the fact that each row can be represented as an 8-bit mask, and transitions between rows are managed by ensuring all constraints are satisfied continuously. ### Conclusion: By using dynamic programming and bitmasking, the program efficiently counts the total number of "unholy" 8x8 binary matrices without needing to enumerate all possible \(2^{64}\) configurations. This approach ensures that each `1` in the matrix has at least one neighboring `1`, adhering to the definition of an "unholy" matrix.

Extract Code

I extracted the following code from that output: 

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdint.h>
#include <string.h>

int main(){
    // Define DP arrays
    unsigned long long prev_dp[256];
    unsigned long long current_dp[256];

    // Initialize previous DP state: no required bits initially
    memset(prev_dp, 0, sizeof(prev_dp));
    prev_dp[0] = 1;

    // Iterate over each row
    for(int row=0; row <8; row++){
        // Reset current DP state
        memset(current_dp, 0, sizeof(current_dp));
        
        // Iterate over all possible required masks from the previous row
        for(int required=0; required <256; required++){
            if(prev_dp[required] == 0) continue; // Skip if no configurations lead to this state
            
            // Iterate over all possible current row configurations
            for(int curr=0; curr <256; curr++){
                // Check if current configuration satisfies the required mask
                if( (required & ~curr) !=0 ) continue; // Required bits must be set in current row

                // Validate that every '1' in current row has at least one neighbor
                int valid = 1;
                for(int i=0; i<8; i++){
                    if(curr & (1 << i)){
                        int has_neighbor = 0;

                        // Check left neighbor
                        if(i >0 && (curr & (1 << (i-1)))) has_neighbor =1;

                        // Check right neighbor
                        if(i <7 && (curr & (1 << (i+1)))) has_neighbor =1;

                        // Check upper neighbor
                        if( (required & (1 <<i)) ) has_neighbor =1;

                        if(!has_neighbor){
                            valid = 0;
                            break;
                        }
                    }
                }

                if(valid){
                    int new_required;
                    if(row <7){
                        // For rows 0 to 6, set new required bits based on current row
                        new_required = curr;
                    } else{
                        // For the last row, there are no rows below, so no required bits
                        new_required = 0;
                    }
                    // Update the current DP state
                    current_dp[new_required] += prev_dp[required];
                }
            }
        }
        // Move to the next row
        memcpy(prev_dp, current_dp, sizeof(prev_dp));
    }

    // The final answer is the number of configurations with no pending required bits
    printf("Total number of unholy 8x8 matrices: %llu\n", prev_dp[0]);

    return 0;
}

Run Code Interpreter

Running the following program: 

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdint.h>
#include <string.h>

int main(){
    // Define DP arrays
    unsigned long long prev_dp[256];
    unsigned long long current_dp[256];

    // Initialize previous DP state: no required bits initially
    memset(prev_dp, 0, sizeof(prev_dp));
    prev_dp[0] = 1;

    // Iterate over each row
    for(int row=0; row <8; row++){
        // Reset current DP state
        memset(current_dp, 0, sizeof(current_dp));
        
        // Iterate over all possible required masks from the previous row
        for(int required=0; required <256; required++){
            if(prev_dp[required] == 0) continue; // Skip if no configurations lead to this state
            
            // Iterate over all possible current row configurations
            for(int curr=0; curr <256; curr++){
                // Check if current configuration satisfies the required mask
                if( (required & ~curr) !=0 ) continue; // Required bits must be set in current row

                // Validate that every '1' in current row has at least one neighbor
                int valid = 1;
                for(int i=0; i<8; i++){
                    if(curr & (1 << i)){
                        int has_neighbor = 0;

                        // Check left neighbor
                        if(i >0 && (curr & (1 << (i-1)))) has_neighbor =1;

                        // Check right neighbor
                        if(i <7 && (curr & (1 << (i+1)))) has_neighbor =1;

                        // Check upper neighbor
                        if( (required & (1 <<i)) ) has_neighbor =1;

                        if(!has_neighbor){
                            valid = 0;
                            break;
                        }
                    }
                }

                if(valid){
                    int new_required;
                    if(row <7){
                        // For rows 0 to 6, set new required bits based on current row
                        new_required = curr;
                    } else{
                        // For the last row, there are no rows below, so no required bits
                        new_required = 0;
                    }
                    // Update the current DP state
                    current_dp[new_required] += prev_dp[required];
                }
            }
        }
        // Move to the next row
        memcpy(prev_dp, current_dp, sizeof(prev_dp));
    }

    // The final answer is the number of configurations with no pending required bits
    printf("Total number of unholy 8x8 matrices: %llu\n", prev_dp[0]);

    return 0;
}
And got the output: Total number of unholy 8x8 matrices: 478467

Substring Evaluation

Testing if the previous output contains the string 1121231537486377866: False