Combinations of characters in the nth character array:

Question

First note: Sorry that my images are not divided. I’m a new member, so I don’t have enough reputation points to place more than one hyperlink.

Let M be the n over n array (mathematically square matrix) characters.

In M, I need to find all character permutations with a constraint. The permutations should not be linear, but they must contain characters, so that each character is adjacent to at least one other character in the permutation. The following is an example of an acceptable permutation:

The following is an unacceptable permutation.

I got so much:

• A permutation can contain no more than n square characters (since no characters can be repeated).
• I do not know the exact number of permutations given the restrictions, but I believe that there can be no more than the value generated by evaluating the expression shown in the hyperlink.

I can easily find permutations containing only characters in straight lines: vertical lines, horizontal lines and diagonals. I am not sure of the possibility of exhaustively finding all the other permutations.

I conducted a study and could not find a solution to this problem.

Any advice on developing such an exhaustive algorithm is welcome.

http://i.stack.imgur.com/uDNfv.png

Answer 1

One algorithm immediately comes to mind, although optimization can be done if the time problem is complex.

2x2 ( , ), 8 , (, -, , , , -, , -).

( pass by value, "current_string" ):

find(position, direction, current_string){
    new_letter = m[0, position + direction];
    if(!current_string.Contains(new_letter)){
        // We have not yet encountered this letter during the search.
        // If letters occur more than once in the array, then you must
        // assign an index to each position in the array instead and
        // store which positions have been encountered along each
        // search path instead.
        current_string += new_letter;
        find(position, (0, 1), current_string);
        find(position, (1, 1), current_string);
        find(position, (1, 0), current_string);
        find(position, (1, -1), current_string);
        find(position, (0, -1), current_string);
        find(position, (-1, -1), current_string);
        find(position, (-1, 0), current_string);
        find(position, (-1, 1), current_string);
    } else {
        // This letter has been encountered during this path search,
        // terminate this path search. See comment above if letters
        // occur more than once in the matrix.
        print current_string; // Print one of the found strings!
    }
}

, " + , , current_string ".

, , , ( , Snake).

( if(!current_string.Contains(new_letter)){), O (1) , . n , cn n, c - .