This is a small program I wrote to search a dictionary for palindromic word squares of any size. See code for documentation comments.

palindromic_squares.go

// This program searches a dictionary for palindromic word squares, such as
// the famous SATOR square:
//
// SATOR
// AREPO
// TENET
// OPERA
// ROTAS
//
// Palindromic word squares read the same forwards, backwards and up and down.
//
// The order (or size) of the square is cutomizable via the --word_size flag, and you
// can optionally customize the dictionary file with the --dict flag.
//
// The algorithm supports unicode characters, and so should work with any language dictionary.
package main

import (
	"bufio"
	"flag"
	"fmt"
	"io"
	"os"
	"strings"
)

var (
	wordSize = flag.Int("word_size", 5, "The word size determines the size of the SATOR square")
	dictFile = flag.String("dict", "dict/scrabble.txt", "The dictionary file contains all the possible words on separate lines")
)

// LoadDict loads the given dictionary file with only words of the given size.
func loadDict(filePath string) map[string]bool {
	f, err := os.Open(filePath)
	if err != nil {
		panic(err)
	}

	ret := make(map[string]bool)
	addWord := func(w string) {
		w = strings.TrimSpace(w)
		if len(w) == *wordSize {
			// Avoid possible casing errors by making everything upper case.
			ret[strings.ToUpper(w)] = true
		}
	}

	// Read the file line by line.
	r := bufio.NewReader(f)
	for {
		l, err := r.ReadString('\n')
		if err == io.EOF {
			break
		}
		if err != nil {
			panic(err)
		}
		addWord(l)
	}

	if len(ret) == 0 {
		panic("The dictionary is empty")
	}
	return ret
}

// Reversed returns the reversed string. E.g. "DOG" becomes "GOD".
func reversed(w string) string {
	var rev []rune
	runes := []rune(w)
	for i := range w {
		rev = append(rev, runes[len(runes)-i-1])
	}
	return string(rev)
}

// TrieNode indexes the words by first and last characters.
//
// It makes it quick and easy to find words that begin with X and end in Y
// without having to search through all the words. Every node represents a single
// prefix and suffix character.
//
// Create with NewNode().
type TrieNode struct {
	// The child nodes are indexed by a single prefix and suffix character. The key of this
	// map is a concatenation of those characters.
	//
	// For example if the prefix is "P" and suffix is "S" then the key of that child would be "PS".
	// Then if that child had a child node with key "AT", then it represents the word "PATS".
	//
	// There is a special case where the key may be a single character, which only happens when
	// --word_size is odd. Then the odd-numbered character in the middle of the string acts as
	// both the prefix and suffix for the leaf node.
	children map[string]*TrieNode
}

// NewNode creates a valid new TrieNode.
func NewNode() *TrieNode {
	return &TrieNode{children: make(map[string]*TrieNode)}
}

// Inserts the word into the trie so it is indexed.
func (root *TrieNode) Insert(word string) {
	dec := []rune(word) // decode the word into unicode runes
	if len(dec) < 2 {
		panic("word is too small")
	}

	cur := root
	for {
		var key string
		if len(dec) >= 2 {
			// Use the prefix and suffix characters from the word as the key for this node.
			key = string([]rune{dec[0], dec[len(dec)-1]})
			// Shrink the word by trimming the prefix and suffix, so we don't reevaluate them.
			dec = dec[1 : len(dec)-1]
		} else if len(dec) == 1 {
			// An odd-numbered character in the middle of the string will have a single char key.
			key = string(dec[0])
			dec = nil
		}

		// Grab the child node at the key, creating a new node if this prefix/suffix combo has not been seen.
		child, ok := cur.children[key]
		if !ok {
			child = NewNode()
			cur.children[key] = child
		}
		if len(dec) == 0 {
			return // the full word has successfully been inserted into the trie
		}
		cur = child
	}
}

// Search returns a list of strings that have the given prefix and suffix.
// If the prefix and suffix are both empty strings, then all strings will be returned.
func (root *TrieNode) Search(prefix, suffix string) []string {
	pre := []rune(prefix)
	suf := []rune(suffix)
	if len(pre) != len(suf) {
		panic("prefix and suffix must be the same size")
	}

	// Iterate through each prefix/suffix character, finding TrieNodes if the word exists.
	cur := root
	for i := 0; ; i++ {
		if i < len(pre) {
			key := string([]rune{pre[i], suf[len(pre)-1-i]})
			child, ok := cur.children[key]
			if !ok {
				break // no match
			}
			cur = child
		}
		if i < len(pre)-1 {
			continue // to search for the next prefix/suffix character in the child node
		}
		// Found a match for the full prefix/suffix. Report all words under this node.
		// Create a buffer and build up the words from their prefixes/suffixes.
		wordBuffer := make([]rune, *wordSize)
		for j := range pre {
			wordBuffer[j] = pre[j]
			wordBuffer[*wordSize-1-j] = suf[len(pre)-1-j]
		}
		return cur.assembleStrings(wordBuffer, len(pre))
	}
	return nil
}

