{"id":2558,"date":"2017-04-20T14:36:14","date_gmt":"2017-04-20T18:36:14","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=2558"},"modified":"2019-11-01T17:08:44","modified_gmt":"2019-11-01T21:08:44","slug":"the-eight-queens-problem","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2017\/04\/20\/the-eight-queens-problem\/","title":{"rendered":"The Eight Queens Problem"},"content":{"rendered":"

Today I want to tackle a classic algorithm puzzle known as the Eight Queens Problem<\/i><\/a>. In this problem, your task is to arrange eight queens on a chessboard so that none of the queens is attacking any of the others. Here is one solution.<\/p>

\"\" <\/p>

The problem is often restated as the N Queens Problem<\/i>, which is placing N queens on an N-by-N board.<\/p>

This is more of a general algorithm topic than an image processing topic, although some of the concepts and MATLAB techniques that I show might be useful to people doing image processing work. For some reason, this problem has been on my mind recently, so I decided to play with it a bit in MATLAB. I ended up with both a working algorithm and an interesting visualization. Here is the result for a 6x6 chessboard.<\/p>

\"\" <\/p>

Solving the eight queens problem was the first \"real\" and nontrivial program that I can recall writing. I wrote it in Basic for a math class project sometime around 1981. My school didn't actually have a computer at that point; I used a teletype terminal (no monitor!) and a dial-up modem to communicate with the county school system's mainframe, which was located some miles away. As I recall, the program used a pure brute-force solution, generating boards randomly and testing each one to see if it was a valid solution. I knew almost nothing about algorithms then.<\/p>

When I revisited the problem this week, I used a recursive divide-and-conquer technique with backtracking<\/i>. I'll explain that in two parts, starting with the recursive divide-and-conquer<\/i> part. The most famous algorithm in signal processing, the fast Fourier transform (FFT) is based on this idea. The discrete Fourier transform of an $N$-point sequence can be written in terms of the discrete Fourier transforms of two different subsets of the original sequence.<\/p>

Here is one way to use divide-and-conquer on the N queens problem. We'll write a routine that places N queens on an N-column board in two steps:<\/p>

A. Place one queen on a safe square somewhere on the first column of the board.<\/p>

B. Call the routine recursively to place N-1 queens on an (N-1)-column board.<\/p>

The backtracking<\/i> part is necessary because, unlike when computing the FFT, one of the substeps A or B might fail.<\/p>

If step B fails, then we backtrack<\/i>. That is, we undo step A, find a different safe square on the first column of the board, and then do the recursive step B call again. At any time, if there are no remaining safe squares on the first column to try, then the solution attempt has failed and the routine returns.<\/p>

Here's some MATLAB code to implement this idea.<\/p>

function [board,succeeded] = placeQueens(board,col)<\/pre>
N = size(board,1);\r\nif col > N\r\n    % There are no columns left. All the queens\r\n    % have been placed. Return with success.\r\n    succeeded = true;\r\n    return\r\nend<\/pre>
safe = false(1,N);\r\nfor row = 1:N\r\n    safe(row) = isSafe(board,row,col);\r\nend<\/pre>
if ~any(safe)\r\n    % There are no safe squares on this column.\r\n    % Return with failure.\r\n    succeeded = false;\r\n    return\r\nend<\/pre>
for row = 1:N\r\n    if safe(row)\r\n        board(row,col) = 1;\r\n        [board,succeeded] = placeQueens(board,col+1);\r\n        if succeeded\r\n            return\r\n        else\r\n            % Backtrack. Undo the placement of the queen\r\n            % on this column and keep looking.\r\n            board(row,col) = 0;\r\n        end\r\n    end\r\nend<\/pre>
% If we get here, we have checked every row on this column\r\n% without succeeding. Return with failure.\r\nsucceeded = false;<\/pre>
While I was generating the animations for boards of different sizes, two things caught my eye. First, there's no solution for a 6x6 board that has a queen in any corner. Look at the animated solution above and see if you can convince yourself about that.<\/p>
Second, I noticed that a solution for the 5x5 board can be found without any backtracking. Check out the animation:<\/p>
\"\" <\/p>
Next time, I'll write about the graphics programming and GIF and video file writing I did to do the algorithm visualization.<\/p>