# six knights

Q. How many distinct ways can 6 knights be placed on a 4 by 4 chess board, so that no knight attacks another knight? (And by distinct, rotations don’t count as a separate solution)
– from chessexpress, Sept 2017

Cython program, type `OK()` to run:

```#sixknights.pyx - placing 6 knights on a 4x4 board, rotations aren't counted.
#quarters of board are numbered 0,1,2,3 clockwise from upper left.
#squares in upper left are named 3,2 (top row) 1,0 (lower row), this is rotated for each quarter
#so e.g. 3 is the corner square in each quarter, 0 the centre square etc
#the 'score' for a quarter is the sum of powers of 2 of the knight square numbers.
#canonical order: no quarter can have a higher score than the UL quarter.
DEF NUMKNIGHTS =  6
DEF NUMRULES = 12
cdef:
int tally = 0, rules[NUMRULES][3], rulelist[36], N[6]
x[:] = [1,1,0,0,2,3,2,3,2,2,3,3,1,0,1,0] #gives the board coordinates for sq pos 0-15
y[:] = [2,3,2,3,2,2,3,3,1,0,1,0,1,1,0,0]
whichSquare[:] = [0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3] #which square in that quadrant
rulelist[:] = [3,3,0, 3,1,0, 2,1,2, 2,2,0, 2,3,2, 1,1,1, 1,2,0, 1,3,1, 0,1,3, 0,2,1, 0,2,2, 0,3,3]

for i in xrange(1,tally+1):
for j in xrange(4):
if codelist[i][0] == code[j] and codelist[i][1] == code[(j+1)%4] \
and codelist[i][2] == code[(j+2)%4] and codelist[i][3] == code[(j+3)%4]:
return True
return False

cdef int PassKnightTests(int N[], int numOfNs):
for i in xrange(4):
for i in xrange(numOfNs):
for j in xrange(NUMRULES): #rule[x,y,z] means: If Quad[i][x] == 1,
for i in xrange(4):    #and Quad[(i+y)%4][z] = 1, fail test - i.e. clashing knights
return False
return True

cdef TestAndWrite(int N[]):
global tally
cdef int score[4]
for i in xrange(4):
score[i]=0
Board[i][:] = [0,0,0,0]
for i in xrange(NUMKNIGHTS):
Board[x[N[i]]][y[N[i]]] = 1
return
tally += 1
codelist[tally][:] = score
txt.write("#%d. %d-%d-%d-%d\n" % (tally,score[0],score[1],score[2],score[3]))
for j in xrange(4):
for i in xrange(4):
txt.write("%d " % Board[i][j])
txt.write("\n")

if level>1:
if not PassKnightTests(N,level):
return
if level == NUMKNIGHTS: #have placed knights 0-5 already
TestAndWrite(N)
else: #place next knight
if N[level-1]>0: #room for another knight
for i in xrange(N[level-1]-1,-1,-1): # i.e. go down to 0
N[level] = i #place Knight no. 'level' on square i

cpdef OK():
for i in xrange(NUMRULES):
for j in xrange(3):
rules[i][j] = rulelist[i*3+j]
N[:] = [0,0,0,0,0,0]
for i in xrange(15,12,-1): #first knight can be only in pos 15-13, w.l.o.g
N[0] = i
txt.write("Found %d.\n" % tally)
txt.close()
```

Which produces the file:

