G
Gabriel Genellina
El 9 mar, 22:57, Robin Rytich escribió:
Warnsdorff's algorithm is heuristic; it works most of the time, but in
some cases leads to a dead end and you have to backtrack and try another
alternative.
The starting square is important; if you start at 1,1 (instead of 0,0)
your program finds a solution for all those problematic board sizes.
Your implementation looks fine to me. Some comments on the code itself:
This sets a class attribute (as opposed to normal, instance attributes)
which is shared by all ChessBoard instances (this really should be covered
in the FAQ!). You really want an instance attribute here: do `self.cell =
[]` in __init__
I would process command line arguments when the script starts, and supply
size/x/y as parameters to the ChessBoard constructor. In other words, the
caller must provide those parameters, it's not ChessBoard responsability
to hunt for them.
All those six () are unnecessary.
Also, `next` might refer to integer 0 or a ChessBoardSquare instance.
That's perfectly legal in Python, but *I* prefer to assign objects of the
same type when using the same variable name. In this case, 0 is used only
as a marker, any other non-ChessBoardSquare instance would do, and I'd
substitute None instead.
(This is more than a stylistic whim: some JIT compiler may benefit from
knowing the object type won't change)
Instead of artificially iterate over the *indices* to finally reach the
objects, you may directly iterate over the board squares:
for row in self.cell:
for square in row:
print(square.status, end = '')
print()
Later:
It would be better to use meaningful names instead of applicant[0],
applicant[1] -- let me re-use y,x. We can write a more concise condition:
result = []
for y,x in applicants:
if not 0 <= y < self.size:
continue
if not 0 <= x < self.size:
continue
if self.cell[y][x].status == 0:
result.append(self.cell[y][x])
Now, lets combine all those conditions into a single one:
result = []
for y,x in applicants:
if 0 <= y < self.size and 0 <= x < self.size and
self.cell[y][x].status == 0:
result.append(self.cell[y][x])
Finally, a code pattern like the above can always be rewritten as a list
comprehension:
result = [self.cell[y][x]
for y,x in applicants
if 0 <= y < self.size and 0 <= x < self.size and
self.cell[y][x].status == 0
]
Apart from these points, your program looks fine to me. You even added
function docstrings! (ok, they might be more informative, but at least
they exist!)
I'm having some troubles with writing Knight's tour
(http://en.wikipedia.org/wiki/Knight's_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).
Warnsdorff's algorithm is heuristic; it works most of the time, but in
some cases leads to a dead end and you have to backtrack and try another
alternative.
The starting square is important; if you start at 1,1 (instead of 0,0)
your program finds a solution for all those problematic board sizes.
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?
Your implementation looks fine to me. Some comments on the code itself:
class ChessBoard:
size = 8 # Board square width and height.
cell = [] # Embedded list of board cells.
This sets a class attribute (as opposed to normal, instance attributes)
which is shared by all ChessBoard instances (this really should be covered
in the FAQ!). You really want an instance attribute here: do `self.cell =
[]` in __init__
def __init__(self):
import sys
# Reading board size.
if len(sys.argv) >= 2:
self.size = int(sys.argv[1])
I would process command line arguments when the script starts, and supply
size/x/y as parameters to the ChessBoard constructor. In other words, the
caller must provide those parameters, it's not ChessBoard responsability
to hunt for them.
if (next != 0):
(self.y, self.x) = (next.y, next.x)
All those six () are unnecessary.
Also, `next` might refer to integer 0 or a ChessBoardSquare instance.
That's perfectly legal in Python, but *I* prefer to assign objects of the
same type when using the same variable name. In this case, 0 is used only
as a marker, any other non-ChessBoardSquare instance would do, and I'd
substitute None instead.
(This is more than a stylistic whim: some JIT compiler may benefit from
knowing the object type won't change)
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[j].status, end = '')
print()
Instead of artificially iterate over the *indices* to finally reach the
objects, you may directly iterate over the board squares:
for row in self.cell:
for square in row:
print(square.status, end = '')
print()
Later:
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:
if applicant[0] < 0 or applicant[0] >= self.size:
continue
if applicant[1] < 0 or applicant[1] >= self.size:
continue
if self.cell[applicant[0]][applicant[1]].status == 0:
result.append(self.cell[applicant[0]][applicant[1]])
It would be better to use meaningful names instead of applicant[0],
applicant[1] -- let me re-use y,x. We can write a more concise condition:
result = []
for y,x in applicants:
if not 0 <= y < self.size:
continue
if not 0 <= x < self.size:
continue
if self.cell[y][x].status == 0:
result.append(self.cell[y][x])
Now, lets combine all those conditions into a single one:
result = []
for y,x in applicants:
if 0 <= y < self.size and 0 <= x < self.size and
self.cell[y][x].status == 0:
result.append(self.cell[y][x])
Finally, a code pattern like the above can always be rewritten as a list
comprehension:
result = [self.cell[y][x]
for y,x in applicants
if 0 <= y < self.size and 0 <= x < self.size and
self.cell[y][x].status == 0
]
Apart from these points, your program looks fine to me. You even added
function docstrings! (ok, they might be more informative, but at least
they exist!)