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:
short Board[4][4], Quad[4][4] #i.e. Quad[0][1] means quadrant 0, square 1 = a3
int x[16], y[16], whichSquare[16], whichQuad[16],codelist[200][4]
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]
whichQuad[:] = [3,3,3,3,2,2,2,2,1,1,1,1,0,0,0,0] #for each sq pos, which quadrant
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]
txt = open("/Users/admin/data.txt", "w")
cdef RotatedVersionAlreadyOnList(int code[]):
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):
Quad[i][:] = [0,0,0,0]
for i in xrange(numOfNs):
Quad[whichQuad[N[i]]][whichSquare[N[i]]] = 1
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
if Quad[i][rules[j][0]] == 1:
if Quad[(i+rules[j][1])%4][rules[j][2]] == 1:
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
score[whichQuad[N[i]]] += 2**whichSquare[N[i]]
if RotatedVersionAlreadyOnList(score):
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")
cdef AddKnight(int level,int 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
AddKnight(level+1,N)
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
AddKnight(1,N)
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.