Hi all
I'm having some troubles with writing Knight's tour
(http://en.wikipedia.org/wiki/Knight%27s_tour) solution in Python 3. I'm
using Warnsdorff's algorithm (http://en.wikipedia.org/wiki/Knight%
27s_tour#Algorithm) and I'm wondering why it doesn't work with boards of
certain sizes. I've written a solution and I like it but it does not
work correctly for 15x15, 26x26, 27x27 and 32x32 boards (don't know why;
checked from 5x5 to 40x40). So I'd be really glad if you tell me whether
I am too stupid for Python or for Discrete Math? In other words, did I
implemented Warnsdorff's algorithm in Python 3 correctly or maybe all my
troubles are because I haven't read tutorial with enough patience?
P.S. Warnsdorff's algorithm says that it's not really important which
square to choose between those which have equal amount of ways out. In
spite of that I tried to changed my program and added '=' to condition
at line 78. Results were quite surprising: now it works for 5x5,
6x6, ... 34x34 but not for 35x35!
#!/usr/bin/env python3
class ChessBoardSquare:
""" Class for chess board square. """
status = 0 # 0 - unvisited, 1 - visited
ways_out = 0 # Count of possible moves from this square.
x = 0 # Square's x coordinate, from left to right.
y = 0 # Square's y coordinate, from top to bottom.
def __init__(self, y, x):
(self.y, self.x) = (y, x)
class ChessBoard:
size = 8 # Board square width and height.
cell = [] # Embedded list of board cells.
move = 0 # Current move number.
x = 0 # x coordinate of square to move to.
y = 0 # y coordinate of square to move to.
def __init__(self):
import sys
# Reading board size.
if len(sys.argv) >= 2:
self.size = int(sys.argv[1])
# Reading first square to move to.
if len(sys.argv) >= 4:
self.y = int(sys.argv[2])
self.x = int(sys.argv[3])
# Creating board squares.
for i in range(self.size):
self.cell.append([])
for j in range(self.size):
self.cell[i].append(ChessBoardSquare(i, j))
# Counting ways out for every square on a board.
for i in range(self.size):
for j in range(self.size):
self.cell[i][j].ways_out = len(self.getCellNeighbours(i, j))
def makeMove(self):
""" This function makes another move. """
# Printint current move number.
self.move += 1
print(self.move, ':', sep = '')
# We have visited just another square.
self.cell[self.y][self.x].status = 1
# Now we should define where to move next and
# re-calculate possible moves from neighbours of
# current square.
neighbours = self.getCellNeighbours(self.y, self.x)
next = 0
for neighbour in neighbours:
neighbour.ways_out -= 1
if next == 0:
next = neighbour
continue
if next.ways_out > neighbour.ways_out:
next = neighbour
if (next != 0):
(self.y, self.x) = (next.y, next.x)
# And finally printing result of this move.
self.printField()
#input()
def printField(self):
""" This function prints field to standart output. """
for i in range(self.size):
for j in range(self.size):
print(self.cell[i][j].status, end = '')
#print('(', self.cell[j][j].status, ')', sep = '', end = ' ')
print()
def getCellNeighbours(self, y, x):
""" This function returns those cells which are accessible from current square. """
# Coordinates of possible neighbours.
applicants = [[y - 1, x - 2], [y - 1, x + 2],
[y + 1, x - 2], [y + 1, x + 2],
[y - 2, x - 1], [y - 2, x + 1],
[y + 2, x - 1], [y + 2, x + 1]]
result = []
for applicant in applicants:
# It's fail if out of index.
if applicant[0] < 0 or applicant[0] >= self.size:
continue
if applicant[1] < 0 or applicant[1] >= self.size:
continue
# If it is unvisited then everythin's alright and we append it to the result list.
if self.cell[applicant[0]][applicant[1]].status == 0:
result.append(self.cell[applicant[0]][applicant[1]])
return result
if __name__ == '__main__':
field = ChessBoard()
while (field.cell[field.y][field.x].ways_out != 0):
field.makeMove()
field.makeMove()
--
http://mail.python.org/mailman/listinfo/python-list
