the_knight's_independence.py

# -*- coding: utf-8 -*-
"""The Knight's independence.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1wbjZCI8e4ugvC-eqcC1lKysV8LoSVjj8
"""

# The Knight's Independence Problem (The k Knight's problem)
# Matheus Ribeiro Alencar https://github.com/matheusriale
import random
import copy

#initialize the chessboard
def initialize_chessboard(dim):
    matrix = []
    row = [0]*dim
    for i in range(dim):
        matrix.append(row[:]) #copy of row, no indexing problems later on
    return matrix

#Knight's move restrictions, we restrict the squares attacked
def place_attacks(pos_x,pos_y,chessboard):
    if pos_x+2<dim and pos_y +1<dim:
      chessboard[pos_x+2][pos_y +1] = 'X'
    if pos_x+2<dim and pos_y -1 >=0:
      chessboard[pos_x+2][pos_y -1] = 'X'
    if pos_x+1<dim and pos_y +2<dim:
      chessboard[pos_x+1][pos_y +2] = 'X'
    if pos_x+1<dim and pos_y -2>=0:
      chessboard[pos_x+1][pos_y -2] = 'X'
    if pos_x-2>=0 and pos_y+1<dim:
      chessboard[pos_x-2][pos_y +1] = 'X'
    if pos_x-2>=0 and pos_y-1>=0:
      chessboard[pos_x-2][pos_y -1] = 'X'
    if pos_x-1>=0 and pos_y-2>=0:
      chessboard[pos_x-1][pos_y -2] = 'X'
    if pos_x-1>=0 and pos_y+2<dim:
      chessboard[pos_x-1][pos_y +2] = 'X'

def check_attacks(chessboard):
  pos_x = None
  pos_y = None
  less_restrictions = -9        # Highest number of squares restricted by the knight's moves is 8
  A = copy.deepcopy(chessboard) # copy of chessboard
                                # Insert copies of original object, source: https://docs.python.org/dev/library/copy.html#module-copy
  for i in range(0,len(A)):
    for j in range(0,len(A)):
      restricted_fields = 0

      if A[i][j] != 'X' and A[i][j] == 0: #square available, we will check if it gets us a good solution
          if i+2<(len(A)) and j+1<(len(A)):
            if A[i+2][j +1] != 'X' and A[i+2][j +1] <= 0:
              restricted_fields = restricted_fields - 1

          if i+2<(len(A)) and j -1 >=0:
            if A[i+2][j -1] != 'X' and A[i+2][j -1] <= 0:
              restricted_fields = restricted_fields - 1

          if i+1<(len(A)) and j +2<(len(A)):
            if A[i+1][j +2] != 'X' and A[i+1][j +2] <= 0:
              restricted_fields = restricted_fields - 1

          if i+1<(len(A)) and j -2>=0:
            if A[i+1][j -2] != 'X' and A[i+1][j -2] <= 0:
              restricted_fields = restricted_fields - 1

          if i-2>=0 and j+1<(len(A)):
            if A[i-2][j +1] != 'X' and A[i-2][j +1] <= 0:
              restricted_fields = restricted_fields - 1

          if i-2>=0 and j-1>=0:
            if A[i-2][j -1]!= 'X' and A[i-2][j -1] <= 0:
              restricted_fields = restricted_fields - 1

          if i-1>=0 and j-2>=0:
            if A[i-1][j -2]!= 'X' and  A[i-1][j -2] <= 0:
              restricted_fields = restricted_fields - 1

          if i-1>=0 and j+2<len(A):
            if A[i-1][j +2]!= 'X' and A[i-1][j +2] <= 0:
              restricted_fields = restricted_fields - 1


          A[i][j] = restricted_fields

          if less_restrictions <= restricted_fields: #we keep our best solution (highest number, minimum = -8, highest = 0(best scenario))
            less_restrictions = restricted_fields
            pos_x = i
            pos_y = j


  return (pos_x,pos_y,A)

