Knight's tour Warndorff's algorithm problem
Robin Rytich
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!
Gabriel Genellina
> 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).
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[i][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!)
--
Gabriel Genellina
Robin Rytich
> 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.
Wow, didn't know about that. It seems to be a good idea for me to make a
little research around this question.
> 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!).
Damn, I'm ashamed.
About other points, I actually totally agree with you (and corrected
almost everything before received your letter). Thank you for your
remarks, I'll review public code more careful next time.
Robin Rytich
Terry Reedy
>> if (next != 0):
>> (self.y, self.x) = (next.y, next.x)
In Python3, next is a builtin function.
Choose a different name, at least in public code ;=).
Lawrence D'Oliveiro
Genellina wrote:
> Warnsdorff's algorithm is heuristic ...
Then it shouldn’t be called an “algorithm”.
Robert Kern
There are lots of algorithms that use heuristics or are heuristics. The two are
orthogonal concepts.
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco
Grant Edwards
> In message <mailman.527.12681994...@python.org>, Gabriel
> Genellina wrote:
>
>> Warnsdorff's algorithm is heuristic ...
>
Why? An algorithm is just a well-defined series of steps.
Just because it uses heuristics doesn't mean it's not an algorithm.
In my book it's still an algorithm even if it never produces a correct
result. It's just not a very _good_ algorithm. :)
--
Grant Edwards grant.b.edwards Yow! YOU PICKED KARL
at MALDEN'S NOSE!!
gmail.com
Terry Reedy
Heuristic algorithms correctly compute some function, just not the one
you want ;-).