{"id":2575,"date":"2017-05-04T19:05:29","date_gmt":"2017-05-04T23:05:29","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=2575"},"modified":"2019-11-01T17:10:05","modified_gmt":"2019-11-01T21:10:05","slug":"the-eight-queens-problem-generating-all-solutions","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2017\/05\/04\/the-eight-queens-problem-generating-all-solutions\/","title":{"rendered":"The Eight Queens Problem – Generating All Solutions"},"content":{"rendered":"

On April 20<\/a>, I wrote about an algorithm for solving the Eight Queens Problem<\/a>. In this problem, the task is to place eight queens on a chessboard so that none of the queens is attacking any other queen. Here is one solution.<\/p>

\"\" <\/p>

After I published that post, I became curious to see what others might have submitted about this problem on the File Exchange. A little searching brought me to this submission<\/a> by uu tii. When I looked at the submission, I was surprised to how little code it contained. This is it:<\/p>

function M = eightqueens()\r\nN=8;\r\nT=N-2;\r\nrows=1:N;\r\ncols=perms(rows);\r\nS=size(cols,1);\r\nM=zeros(N,N,S);\r\nlinearInd = sub2ind(size(M), repmat(rows',1,S), cols', repmat(1:S,N,1));\r\nM(linearInd) = 1;\r\ndv=arrayfun(@(k)max([arrayfun(@(x)sum(diag(M(:,:,k),x)),-T:T),arrayfun(@(x)sum(diag(rot90(M(:,:,k)),x)),-T:T)]),1:S);\r\nM(:,:,dv>1)=[];<\/pre>
When I ran it, it returned an 8x8x92 array. The size caught my eye because there are exactly 92 solutions to the Eight Queens Problem (including rotations and flips).<\/p>
M = eightqueens;\r\nwhos M<\/span>\r\n<\/pre>
  Name      Size              Bytes  Class     Attributes\r\n\r\n  M         8x8x92            47104  double              \r\n\r\n<\/pre>
Let's peek at one of the planes of M<\/tt>.<\/p>
M(:,:,45)\r\n<\/pre>
\r\nans =\r\n\r\n     0     0     0     0     1     0     0     0\r\n     1     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     1\r\n     0     0     0     1     0     0     0     0\r\n     0     1     0     0     0     0     0     0\r\n     0     0     0     0     0     0     1     0\r\n     0     0     1     0     0     0     0     0\r\n     0     0     0     0     0     1     0     0\r\n\r\n<\/pre>
Indeed, that is a solution. So, what's going on in this small chunk of code? Well, as I see it, this code has three conceptual chunks. The first chunk, consisting of eight lines, is the longest. Let's run it.<\/p>
N=8;\r\nT=N-2;\r\nrows=1:N;\r\ncols=perms(rows);\r\nS=size(cols,1);\r\nM=zeros(N,N,S);\r\nlinearInd = sub2ind(size(M), repmat(rows',1,S), cols', repmat(1:S,N,1));\r\nM(linearInd) = 1;\r\n\r\nwhos M<\/span>\r\n<\/pre>
  Name      Size                    Bytes  Class     Attributes\r\n\r\n  M         8x8x40320            20643840  double              \r\n\r\n<\/pre>
This seems to be a collection of 40320 boards. There aren't that many solutions, so the collection must contain many boards that aren't valid solutions. For example:<\/p>
M(:,:,45)\r\n<\/pre>
\r\nans =\r\n\r\n     0     0     0     0     0     0     0     1\r\n     0     0     0     0     0     0     1     0\r\n     0     0     0     0     0     1     0     0\r\n     0     0     0     1     0     0     0     0\r\n     1     0     0     0     0     0     0     0\r\n     0     0     1     0     0     0     0     0\r\n     0     0     0     0     1     0     0     0\r\n     0     1     0     0     0     0     0     0\r\n\r\n<\/pre>
There are four queens lined up on the main antidiagonal, so this board is not a solution.<\/p>
This set of boards has been constructed by making the observation that any solution must have exactly one queen on each row and exactly one queen on each column. The array M<\/tt> contains every board that has this property. All the computational magic here is in the line cols=perms(rows)<\/tt>. The rest of this chunk is some indexing computations to initialize and fill in the array M<\/tt> with queens at the locations given by rows<\/tt> and cols<\/tt>.<\/p>
The second chunk is this line:<\/p>
dv=arrayfun(@(k)max([arrayfun(@(x)sum(diag(M(:,:,k),x)),-T:T),arrayfun(@(x)sum(diag(rot90(M(:,:,k)),x)),-T:T)]),1:S);\r\n<\/pre>
Wow, there's a lot going on there. I would summarize it this way: For every board k<\/tt> in M, sum every diagonal and every antidiagonal and take the maximum of those sums. The idea is that M<\/tt> was constructed so that every board has exactly one queen on each row and exactly one queen on each column, so you really only have to check the diagonals of a board to determine whether it is a solution. Let's look at dv<\/tt> for the 45th board, which I displayed above.<\/p>
dv(45)\r\n<\/pre>
\r\nans =\r\n\r\n     4\r\n\r\n<\/pre>
Remember my comment above that board 45 has 4 queens lined up on the main antidiagonal? That's why dv(45)<\/tt> is 4.<\/p>
The last conceptual chunk is eliminate all the boards in the M<\/tt> that are not solutions. We do that by eliminating all boards for which dv > 1<\/tt>.<\/p>
M(:,:,dv>1)=[];\r\n\r\nwhos M<\/span>\r\n<\/pre>
  Name      Size              Bytes  Class     Attributes\r\n\r\n  M         8x8x92            47104  double              \r\n\r\n<\/pre>
And there it is. That's a very clever use of perms<\/tt> and indexing and arrayfun<\/tt> to generate all possible solutions. Thanks, uu tii.<\/p>