Eight Queens Solver Desktop Application
Note that this is not my first wxPython 4 application, nor my first Python 3 design. The learning curve was moderate.
- The application shall be cross-platform between Windows 10 Pro 20H2, Ubuntu 2018.04 LTS, and macOS 10.15 Catalina.
- The application shall be possible to distribute closed-source by not relying upon a copy-left graphical toolkit.
- The application shall search for all chess board permutations without using a brute-force approach.
- The application shall graphically represent the chess board with eight queen pieces.
- The application shall be capable of displaying any of the 92 puzzle solutions, one at a time.
- The application shall use the wxWidgets 3.0.x/3.1.x graphical toolkit via wxPython 4.x for the design of the window frame and controls.
- The Anaconda3 2020.11 distribution shall be used as the Python 3 installation of choice.
- The application shall provide solutions ordered as a depth-first traversal of the chess board rows, solving the puzzle in like fashion as a human would solve on a physical board.
- Examples in the blog post shall give more than hints as this puzzle is well discussed on-line.
Eight Queens Solver App, Python, on macOS Catalina.
Eight Queens Solver App, Python, on Ubuntu 18.04 LTS.
Eight Queens Solver App, Python, on Windows 10 20H2.
Hints for cross-platform design
pip install wxPython
For macOS 10.15 and Windows 10 a Wheel package can be downloaded by
provide the necessary binaries of wxWidgets 3 to support the wxPython 4.
For Ubuntu Linux, the
pip command will attempt to compile wxWidgets and
wxPython from source. The wxPython 4 wheel may not compile correctly if your
system is not configured for from-source compilation. By passing
pip install the compilation process will be visable.
WARNING remarks from the ./configure script reveal what headers are required
to be installed via the Ubuntu
apt-get package management. This can include
g++ compiler, as well as
libnotify and more. On Ubuntu, the command
dpkg-query --list can be used
to view what packages are installed, and give clue as to which headers of which
version of an already installed library should be downloaded.
Running the wxPython 4 application with main loop
Note that the following method of constructing a wx.App and running its
MainLoop() call interferes with the Spyder 4 IDE debugging. The command-line
debugger can still be invoked by adding the pdb argument to the python
python3 -m pdb weather_app.py
#!/usr/bin/env pythonw # """This module when called as main instantiates the Eight Queens Solution Application window and runs.""" import wx # pylint: disable=no-member import queens_frame DEBUG_WX_FRAME = False class QueensApp(wx.App): """This class when instantiated and .MainLoop() called, executes a wxpython application for interactive eight queens solutions calculations.""" def __init__(self): """Instantiate a QueensApp object that controls the execution of this wxpython application.""" super(QueensApp, self).__init__() self._frame = None def OnInit(self): # pylint: disable=invalid-name """Called when this wxpython app is initialized and starts main loop.""" self._frame = queens_frame.QueensFrame(None) self._frame.Show() return True # Executed when the queens_app module is called directly as a script. if __name__ == "__main__": app = QueensApp() if DEBUG_WX_FRAME: wx.lib.inspection.InspectionTool().Show() app.MainLoop()
Running the Python app with Framework support on Ubuntu
$ which python3 /home/timothystotts/anaconda3/bin/python3 $ python3 queens_app.py
Running the Python app Framework support on macOS 10.15
$ which pythonw /Users/timothystotts/opt/anaconda3/bin/pythonw $ pythonw queens_app.py
Running the Python app Framework support on Windows 10
Run the Anaconda3 Powershell Prompt
Eight Queens Solver Algorithm implementation
(The execution times were measured with Anaconda 2020.11 Python 3.8 on macOS Catalina 10.15.7 with all updates.)
The chess board was represented as a 8 row list of 9 column lists. The lists contain only Boolean values of True or False. The board is initially populated with one queen per row positioned in column 8 (of zero to eight), representing the queen piece not being placed on the board. From there, a piece is placed at row 0, then row 1, and so forth. Each time a row is placed, the line of sight (rook, bishop, lines of sight) is determined between that row and each of the above rows, the previous row and each of the above rows, back to row 0. A slow and overly computational test of the above rows would be:
def test_above(self, above_row): ret = True for j in range(above_row, -1, -1): # let be row 2, 1, 0 idx = self._chessboard[j].index(True) # let be col c for k in range(j - 1, -1, -1): # let be row 1, 0 chkidx = self._chessboard[k].index(True) # let be col b if (chkidx == idx): ret = False elif (abs(chkidx - idx) == abs(j - k)): ret = False return ret
With this implementation, the puzzle solver finds 92 correct answers and
computes all of them in 0.116s time, compared to the 0.073s of the instructor’s
nqueens.py implementation. There is an optimization possible here. For each
row above which was already successfully placed, that row has already been
tested for line-of-sight. Thus, we only need to test the row we are currently
placing. The optimization is:
def test_above(self, above_row): ret = True j = above_row # let be row 2 idx = self._chessboard[j].index(True) # let be col c for k in range(j - 1, -1, -1): # let be row 1, 0 chkidx = self._chessboard[k].index(True) # let be col b if (chkidx == idx): ret = False elif (abs(chkidx - idx) == abs(j - k)): ret = False return ret
With this optimization to the puzzle solver, the solver finds 92 correct
answers and computes all of them in 0.044s time. Each row is placed one column
at a time; and the solver moves to the next row if the line can be placed
True; and if the row cannot be placed, it is
marked in column 8 as True, and the previous row is tested to be placed at a
further down-the-row position; iteratively for the whole board.
One minimal change was made after completing the program. It is arguable that setting a full row to a new value should be done with class constants instead of inline constants. The calculation class now looks like:
class QueensCalc: """A combined data and behavior definition of a single iteration, or all iterations, of calculating the Eight Queens solution.""" BOARD_N = 8 ROW_EMPTY = [False, False, False, False, False, False, False, False, False] ROW_UNPLACED = [False, False, False, False, False, False, False, False, True] def __init__(self):
and setting a row looks like:
self._chessboard[cur_row] = copy.copy(self.ROW_UNPLACED)
self._chessboard[cur_row] = [False, False, False, False, False, False, False, False, True]
With this style change to the puzzle solver, the solver finds 92 correct answers and computes all of them in 0.048s time. The performance impact was minimal.