Register | Sign In


Understanding through Discussion


EvC Forum active members: 65 (9162 total)
6 online now:
Newest Member: popoi
Post Volume: Total: 915,817 Year: 3,074/9,624 Month: 919/1,588 Week: 102/223 Day: 13/17 Hour: 0/0


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Author Topic:   Design without a designer?
Rrhain
Member
Posts: 6351
From: San Diego, CA, USA
Joined: 05-03-2003


Message 8 of 14 (59023)
10-01-2003 11:15 PM


I'm reminded of an assignment given in a computer science class:
Write a program that attempts to find a knight's tour of a chessboard. For bonus points, determine if the tour is cylical.
That was about it. For those who don't know, a knight's tour is where you take a knight and, using only the moves allowable by a knight, try to traverse the entire chessboard, landing on each square only once. It's "cyclical" if the last square is a knight's move from the first square.
How to go about this? Well, you first need to model the chessboard. That's simple...an 8x8 array. But then we notice that not all moves are possible on all squares. From the corner squares, there are only two possible moves.
What I noticed was that if you had moved to a corner, you actually only had one possible move left since the other one was the square you just came from which you could no longer land on. So instead of allowing all possible moves from the corner, you should restrict each space to have only legal moves available. But along those lines, I got to thinking if there was a "favorable" direction to move in general. Might certain types of moves be more likely to arrive at a knight's tour than others? Perhaps there was a way to restrict the possible moves for each square....
And after a little bit of playing around with a real knight and chessboard, I found a cyclical knight's tour. And thus, I programmed each square with only two possible moves. Thus, no matter what square you started on, you were guaranteed to get a cyclical knight's tour.
But the thing is, it was always the same tour. The only difference between one square and the next would be whether it started going in one direction or the other.
Since the assignment didn't say how to accomplish the finding of the tour, my program received an A, but it sorta missed the point. The program wasn't really finding the tour.
Some other people actually gave their algorithms a memory. That is, the knight would just start moving around the board, keeping track of the moves, so that if the knight got stuck and yet still not have found a tour, it could backtrack until it found a new direction it hadn't gone and try again.
Now, this isn't quite enough because, depending on how the algorithm searched for moves, you could get the same tour for any given starting point. That is, starting square A would give you a different tour from square B, but you always get the same tour when you start from A. This would happen if each square listed the 8 possible moves in the same order and it always chose the same direction to move first, second, etc.
There is, of course, a way to fix this: Randomize the direction of the next move. Keep track of which moves resulted in failure, but when you get back to a square with an option, don't "rotate one move clockwise" but rather "choose a random direction not tried."
A program of that final type could give you different tours, even when starting on the same square.
So do we see how simple rules can come up with complex patterns? How the claim of "the computer was programmed with the answer" is silly? Yeah, my version was me programming the computer with the answer, but that isn't the only way to do it.
------------------
Rrhain
WWJD? JWRTFM!

  
Newer Topic | Older Topic
Jump to:


Copyright 2001-2023 by EvC Forum, All Rights Reserved

™ Version 4.2
Innovative software from Qwixotic © 2024