CODEWITHSUNDEEP
pythonknights-tour
Lashen
Lashen

Reputation: 427

Python Knight's Tour Special Program

I want to make a program where I can input a:

I want it in this format:

Size: 10 Moves: 2 Knight: 2,4

2 . . 1 2 1 . . 2 .

. 2 1 2 . 2 1 2 . .

2 . 2 . 0 . 2 . 2 .

. 2 1 2 . 2 1 2 . .

2 . . 1 2 1 . . 2 .

. 2 . 2 . 2 . 2 . .

. . 2 . 2 . 2 . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

The numbers above are the number of moves made to come to the area. My problem is that I don't know how to write down the corresponding number on the board for how many moves each square took and am having trouble limiting it to a specific value so that the program won't keep looking for squares even after reaching the specified limit.

The code below for now uses 'X' in place of the numbers and '.' in place of the knight's position. The 0's are a place holder for the '.' used to indicate an empty spot.

Here is my code:

chess_board = []
size = 10

for i in range(size):
  row = []
  for j in range(size):
    row.append(0)
  chess_board.append(row)

def print_board():
    for i in range(size):
        for j in range(size):
            print(chess_board[i][j], end=" ")
        print("\n")




def get_possibilities(x, y):
    pos_x = (2, 1, 2, 1, -2, -1, -2, -1)
    pos_y = (1, 2, -1, -2, 1, 2, -1, -2)
    possibilities = []
    for i in range(len(pos_x)):
        if x+pos_x[i] >= 0 and x+pos_x[i] <= (size-1) and y+pos_y[i] >= 0 and y+pos_y[i] <= (size-1) and chess_board[x+pos_x[i]][y+pos_y[i]] == 0:
            possibilities.append([x+pos_x[i], y+pos_y[i]])

    return possibilities

def solve():
    counter = 2
    x = 2
    y = 4
    chess_board[x][y] = '.'
    for i in range((size*2)-1):
        pos = get_possibilities(x, y)
        minimum = pos[0]
        for p in pos:
            if len(get_possibilities(p[0], p[1])) <= len(get_possibilities(minimum[0], minimum[1])):
                minimum = p
        x = minimum[0]
        y = minimum[1]
        chess_board[x][y] = 'x'
        counter += 1

solve()    
print_board()

Upvotes: 0

Views: 132

Answers (2)

trincot
trincot

Reputation: 350137

A breadth-first traversal will avoid the need for correcting earlier stored values downward, because breadth-first guarantees that the first visit to a square will be via the shortest path:

knight_moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

def move_knight(size, x, y, limit_max):
    board = [["."] * size for _ in range(size)]
    if not (0 <= x < size and 0 <= y < size):
        return board
    frontier = [[x, y]]
    for distance in range(limit_max + 1):
        for x, y in frontier:
            board[x][y] = str(distance)
        frontier = {
            (x1, y1)
            for x, y in frontier
            for dx, dy in knight_moves
            for x1, y1 in [(x + dx, y + dy)]
            if 0 <= x1 < size and 0 <= y1 < size and board[x1][y1] == "."
        }
    return board


size = int(input("Size: "))
moves = int(input("Moves: "))
x, y = map(int, input("Knight: ").split(","))
print()

board = move_knight(size, x, y, moves)
print("\n".join([" ".join(row) for row in board]))

Upvotes: 0

Lashen
Lashen

Reputation: 427

I managed to get an answer:

possible_x = [1, 1, -1, -1, 2, 2, -2, -2]
possible_y = [2, -2, 2, -2, 1, -1, 1, -1]

board = []
def makeBoard(size, board):
  for row in range(size):
    row_list = []
    for column in range(size):
      row_list.append(". ")
    board.append(row_list)
  return board

def limit(size, x, y):
  if(x >= 0 and x < size and y >= 0 and y < size):
    return True
  else:
    return False
  
board = []

def moveKnight(size, x, y, check, limit_max, start_x, start_y):
  for index in range(len(possible_x)):
    if check >= limit_max:
      break
    nextX = possible_x[index] + x
    nextY = possible_y[index] + y
    if limit(size, nextX, nextY):
      if '.' in board[nextX][nextY] or int(board[nextX][nextY].rstrip()) > check+1:
          board[nextX][nextY] = str(check+1)+' '
          moveKnight(size, nextX, nextY, check+1, limit_max, start_x, start_y)
        
  board[start_x][start_y] = '0 '

size = int(input("Size: "))
moves = int(input("Moves: "))
knight_posX, knight_posY = input("Knight: ").split(",") 

board = makeBoard(size, board)

moveKnight(size, int(knight_posX), int(knight_posY), 0, moves, int(knight_posX), int(knight_posY))
print('\n'.join([''.join(row).rstrip() for row in board]))

Upvotes: 0

Related Questions