Asp Forum - Knight's tour Warndorff's algorithm problem

Gabriel Genellina

3/10/2010 5:37:00 AM

El 9 mar, 22:57, Robin Rytich escribió:

> I'm having some troubles with writing Knight's tour
> (http://en.wikipedia.org/wiki/Knigh...) solution in Python 3. I'm
> using Warnsdorff's algorithm (http://en.wikipedia.org/wi...
> 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

4 Answers

Lawrence D'Oliveiro

3/10/2010 9:50:00 PM

In message <mailman.527.1268199449.23598.python-list@python.org>, Gabriel
Genellina wrote:

> Warnsdorff's algorithm is heuristic ...

Then it shouldnâ??t be called an â??algorithmâ?.

Robert Kern

3/10/2010 10:06:00 PM

On 2010-03-10 15:49 PM, Lawrence D'Oliveiro wrote:
> In message<mailman.527.1268199449.23598.python-list@python.org>, Gabriel
> Genellina wrote:
>
>> Warnsdorff's algorithm is heuristic ...
>
> Then it shouldnâ??t be called an â??algorithmâ?.

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

Dave \Crash\ Dummy

3/10/2010 10:10:00 PM

On 2010-03-10, Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> wrote:
> In message <mailman.527.1268199449.23598.python-list@python.org>, Gabriel
> Genellina wrote:
>
>> Warnsdorff's algorithm is heuristic ...
>
> Then it shouldn???t be called an ???algorithm???.

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

3/11/2010 4:45:00 AM

On 3/10/2010 4:49 PM, Lawrence D'Oliveiro wrote:
> In message<mailman.527.1268199449.23598.python-list@python.org>, Gabriel
> Genellina wrote:
>
>> Warnsdorff's algorithm is heuristic ...
>
> Then it shouldn’t be called an “algorithm”.

Heuristic algorithms correctly compute some function, just not the one
you want ;-).

comp.lang.python

Knight's tour Warndorff's algorithm problem

Gabriel Genellina

Lawrence D'Oliveiro

Robert Kern

Dave \Crash\ Dummy

Terry Reedy

x Login to ForumsZone