The Eight Queens Problem - Game Theory
I've always been fascinated by chess, but could never find regular challengers. So I often turned to computers and researching the mathematical aspects of chess. Many years ago, when I was in high school, and computers were about the size of a car, I attempted to solve the Eight Queens problem using what is known in computer lingo as "brute force". That is, by trying every possible combination.
If you're not familiar with the Eight Queens problem, it asks the question, "Can 8 queens be placed on a standard chessboard in such a way that none of the queens can capture one of the other queens?"
I won't get deep into a mathematical discussion of this problem, but suffice it to say that the brute force method is as naive as the mythical king who agreed to pay his minister in grains of rice - especially since the computer I was using was a huge old IBM beast about the size of a large closet.
It wasn't bad enough that I started a computer "job" attempting to try all possible combinations for placing the 8 queens on a standard 64-square chess board. I also decided to print out diagnostics for EACH attempt. And this on a giant IBM feed printer, where the paper hooked into metal pin rollers. (Laser printers didn't even exist back then.)
I was waiting in the print room for my printout, when a certain loud Italian professor in his unusual accent - that I could never figure out - came roaring into the basement room, presumably having run down from the 3rd floor. (Our high school had an agreement with the local college's computer department.)
"Who the hell crashed the computer?!!". That's all I remember. He was fuming, but upon seeing me, whom he'd known since I was a kid, he calmed down., never suspecting it was me, even with the pages of diagnostics spewing out of the printer.
My attempt to solve the Eight Queens problem was written with an erroneous infinite loop, and brought the department computer down, as well as probably wasting loads of paper. I didn't stick around. I snuck off out of there before the professor figured out it was me. Even a couple of years later, in college, when I had him for a computer science professor, he still hadn't figure out it was me.
To this day, I've never revisited the Eight Queens problem. Not even to read up on it, until now. The University of Utah website has a page discussing the "12 essentially distinct solutions" to the 8 Queens problem, as well as a graphic showing the 12 configurations. Aaron Davidson has an easy to use 8 Queens Java applet that will display solutions.
(c) Copyright: 2006-present, Raj Kumar Dash, http://www.getyergameon.com/
Technorati Tags: getyergameon, get yer game on, chess, game theory
If you're not familiar with the Eight Queens problem, it asks the question, "Can 8 queens be placed on a standard chessboard in such a way that none of the queens can capture one of the other queens?"
I won't get deep into a mathematical discussion of this problem, but suffice it to say that the brute force method is as naive as the mythical king who agreed to pay his minister in grains of rice - especially since the computer I was using was a huge old IBM beast about the size of a large closet.
It wasn't bad enough that I started a computer "job" attempting to try all possible combinations for placing the 8 queens on a standard 64-square chess board. I also decided to print out diagnostics for EACH attempt. And this on a giant IBM feed printer, where the paper hooked into metal pin rollers. (Laser printers didn't even exist back then.)
I was waiting in the print room for my printout, when a certain loud Italian professor in his unusual accent - that I could never figure out - came roaring into the basement room, presumably having run down from the 3rd floor. (Our high school had an agreement with the local college's computer department.)
"Who the hell crashed the computer?!!". That's all I remember. He was fuming, but upon seeing me, whom he'd known since I was a kid, he calmed down., never suspecting it was me, even with the pages of diagnostics spewing out of the printer.
My attempt to solve the Eight Queens problem was written with an erroneous infinite loop, and brought the department computer down, as well as probably wasting loads of paper. I didn't stick around. I snuck off out of there before the professor figured out it was me. Even a couple of years later, in college, when I had him for a computer science professor, he still hadn't figure out it was me.
To this day, I've never revisited the Eight Queens problem. Not even to read up on it, until now. The University of Utah website has a page discussing the "12 essentially distinct solutions" to the 8 Queens problem, as well as a graphic showing the 12 configurations. Aaron Davidson has an easy to use 8 Queens Java applet that will display solutions.
(c) Copyright: 2006-present, Raj Kumar Dash, http://www.getyergameon.com/
Technorati Tags: getyergameon, get yer game on, chess, game theory
posted by blogslinger at 12:32 AM
0 Comments:
Post a Comment
<< Home