nqueens.py

# bitwise python solution to n queens with some pretty printing
# described by Martin Richards in http://www.cl.cam.ac.uk/~mr10/backtrk.pdf

import sys
import shutil
import itertools

def tryP(ld, col, rd, all_p, cur_s):
	if (col == all_p):
		return (cur_s,)
	pos = ~( ld | col | rd) & all_p
	sols = []
	while pos:
		bit = pos & -pos
		pos &= ~bit
		sols.extend(tryP((ld|bit) << 1, col|bit, (rd|bit) >> 1, all_p, cur_s + (bit,)))
	return sols

def getBSols(n):
	# get bitmask solutions for a board size
	return tryP(0,0,0, (1<<n) -1, ())


# remove dups and convert solutions to more readable form.

def solsToPerms(bSols):
	# convert bitmask solutions to integers
	if not bSols:
		return []
	n = len(bSols[0])
	lookup = {1 << i : i for i in range(n)}
	return [tuple(lookup[p] for p in s) for s in bSols]

def rotSol(sol):
	# rotate a solution to find similar ones.
	n = len(sol)
	nSol = [0] * n
	for i, p in enumerate(sol):
		nSol[p] = n - i - 1
	return tuple(nSol)

def getVariants(sol):
	vSols = []
	for s in [sol, tuple(reversed(sol))]:
		vSols.append(s)
		for _ in range(3):
			s = rotSol(s)
			vSols.append(s)
	return vSols

def getUniqSols(n):
	sols = sorted(solsToPerms(getBSols(n)))
	seenSols = set()
	uSols = []
	for s in sols:
		if s in seenSols:
			continue
		uSols.append(s)
		seenSols.update(getVariants(s))
	return uSols


# code below here is for printing

# assumes char height is 2x width
QUEEN = "Q "
PAD = ". "

def solToStr(sol):
	n = len(sol)
	return [(PAD * p + QUEEN + PAD * (n-p-1)) for p in sol]

def gridPrint(data, max_w, fill="  "):
	data_max_w = max(max(len(r) for r in d) for d in data)
	m_cols = max_w // (data_max_w + len(fill))
	p_data = data + [[]] * (-len(data) % m_cols) 
	fmt_str = fill.join(["{: <" + str(data_max_w) + "}"] * m_cols)
	rows = []
	for i in range(0, len(p_data), m_cols):
		for tup in itertools.zip_longest(*p_data[i:i + m_cols], fillvalue=''):
			rows.append(fmt_str.format(*tup))
		rows.append('')
	return rows

def main(n=8):
	n = int(n)
	sols = getUniqSols(n)
	print("{} unique sol for n={}".format(len(sols), n))
	max_w = shutil.get_terminal_size((80, 20)).columns
	print("\n".join(gridPrint([solToStr(s) for s in sols], max_w)))


if __name__ == "__main__":
	main(*sys.argv[1:])