```#1. 14-8-12-0
1 1 0 1
1 0 0 0
0 0 0 0
0 0 1 1
#2. 14-8-10-0
1 1 0 1
1 0 0 0
0 0 0 1
0 0 0 1
#3. 14-8-8-8
1 1 0 1
1 0 0 0
0 0 0 0
1 0 0 1
#4. 14-8-6-0
1 1 0 1
1 0 0 0
0 0 0 1
0 0 1 0
#5. 14-8-4-8
1 1 0 1
1 0 0 0
0 0 0 0
1 0 1 0
#6. 14-8-2-8
1 1 0 1
1 0 0 0
0 0 0 1
1 0 0 0
#7. 14-0-14-0
1 1 0 0
1 0 0 0
0 0 0 1
0 0 1 1
#8. 14-0-12-8
1 1 0 0
1 0 0 0
0 0 0 0
1 0 1 1
#9. 14-0-10-8
1 1 0 0
1 0 0 0
0 0 0 1
1 0 0 1
#10. 14-0-6-8
1 1 0 0
1 0 0 0
0 0 0 1
1 0 1 0
#11. 13-2-8-2
1 1 1 0
0 1 0 0
0 0 0 0
0 1 0 1
#12. 12-10-12-0
1 1 1 1
0 0 0 0
0 0 0 0
0 0 1 1
#13. 12-10-8-8
1 1 1 1
0 0 0 0
0 0 0 0
1 0 0 1
#14. 12-10-8-2
1 1 1 1
0 0 0 0
0 0 0 0
0 1 0 1
#15. 12-10-4-8
1 1 1 1
0 0 0 0
0 0 0 0
1 0 1 0
#16. 12-10-4-2
1 1 1 1
0 0 0 0
0 0 0 0
0 1 1 0
#17. 12-10-0-10
1 1 1 1
0 0 0 0
0 0 0 0
1 1 0 0
#18. 12-8-12-8
1 1 0 1
0 0 0 0
0 0 0 0
1 0 1 1
#19. 12-8-12-2
1 1 0 1
0 0 0 0
0 0 0 0
0 1 1 1
#20. 12-8-10-8
1 1 0 1
0 0 0 0
0 0 0 1
1 0 0 1
#21. 12-8-8-10
1 1 0 1
0 0 0 0
0 0 0 0
1 1 0 1
#22. 12-8-6-8
1 1 0 1
0 0 0 0
0 0 0 1
1 0 1 0
#23. 12-8-4-10
1 1 0 1
0 0 0 0
0 0 0 0
1 1 1 0
#24. 12-2-12-2
1 1 1 0
0 0 0 0
0 0 0 0
0 1 1 1
#25. 12-2-8-10
1 1 1 0
0 0 0 0
0 0 0 0
1 1 0 1
#26. 12-2-4-10
1 1 1 0
0 0 0 0
0 0 0 0
1 1 1 0
#27. 11-4-8-4
1 0 0 0
1 1 0 1
1 0 0 0
0 0 0 1
#28. 10-8-10-8
1 0 0 1
1 0 0 0
0 0 0 1
1 0 0 1
#29. 10-8-10-4
1 0 0 1
1 0 0 0
1 0 0 1
0 0 0 1
#30. 10-8-6-8
1 0 0 1
1 0 0 0
0 0 0 1
1 0 1 0
#31. 10-4-10-4
1 0 0 0
1 0 0 1
1 0 0 1
0 0 0 1
#32. 9-6-9-0
1 0 1 0
0 1 0 1
0 0 1 0
0 0 0 1
#33. 9-6-8-4
1 0 1 0
0 1 0 1
1 0 0 0
0 0 0 1
#34. 9-6-8-2
1 0 1 0
0 1 0 1
0 0 0 0
0 1 0 1
#35. 9-6-1-4
1 0 1 0
0 1 0 1
1 0 1 0
0 0 0 0
#36. 9-6-1-2
1 0 1 0
0 1 0 1
0 0 1 0
0 1 0 0
#37. 9-6-0-6
1 0 1 0
0 1 0 1
1 0 0 0
0 1 0 0
#38. 9-4-9-4
1 0 0 0
0 1 0 1
1 0 1 0
0 0 0 1
#39. 9-4-9-2
1 0 0 0
0 1 0 1
0 0 1 0
0 1 0 1
#40. 9-4-8-6
1 0 0 0
0 1 0 1
1 0 0 0
0 1 0 1
#41. 9-4-1-6
1 0 0 0
0 1 0 1
1 0 1 0
0 1 0 0
#42. 9-2-9-2
1 0 1 0
0 1 0 0
0 0 1 0
0 1 0 1
#43. 9-2-8-6
1 0 1 0
0 1 0 0
1 0 0 0
0 1 0 1
#44. 9-2-1-6
1 0 1 0
0 1 0 0
1 0 1 0
0 1 0 0
#45. 8-6-8-6
1 0 1 0
0 0 0 1
1 0 0 0
0 1 0 1
#46. 8-6-1-6
1 0 1 0
0 0 0 1
1 0 1 0
0 1 0 0
#47. 6-1-6-1
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
Found 47.
```