【剑指offer】面试题28的练习题：正方体，八皇后

【剑指offer】面试题28的习题：正方体，八皇后

test1 的判定函数：

'''
	@ sum(1,2,3,4) = sum(5,6,7,8) and 
	@ sum(1,2,5,6) = sum(3,4,7,8) and
	@ sum(1,3,5,7) = sum(2,4,6,8)
	@ used for test 1
'''
def sumEqual(data):
	eq1 = sum(data[0:4]) == sum(data[4:8])

	eq2 = sum(data[i << 1] for i in range(4)) == \
		  sum(data[i << 1 | 1] for i in range(4))

	eq3 = sum(data[0:2]) + sum(data[4:6]) == \
		  sum(data[2:4]) + sum(data[6:8])

	return eq1 and eq2 and eq3

test 2 的判定函数：

'''
	@ for square matrix, the slop is +1 or -1, means
	@ abs(p.x - q.x) == abs(p.y - q.y)
	@ for data[], we make index i stand for row(coordinate x) i, and 
	@ data[i] stand for col(coordinate y) data[i], so the conflict 
	@ condition is: abs(i - j) == (data[i] - data[j])
	@ used for test 2
'''
def NotConflict(data):
	for i in range(len(data) - 1):
		for j in range(i + 1, len(data)):
			if abs(i - j) == abs(data[i] - data[j]):
				return False
	return True

主体：

cnt = 0 

'''
	@ get all the permutition of data and print ones that s.t. cf,
'''
def permutition(data, start, cf):
	if len( data ) <= 1:
		return 
	if cf(data):
		print data
		global cnt;
		cnt += 1
	for i in range(start, len( data ) - 1):
		for j in range( i + 1, len( data )):
			data[i], data[j] = data[j], data[i]
			permutition(data, i + 1, cf)
			data[i], data[j] = data[j], data[i]


if __name__ == '__main__':
	data = [0,1,2,3,4,5,6,7,8]
	permutition(data, 0, cf = NotConflict)
	print cnt