Purpose is to show how the N Queens problem can be solved using SQL. In addition it includes XML, XSL, and Oracle Forms program to display generated solutions.
Terms of Agreement:
By using this article, you agree to the following terms...
You may use
this article in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
You MAY NOT redistribute this article (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
You may link to this article from another website, but ONLY if it is not wrapped in a frame.
You will abide by any additional copyright restrictions which the author may have placed in the article or article's description.
The N Queen problem means to find a way to place N queens on NxN chessboard so that no queen attacks any other queen. This problem was firstly introduced on 8x8 chessboard in „Illustrierte Zeitung“ in 1850. From that time many people including famous mathematician Karl Friedrich Gauss have paid attention to it. On 4x4 board there are only 2 solutions, on 8x8 one there are already 92 solutions.
This article presents the algorithm (written in PL/SQL) that solves the N Queen problem. Time spent by searching process non-linearly increases by the board size. And it (obviously) depends on server’s capacity as well: my server spent approximately 1 minute for 8x8 board, but almost 30 minutes for 9x9 board. The searching process can be interrupted to continue later on. It is also possible to pass parameter for maximal number of searched solutions.
Although full understanding requires at least intermediate knowledge of PL/SQL, XML, XSL, Oracle Forms, UML, it can be practicing example for beginners. Searching algorithm is written in PL/SQL. Created view, XML, XSL formats, or Queens.fmx (Oracle Forms application), can display solutions.
Download and unzip the file Queens.zip. Then open Queens_ReadMe.doc with instructions.
In short, Queens.zip file contains:
(1) Queens.sql, a PL/SQL executable script creating (a)table tab_Queen, (b) view tab_Queen_View, (c) package bcp_Queens, (d)directory DIR_QUEENS, (e) all solutions for 8x8 board by executing bcp_queens.prc_setqueens(8)
(2) SolutionAlgorithm.jpg, UML scheme
(3) SearchAllSolutions.jpg, UML scheme
(4) Queens.xsl – template to display *.xml files generated by bcp_queens.writeXML procedure (5) Queens8_4.xml file with reference to Queens.xsl template (open Queens8_4.xml in Mozilla or IE from version 6 to see all solutions for 8x8 board),
(6) additional 4 gif files: b.gif, w.gif, Qb.gif, Qw.gif, used by Queens.xsl template,
(7) Queens.fmx - Oracle Forms application that displays solutions' board according to the board size.
Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come
out every day, so no prevention program can catch 100% of them. For your own safety, please:
Re-scan downloaded files using your personal virus checker before using it.
NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.
If you don't have a virus scanner, you can get one at many places on the net
including:McAfee.com
Terms of Agreement:
By using this article, you agree to the following terms...
You may use
this article in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
You MAY NOT redistribute this article (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
You may link to this article from another website, but ONLY if it is not wrapped in a frame.
You will abide by any additional copyright restrictions which the author may have placed in the article or article's description.
Your feedback will be posted below and an email sent to
the author. Please remember that the author was kind enough to
share this with you, so any criticisms must be stated politely, or they
will be deleted. (For feedback not related to this particular article, please
click here instead.)
By 2 Users
Download article
