WqGStep2.exe is a Windows®-based program that finds solutions to the "N-Queens on an N by N chess board" puzzle, for board sizes from 1 square by 1 square (a hypothetical board of course!) up to 32 squares by 32 squares. It shows a simple graphical board display and gives plain-English descriptions of some of the results of its calculations.
|
Screen-captures
from the program. On the left, it's nearly half way through its discovery of all 15 x 15 solutions. On the right, it has found the first-possible solution for the 32 x 32 board. Click the pictures to see full-sized versions |
 |
This simple demo
program has a maximum
board size
of 32 x 32 squares.
A specific aim of the program is to accompany my related entries in the On-Line Encyclopedia of Integer Sequences (OEIS). The two OEIS sequences ( A140450 and A141843 ) show respectively how many tentative Queen placements are needed to find the first puzzle-solution for various board sizes, and the list of First Solutions I've discovered so far.This is a lightweight program, with no bells or whistles, and it has not been optimised for speed or for a great User experience! In the 10 years or so since it was written it has spawned many more sophisticated later versions, but this 'minimalist' version contains enough functionality to illustrate some aspects of my Queens solution-seeking algorithm.
The "tentative Queen placement" algorithm employed by the program is explained on my Queen-placement example page.
Program Operation
As soon as the program is started it begins seeking the FIRST solution to the "N-Queens" puzzle for the size of board that was set the last time the program was executed. When it is run for the first time, the board size will be the familiar 8 squares by 8 squares.
The program has a 'Tick box' option so the User can choose either -
- To stop seeking solutions as soon as the first possible
solution is
identified.
(This is the default option when the program is first launched)
or - To continue seeking all solutions for the current board
size.
For example, there are 92 possible solutions for an 8 x 8 board.
(The option to seek ALL solutions is now only available for boards of 15 x 15 or smaller.)
- "Restart" Restarts a search for solutions for the current board size.
- "Stop" Stops seeking solutions!
- (Tick-box) An option whether or not to "Stop on First Solution Found".
- "Down" Reduce the size of the 'board' (The minimum size is an infeasible 1 x 1).
- "Up" Increase the size of the 'board' (The maximum size is 32 x 32 squares).
Note: (A minor oddity) - The "Up" and "Down" buttons can be clicked even while the program is busy, but occasionally this may cause the program to lose track of what you want and it will simply "Stop" instead! So please pause briefly between each click on those buttons, and allow the program to keep up with your wishes.
WqGStep2's Default Starting State
When WqGStep2 starts for the first time, it uses the following settings:
- The program window opens near top-left of the Desktop.
- The window size is set to 610 pixels wide by 590 pixels high.
- The Board size is set to 8 squares by 8 squares.
- The option to "Stop on First Solution Found" is set to ON.
The Results Of Solution-Searches
The progress of the search and the results so far are shown in plain text in the upper part of the program's window. Any line of text that has nothing significant to report is coloured grey. A graphical display of the board is shown at the bottom of the window, and little "Queens" will appear on the board (really just asterisks) whenever a solution is discovered.
If the User has chosen NOT to "Stop on First Solution Found", then the Queens will be seen 'moving' progressively across the board in one-second snapshots as the program continues to seek ALL possible solutions. In this case, once the last solution is discovered and counted, the Queens will remain visible on the board in that last-solved pattern. (Note that the last-solved pattern is always just a mirror image of the first possible solution!)
If the board size is increased to the point where it would clash with the text lines above, then the board turns a subdued grey colour as a warning that all Rows of the board may NOT now be visible. This will not affect the search for solutions. The full coloured board will re-appear if the window size is increased to accommodate the larger board.
This version of the program has no way of saving its results to disk. I repeat that WqGStep2 is intended only to show a sub-set of all the possible data that could be gleaned during searches for solutions to this puzzle, while using one specific search algorithm.
Program Limitations
The mathematics library with which I compiled this program has an internal storage limit for unsigned integers, of 32-bits. When working on board sizes of 16 x 16 and larger, an overflow error would occur as the program accumulated its count of the "number of Queens placed", because the counter would exceed the value of 4,294,967,295 which is the limit for a 32-bit unsigned integer. To avoid this overflow, I have limited the program so that a search for ALL solutions for a board size is now only possible for sizes 15 x 15 or smaller. The size of the board can still be increased up to 32 x 32, but sizes of 16 x 16 and larger will now always stop on the first solution found.
Download Details
WqGStep2.exe is a standalone program which needs no installation. After you've extracted it from the downloaded .ZIP file it can be stored in and executed from any folder on your PC. It contains no advertising, no banners, no malware and no viruses. It has been checked with F-PROT Antivirus for Windows). The program is not capable of connecting to the Internet.
In order to remember some User preferences, the program will try to write only to its .ini file (see Operating System Compatibility below), but it does not modify any other part of your PC. It does not write to your PC's Registry and it does not read from your PC's Registry.
| File Name | Version | File-Modified Date | MD5 Hash | |
| WqGStep2.zip | (Right-click to download) | n/a | 27 Oct 2008, 04:59 | fc9237b6e9ec89e3d79b7574016aa046 |
| WqGStep2.exe | (contained in the .zip file) | 2.2.0.1 | 27 Oct 2008, 03:34 | 04dd953d0447f84e3276a558d54a8456 |
| ReadMe for WqGStep_exe 2_2_0_1.txt | (contained in the .zip file) | n/a | 27 Oct 2008, 04:20 | a34f8271b478bec87957e731b7f0a0f9 |
The ReadMe for WqGStep_exe 2_2_0_1.txt file is a plain-text version of the information on this page.
Operating System Compatibility
WqGStep2.exe is compiled as a WIN32s®-based program and is compatible with all versions of Microsoft Windows® including Windows 95, Windows 2000 and Windows XP. It will run happily on Windows Vista and on Windows 7, but see the following paragraphs about how WqGStep2 remembers its settings and your User preferences.
Due to its earlier code base, this program maintains its settings such as window position and size, plus the last-searched board size, not in the computer's Registry, but instead in a .ini file called WqGStep2.ini. This .ini file is created (when possible) the first time the program is launched, and it is stored in the "\Windows" folder on the PC on which it is run. If the currently logged in User does not have file-write permissions to the "\Windows" folder then the program will still function happily, but it won't be able to remember your preferences. Windows Vista and Windows 7 will (usually) prevent any program from writing directly to the "\Windows" folder, so in these cases too, WqGStep2 will always start with its programmed-default settings.
The program automatically learns where the "\Windows" folder is on any version of Microsoft Windows® by using a standard Windows Application Programming Interface (API) call to look at the PC's Environment variable called %WINDIR%. We don't need to tell it where to find "\Windows" on your PC.
Licence
The WqGStep2.exe program is not covered by the Creative Commons Licence that applies to all other parts of this web site. But otherwise, WqGStep2.exe is a FREE program. You can distributed it freely, but only in an unmodified form and provided that it is accompanied by the notes which are included in the ZIP file as downloaded from this site. The C++ code is not available for distribution and I have no plans at present for any further support or development of the program.
DISCLAIMER:
As the author of this
program I believe it to be safe and free of serious bugs. By
downloading and unzipping this program you expressly agree that you
accept it "AS IS" and that you will use it entirely at your own risk.
You further agree that you understand and accept the following
conditions for its use: I do not warrant the suitability of
this program for any purpose and I disclaim any
liability to any third party anywhere in the world
for any injury, loss or damage, direct or
indirect, or for any other loss suffered as a result
of its use or storage on your computer, to
the maximum extent permitted by law. Colin S
Pearson
27th October 2008
