CodeIQ：魔方陣で最大値？

問題の概要

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def setUsed(used, arr, val)
	for a in arr
		used[a] = val
	end
	return used
end

def isDup(x, used, others)
	if used[x] then return true end
	if others.include?(x) then return true end
	return false
end

# 次のサイトから移植
# http://www.daido-it.ac.jp/~oishi/TH5/ms4/ms4prg.html
def makeMagicSquare()
	ret = []
	used = Array.new(17,false)

	for a in 1..13	# aのループ
		used[a]=true

		for d in (a+1)..15	# dのループ
		used[d]=true

			for m in (d+1)..16	# mのループ
				q=34-a-d-m								# qを計算
				if q<a then break end					# 回転禁止条件より
				if q>16 then next end					# 16以下であること
				if isDup(q, used, [m]) then next end	# 重複チェック
				used=setUsed(used, [m,q], true)			# 使用済みのフラグを立てる

				for f in 1..16	# fのループ
					if used[f] then next end				# fが既に使用されていないか
					k=34-a-f-q								# kを計算
					if k<1 then break end					# 1以上であること（kはこの先減る）
					if k>16 then next end					# 16以下であること
					if isDup(k, used, [f]) then next end	# 重複チェック
					used=setUsed(used, [f,k], true)			# 使用済みのフラグを立てる

					for b in 1..16	# bのループ
						if used[b] then next end
						c=34-a-b-d
						if c<1 then break end
						if c>16 then next end
						if isDup(c, used, [b]) then next end
						used=setUsed(used, [b,c], true)

						for g in 1..16	# gのループ
							if used[g] then next end
							j=34-d-g-m
							if j<1 then break end
							if j>16 then next end
							if isDup(j, used, [g]) then next end

							o=34-c-g-k
							if o<1 then break end
							if o>16 then next end
							if isDup(o, used, [j,g]) then next end

							n=34-b-f-j
							if n>16 then break end
							if n<1 then next end
							if isDup(n, used, [j,g,o]) then next end

							used=setUsed(used, [g,j,o,n], true)

							for e in 1..16	# eのループ
								if used[e] then next end
								h=34-e-f-g
								if h<1 then break end
								if h>16 then next end
								if isDup(h, used, [e]) then next end

								i=34-a-e-m
								if i<1 then break end
								if i>16 then next end
								if isDup(i, used, [e,h]) then next end

								l=34-d-h-q
								if l>16 then break end
								if l<1 then next end
								if isDup(l, used, [e,h,i]) then next end

								ret << [[a,b,c,d],[e,f,g,h],[i,j,k,l],[m,n,o,q]]
							end
							used=setUsed(used, [g,j,o,n], false)     # フラグを降ろす
						end
						used=setUsed(used, [b,c], false)     # フラグを降ろす
					end
					used=setUsed(used, [f,k], false)     # フラグを降ろす
				end
				used=setUsed(used, [m,q], false)     # フラグを降ろす
			end
			used[d]=false
		end
		used[a]=false
	end
	return ret
end

# ダイクストラ法で経路探索
def getMaxPath(map)
	memo = Array.new(4){Array.new(4, 0)}
	directions = [[0,1], [1,0]]

	queue = [[0,0]]
	memo[0][0] = map[0][0]

	while !queue.empty?
		cur = queue.shift
		v = memo[cur[0]][cur[1]]

		for d in directions
			nxt = [cur[0]+d[0], cur[1]+d[1]]

			if (nxt[0]<0) || (nxt[1]<0) || (4<=nxt[0]) || (4<=nxt[1]) then next end
			nv = v + map[nxt[0]][nxt[1]]

			if nv > memo[nxt[0]][nxt[1]] then
				memo[nxt[0]][nxt[1]] = nv
				queue << nxt
			end
		end

		queue.uniq!
	end

	return memo[3][3]
end

# mapを回転する
def rotateMap(map)
	nxt = Array.new(4){Array.new(4, 0)}
	for i in 0...4
		for j in 0...4
			nxt[j][3-i] = map[i][j]
		end
	end
	return nxt
end

# mapを上下鏡像にする
def mirrorMap(map)
	nxt = Array.new(4){Array.new(4, 0)}
	for i in 0...4
		for j in 0...4
			nxt[3-i][j] = map[i][j]
		end
	end
	return nxt
end

# 魔方陣の全パターンの最長経路を求める
def makeCountList()
	ret = Hash.new(0)

	maps = makeMagicSquare()
	for map in maps
		valiants = [map]
		for _ in 0...3
			valiants << rotateMap(valiants.last)
		end
		valiants << mirrorMap(map)
		for _ in 0...3
			valiants << rotateMap(valiants.last)
		end

		for v in valiants
			c = getMaxPath(v)
			ret[c] += 1
		end
	end

	return ret
end

# main
counts = makeCountList()
while line = gets
	line.strip!
	if line.empty? then next end

	p counts[line.to_i]
end

解説

私のプログラムは愚直にやっていますが、もっと効率の良い方法があるのでしょうか？

雑感

私のやり方は完全な総当たりですがもっと効率の良い方法がある気はします。
その上、魔方陣を解く関数のネストがヒドく、ちょっとどうかと思います（人のコードを移植しておいてアレですが）。
私は魔方陣を回転、鏡像を除いて列挙した上で回転、鏡像を作成しています。多分、一気に全て列挙するよりもこちらの方が速いと思うのですがどうでしょう？