A cross-platform Eight Queens problem solver application in C++

clinic-answer-eight-queens-cpp

Eight Queens Solver Desktop Application

Example answer to the Eight Queens Puzzle of Chapter 3 of the LinkedIn Learning: Code Clinic: C++.

Note that this is not my first wxWidgets C++ application. The learning curve was moderate; and wxPython 4 was one tool used to prototype the application in Python before implementing in C++.

Derived requirements:

• The application should be cross-platform between Windows 10 Pro 20H2, Ubuntu 2018.04 LTS, and macOS 10.15 Catalina.
• The application should 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.

Refined requirements:

• The application shall use the wxWidgets 3.0.x/3.1.x graphical toolkit for the design of the window frame and controls.
• The application shall use Boost C++ 1.74.0, or similar version.
• 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.

Solution 1/92

Solution 2/92

Eight Queens Solver App, Python, on Ubuntu 18.04 LTS.

Solution 2/92

Eight Queens Solver App, Python, on Windows 10 20H2.

Solution 2/92

Hints for cross-platform design

Location of the resource files (the PNG images)

    // Determine the path to the resource files based upon platform/OS.
#ifdef __WXMSW__
    _resourcesPath = std::string(".");
#endif

#ifdef __WXGTK__
    _resourcesPath = std::string(".");
#endif

#ifdef __WXOSX__
    wxStandardPaths stdPaths = wxStandardPaths::Get();
    wxString resourcePath = stdPaths.GetResourcesDir();

    _resourcesPath = resourcePath.ToStdString();
#endif

Example compiling on Ubuntu with clang++

apt-get install clang-10 wx3.0-headers \
	libwxgtk3.0-dev libwxgtk3.0-gtk3-dev \
	libboost-all-dev 

#!/bin/bash
mkdir -p ./Debug/
clang++-10 *.cpp \
	$(wx-config --cxxflags --libs) \
	-std=c++14 -g -O0 -o Debug/QueensApp.elf

Example running on Ubuntu once the program is compiled

#!/bin/bash
./Debug/QueensApp.elf

Compiling with Xcode 12.4 on macOS 10.15

port install boost

• Re-use the minimal_cocoa Xcode project from the wxWidgets-3.1.4 samples/ directory (from the full downloaded wxWidgets source). Configure to compile wxWidgets as part of the Xcode project hierarchy.
• Remove demo sources from IDE folder src/ .
• Add C++ sources IDE folder src/ .
• Add macports /opt/local/include/ to header paths.
• Have the Xcode subproject build the app-dynamic target with -std=c++14 or -std=gnu++14 .
• Embed & Sign the resulting wxWidgets .dylib into the Xcode application bundle.

Example running on macOS 10.15 once the program is compiled

• Select the menu: Product -> Run

Example compiling on Windows 10 with Visual Studio 2019

• Install boost 1.74.0 source.
• Install wxWidgets 3.1.4 source and binaries. For the binaries, separate the .lib files into a _lib directory and the .dll files into a _dll directory.
• Add the C:\wxWigets-3.1.4\lib\vc14x_x64_dll directory to the system PATH variable.
• In Visual Studio 2019, properties to set on the project:
  • In Property Manager, add C:\wxWidgets-3.1.4\wxwidgets.props to the execution configurations of the project.
  • In VC++ Directories:
    • Add C:\wxWidgets-3.1.4\lib\vc14x_x64_lib as a Library Directory
  • In C/C++ All Options:
    • Add C:\boost_1_74_0 to Additional Include Directories
    • As needed, select from the following for Preprocessor Definitions: WIN32;DEBUG;_DEBUG;_WINDOWS;__WXMSW__;__WXDEBUG__;_UNICODE;WXUSINGDLL; wxMSVC_VERSION_ABI_COMPAT;_CRT_SECURE_NO_WARNINGS;_CRT_SECURE_NO_DEPRECATE; _CRT_NONSTDC_NO_DEPRECATE;
  • In Linker All Options:
    • Add $(wxRootDir)\lib\$(wxCompilerPrefix)$(wxArchSuffix)_lib;$(wxLibOrDllDir); to Additional Library Directories.

Example running on Windows 10 once the program is compiled

• Select the menu: Debug -> Run

Eight Queens Solver Algorithm implementation

The chess board was represented as a 8 row array of 9 column bit bitset. The bitsets 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, back to row 0. 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.

#define BOARD_N 8
#define BOARD_NP1 9

typedef std::array<std::bitset<BOARD_NP1>, BOARD_N> t_chessmatrix;

/*!
 * \brief Returns the position where a row has a True value.
 * If multiple returns -2. If none returns -1.
 */
int QueensCalc::ChessMatrixIndex(const t_chessmatrix& board, int row)
{
    int ret = -1;
    bool found = false;

    for (int j = 0; j < board[row].size(); ++j)
    {
        if (board[row][j] == true)
        {
            if (found == true)
                ret = -2;
            else
            {
                found = true;
                ret = j;
            }
        }
    }

    return ret;
}

/*!
 * \brief Test that the current placed row aboveRow has no Rooke or Bishop
 * line of sight. This tests if the current row versus all above is valid for
 * calculating a new solution to the Eight Queens Puzzle.
 */
bool QueensCalc::TestAbove(const int aboveRow)
{
    bool ret = true;
    int idx = -1;

    idx = ChessMatrixIndex(_chessboard, aboveRow);
    for (int k = aboveRow - 1; k >= 0; --k)
    {
        int chkidx = ChessMatrixIndex(_chessboard, k);
        if (chkidx < 0 || idx < 0)
            ret = false;
        else if (chkidx == idx)
            ret = false;
        else if (abs(chkidx - idx) == abs(aboveRow - k))
            ret = false;
    }

    return ret;
}