#Placing the knights
def place_knights(chessboard):
  global current_knight

  if current_knight == 1:
    first_move = True
  else:
    first_move = False
  dim = len(chessboard)

  if first_move: #On first move, we got no restrictions yet. By our heuristic, we will start in one of the 4 corners since it only blocks 2 squares

    #We will choose randomly the first square to be occupied

    corners = [0,dim-1]
    pos_x = random.choice(corners)
    pos_y = random.choice(corners)
    chessboard[pos_x][pos_y] = current_knight


    #We restrict positions on our chessboard based on the knight that was placed
    place_attacks(pos_x,pos_y,chessboard)

    current_knight = current_knight + 1


  #After first move
  else:
    for i in range(dim*dim - 1):

        pos = check_attacks(chessboard)
        if pos[0] == None:
          break
        chessboard[pos[0]][pos[1]] = current_knight  #We alocate the ith knight to the best position possible (following our heuristic).
        place_attacks(pos[0],pos[1],chessboard)

        current_knight = current_knight + 1
        #return chessboard

    return reset_chessboard()
  return

#We keep our chessboard and the number of knights on that board
#We reset the board to start another one, if necessary
def reset_chessboard():
  global chessboard_solutions
  global solutions
  global current_knight
  global chessboard

  chessboard_solutions.append(chessboard)
  n_knights = current_knight - 1
  solutions.append(n_knights)
  current_knight = 1

  dim= len(chessboard)
  chessboard = []
  row = [0]*dim
  for i in range(dim):
      chessboard.append(row[:])

  return chessboard_solutions,solutions

def branch(P): #we will branch our board P in P0 (without putting a knight on the next position) and in P1(having a knight on the next position)
  P1 = copy.deepcopy(P)
#----------------------------------------PRUNE-------------------------------------------------------
  next = 1 #variable to allow the continuation of our branches
  #check if we can prune P and consequently P1
  #verify prune comparing the best solution (putting knights in all remaining squares) with the heuristic solution
  max_knights = 0
  for i in range(len(P)):
    for j in range(len(P)):
      if P[i][j] != 'X' and (P[i][j] == 'K' or P[i][j] == 0):
        max_knights = max_knights + 1
  if max_knights < solutions[0]: #if the highest number is lower, it is not worth it, we return None
    P = None
    P1 = None
    return (P,P1,next)
#-----------------------------------------------------------------------------------------------------
  global final_solutions #vector where we will add our solutions

  next = 0
  for i in range(len(P)):
    for j in range(len(P)):
      if P[i][j] == 0: #if exists at least one 0 element (square available), we will put our markings X -> no Knight, K -> Knight
        next = 1
        P[i][j] = 'X'
        P1[i][j] = 'K'
        place_attacks(i,j,P1)
        break
    if next == 1:
      break
    else:
      if P not in final_solutions: #Discarding repeated solutions
        final_solutions.append(P)
  return (P,P1,next)

#--------------------------------------------------------- MAIN -------------------------------------------------------------------
#initializing variables and global variables (our chessboard)
dim = int(input("Chessboard dimension: \n"))
chessboard = initialize_chessboard(dim)
current_knight = 1
chessboard_solutions = []
solutions = [] #number of knights on that board
first_knight = True #for heuristic's use in first move

#--------------------------------------------------------- MAIN HEURISTIC ---------------------------------------------------------
#In this section we use our heuristic to estabilish a "good" solution
print("\n-------------------------------------------------------\n")
test_solutions = []
while len(solutions) < 1:
  test_solutions.append(place_knights(chessboard)) #keep every board solution and it's number of knights

print("By our heuristc we have:")
for i in chessboard_solutions[0]:
    print(i)
print('Highest number of knights by our heuristic:',solutions[0],'\n')

#----------------------------------------------------------------------------------------------------------------------------------
#Initializing our queue, and solutions vector
queue = [initialize_chessboard(dim)]
q_solutions = []
final_solutions = []

while len(queue) > 0:
  P = queue.pop(0)
  v = branch(P)
  if v[2] == 1:
    if v[0]!= None:
      queue.append(v[0])
    if v[1]!= None:
      queue.append(v[1])

solutions_size = len(final_solutions) #keep our number of possible solutions
for i in range(solutions_size):
    count = 0
    for j in range(dim):
      for k in range(dim):
        if final_solutions[i][j][k] == 'K':
          count = count + 1
    q_solutions.append(count) #count the number of knights per solution
    #No need to remove all lists from our queue, in the moment we got no more squares available we stop the process

print("Solutions possiblle: ", solutions_size)
max = idx = 0
for i in range(solutions_size):
  if q_solutions[i] >= max:
    max = q_solutions[i]
    idx = i

print("Highest number of knights possible: ",max)
print("Possible chessboard configuration: ")
for i in final_solutions[idx]:
  print(i)