// Iterates recursively through the node and its children, assembling the prefixes and suffixes
// into the original strings and returns the list of strings.
// `buf` is a buffer that holds the temporary string as its being built.
// `index` indicates the location in the string that is being mutated at the current
//   level of recursion. Each TrieNode holds a single pre
func (n *TrieNode) assembleStrings(buf []rune, index int) []string {
	firstIndex := index
	lastIndex := len(buf) - 1 - index
	if lastIndex < firstIndex {
		// We reached the leaf node, report the current buffer.
		// This condition terminates recursion.
		return []string{string(buf)}
	}
	var ret []string
	for key, child := range n.children {
		keyDec := []rune(key)
		buf[firstIndex] = keyDec[0]
		buf[lastIndex] = keyDec[len(keyDec)-1] // don't assume there is an index 1, as the size is not always 2
		ret = append(ret, child.assembleStrings(buf, index+1)...)
	}
	return ret
}

// FindPalindromicSquares recursively searches for palindromic squares and prints them to the console.
//
// At the first level of recursion, all strings in the trie are checked if they work as the
// first word in the square (the last word is also known because it is simply the reverse of
// the first word). At the second level, only the words that begin with the second letter
// of the first word, and end with the second letter of the last word are checked if they work
// as the second word in the square, and so on. Thereby the word square is assembled from
// the outside in, aborting only when no word is found that fits. This effectively searches all
// combinations of words in the dictionary to see if they work.
func (root *TrieNode) FindPalindromicSquares() {
	// Instantiate a buffer for bufferSquare space.
	var bufferSquare [][]rune
	for i := 0; i < *wordSize; i++ {
		bufferSquare = append(bufferSquare, make([]rune, *wordSize))
	}
	root.findPalindromicSquares(bufferSquare, "", "")
}

// This is an internal recursion helper function that searches for palindromic squares.
//
// `buf` is the word square buffer that is used to build temporary squares for checking.
// `prefix` and `suffix` are the prefix and suffix that need to be satisfied at the current
//   level of recursion.
func (root *TrieNode) findPalindromicSquares(buf [][]rune, prefix, suffix string) {
	matches := root.Search(prefix, suffix)
	if len(matches) == 0 {
		return
	}
	index := len([]rune(prefix))
	finalIndex := (*wordSize / 2) + (*wordSize % 2)
	for _, word := range matches {
		// Update the square buffer with the candidate word at the index that corresponds to the prefix/suffix.
		for i, c := range word {
			buf[index][i] = c
			buf[i][index] = c
			buf[*wordSize-1-index][*wordSize-1-i] = c
			buf[*wordSize-1-i][*wordSize-1-index] = c
		}

		nextIndex := index + 1
		if nextIndex == finalIndex {
			// We have successfully found a palindromic square! Show it and keep searching for more squares.
			fmt.Println("") // separate each square by an empty line
			for _, l := range buf {
				fmt.Println(string(l))
			}
			continue
		}

		// The square works so far, but is incomplete. Descend to the next recursion level.
		var nextPrefix, nextSuffix []rune
		for i := 0; i < nextIndex; i++ {
			nextPrefix = append(nextPrefix, buf[nextIndex][i])
			nextSuffix = append(nextSuffix, buf[nextIndex][*wordSize-nextIndex+i])
		}
		root.findPalindromicSquares(buf, string(nextPrefix), string(nextSuffix))
	}
}

// The main application workflow.
func main() {
	flag.Parse()

	// Load the dictionary file into an in-memory index for fast word lookups.
	allWords := loadDict(*dictFile)

	// Find all the words in the dictionary that form words when read backwards,
	// and insert them into the trie.
	trie := NewNode()
	for w := range allWords {
		if allWords[reversed(w)] {
			trie.Insert(w)
		}
	}

	// Use the trie to search for squares.
	trie.FindPalindromicSquares()
}