8QUEEN.BAS and 5QUEEN.BAS 18 February 2000 by Marc Kummel aka Treebeard. Contact mkummel@rain.org, http://www.rain.org/~mkummel/ What are 8QUEEN.BAS and 5QUEEN.BAS ----------------------------------- Here are two simple BASIC programs to solve two classic chess stumpers that I recently (re)posed as stumpers at school and on my web Stumper page: Chess queens can move in a straight line any distance up, down, across, or diagonally. Can you arrange eight peaceful queens on a chessboard so that no queen can attack any other? Eight peaceful queens will threaten every square on the board, but it's overkill. What's the smallest number of warrior queens that can threaten every square? These programs use a recursive function call to test every interesting board position. 8QUEEN is a small BASIC program that solves the classic "8 Queens" problem of arranging 8 queens on a chessboard so that no queen is under attack. This becomes the more general N Queens problem of arranging N queens on an N by N chessboard. This code is modified from C++ code I found on the Web by David Sleeper at: . It finds all 92 solutions to the 8x8 problem in no time at all, but it doesn't consider symmetry. Of the 92 solutions, only 12 are unique and the remaining 80 are variations -- mirror images on horizontal, vertical, or diagonal axes, or 90, 180, or 270 degree reflections. It bogs down with large chessboards. 5QUEEN is a small BASIC program that solves the classic "5 Queens" problem of arranging 5 queens on a chessboard so that every square is attacked. This problem is not as much studied as the classic "8 Queens" problem of arranging N peaceful queens on an N x N chessboard, and it's interesting. If no solutions are found, the program returns a "best try" with a minimum of unattacked squares. It's slow because it has to try every possible position. In general for M pieces on an N by N board, that's: n! --------- positions, eg 7,624,512 for 5 queens on an 8x8 board. m! (n-m)! 5QUEEN finds all 4860 solutions of 5 queens on an 8x8 checcboard in a few minutes, and it works for the general problem. For more info on these classic stumpers, check out my "Peaceful Queens and Warriors" stumper at . There's more discussion and links at Eric Weisstein's World of Mathematics site at . Using 8QUEEN.BAS and 5QUEEN.BAS -------------------------------- These are simple DOS programs. Run them in DOS, or a Command session in Windows. There are several options that can be set from the command line. Usage: 8QUEEN [n] [/f[name.ext]] Options:" n = Size of chessboard, default is 8 x 8. [/f] = Save all solutions to file nqueens.txt or . [/?] = Help. Usage: 5QUEEN [m [n]] [/f[name.ext]] Options:" m = Number of queens on the board, default is 5. n = Size of chessboard, default is 8 x 8. [/f] = Save all solutions to file mnqueen.txt or . [/?] = Help. The Files: ----------- I wrote these programs to solve a stumper. You'll have to study the source code for more info. I wrote it using MS Basic PDS v7.10. It might need some work in QBasic, since that interpreter can't read the command line. 8QUEEN.EXE DOS executible to place peaceful queens on chessboard 8QUEENn.BAS BASIC source code 8QUEEN.TXT 92 solutions to the classic 8 queens problem NQUEEN.TXT Default file created to save results with /F option 5QUEEN.EXE DOS executible to place warrior queens on a chessboard 5QUEENn.BAS BASIC source code 5QUEEN.TXT 4860 solutions to the classic 5 queens problem MNQUEEN.TXT Default file created to save results with /F option README.TXT This file TBVAULT.TXT Treebeard's Basic Vault info Conditions: ------------ This program and source code are yours to use and modify as you will, but they are offered as freeware with no warranty whatsoever. Give me credit, but do not distribute any changes under my name, or attribute such changes to me in any way. You're on your own! If you find this program or code useful, then let me know what you do with it, as a courtesy to a fellow programmer who still hacks for fun and glory. Any suggestions or comments will be much appreciated. Send comments and fixes to: Marc Kummel aka Treebeard mkummel@rain.org http://www.rain.org/~mkummel/ http://www.treebeard.org/ For more interesting Basic software with source code, check out Treebeard's Basic Vault at .