With this implementation of the puzzle solver, the solver finds all 92 correct answers. Each row is placed one column at a time; and the solver moves to the next row if the line can be placed by QueensCalc::TestAbove() returning 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.

/*!
 * \brief Find the next column in the current row that is a valid piece
 * placement, at this row of evaluation, for this iteration of solving the
 * Eight Queens Puzzle.
 */
bool QueensCalc::FindNextColumn(const int curRow)
{
    int curCol = ChessMatrixIndex(_chessboard, curRow);
    int j = 0;

    if (curCol < 0)
    {
        std::cerr << "Error in bitset of row " << curRow << std::endl;
    }

    if (curCol >= BOARD_N)
        curCol = -1;

    for (j = curCol + 1; j < BOARD_N; ++j)
    {
        _chessboard[curRow].reset();
        _chessboard[curRow].set((size_t)j);

        if (TestAbove(curRow))
            return true;
    }

    _chessboard[curRow].reset();
    _chessboard[curRow].set((size_t)j);

    return false;
}

QueensCalc::FindNextColumn() is called by a public method, QueensCalc::FindNextBoard(). When FindNextColumn returns true, the row index is advanced and the call repeated. When FindNext Column returns false, the row index is decremented and the call repeated.

Eight Queens Solver Graphical implementation

The Eight Queens graphical representation was implemented by instantiating a custom wxPanel with an OnPaint() event handler that paints a PNG board image and a PNG queen icon.

/*!
 * \brief Constructor for a custom wxPanel that paints a chess board and 8
 * queen pieces. The queen pieces are arranged according to the internal
 * t_chessmatrix type chess board values.
 */
QueensDrawPanel::QueensDrawPanel(wxWindow* parent) : wxPanel(
    parent,
    wxID_ANY, wxDefaultPosition, wxSize(800, 540),
    wxSUNKEN_BORDER, "Queens Solution")
{
    Bind(wxEVT_PAINT, &QueensDrawPanel::OnPaint, this);

    int j = 0;
    for (int i = 0; i < BOARD_N; ++i)
    {
        for (int j = 0; j < BOARD_N; ++j)
            _chessboard[i][j] = false;
        _chessboard[i][j] = true;
    }

    wxImage::AddHandler(new wxPNGHandler);
    
    // Determine the path to the resource files based upon platform/OS.
#ifdef __WXMSW__
    _resourcesPath = std::string(".");
#endif

#ifdef __WXGTK__
    _resourcesPath = std::string(".");
#endif

#ifdef __WXOSX__
    wxStandardPaths stdPaths = wxStandardPaths::Get();
    wxString resourcePath = stdPaths.GetResourcesDir();

    _resourcesPath = resourcePath.ToStdString();
#endif
}

QueensDrawPanel::~QueensDrawPanel()
{
}

/*!
 * \brief An event handler to redraw the chess board on refresh
 * of the custom wxPanel.
 */
void QueensDrawPanel::OnPaint(wxPaintEvent& event)
{
    // Attached a Paint Device Context to the panel.
    wxPaintDC dc(this);
    // Set the background White
    wxBrush brush("white");
    dc.SetBackground(brush);
    dc.Clear();

    // Width of the queen icon PNG
    int squareWidth = 60;
    // Width and height of the board PNG
    int boardWidth = 482;
    int boardHeight = 481;
    // Calculate the top left position of the board PNG,
    // centered on the panel which is 800, 540
    int boardTop = (540 - boardHeight) / 2;
    int boardLeft = (800 - boardWidth) / 2;

    // Create a string of the path to the board PNG
    std::string boardPngPath = _resourcesPath;
    boardPngPath += "/";
    boardPngPath += "board.png";

    // Create a string of the path to the queen PNG
    std::string queenPngPath = _resourcesPath;
    queenPngPath += "/";
    queenPngPath += "queen.png";

    // Createa bitmap from the board PNG and draw it at the
    // (boardLeft, boardTop) position, which centers it on
    // the panel.
    wxImage boardImg(wxString(boardPngPath), wxBITMAP_TYPE_PNG);
    wxBitmap boardBtm(boardImg);
    dc.DrawBitmap(boardBtm, wxPoint(boardLeft, boardTop), true);

    // For each row and column, conditionally draw a queen piece
    // centered on a board square. The condition is the state
    // of the t_chessmatrix type matrix.
    for (int iRow = 0; iRow < _chessboard.size(); ++iRow)
        for (int iCol = 0; iCol < _chessboard[0].size(); ++iCol)
    	    if (_chessboard[iRow][iCol])
            {
                wxImage queenImg(wxString(queenPngPath), wxBITMAP_TYPE_PNG);
                wxBitmap queenBtm(queenImg);
                int queenLeft = boardLeft + iCol * squareWidth + 5;
                int queenTop = boardTop + iRow * squareWidth + 5;
                dc.DrawBitmap(queenBtm, wxPoint(queenLeft, queenTop), true);
            }
}

/*!
 * \brief Copy a new matrix value for the chess board to display on the
 * wxPanel.
 */
void QueensDrawPanel::UpdateBoard(const t_chessmatrix& board)
{
    for (int i = 0; i < BOARD_N; ++i)
        for (int j = 0; j < BOARD_NP1; ++j)
            _chessboard[i][j] = board[i][j];
}