Solving the Eight Queens Chess Problem with a Lambda

[Patrick2788]

Background

"The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques."

https://en.wikipedia.org/wiki/Eight_queens_puzzle

The Initial Goal for this Task

My initial goal for this task was to write a formula capable of pulling all 92 solutions for this puzzle when n=8. The problems with this were with the limitations of the two methods that could be employed:

1) Generate all possible permutations for 1 to n

2) A Recursive technique often used in coding languages called 'Backtracking'.

I tried using Octals (0 to 7) with method 1 to make the task of generating permutations a bit easier but any approach seemed to be a Herculean task of not only generating the permutations, but then picking out the ones that actually solved the puzzle! Method 2 has even more limitations with the number of calls allowed in a given function. I had a recursive function developed that accepted a number (1 to n) and it would solve the puzzle using that number as the first pick in the array. The problem was the logic didn't always make the correct picks beyond pick 3 - close but no cigar.

The New Approach
Instead of generating 92 solutions, I set my sight on creating a function to solve the puzzle when n=4 all the way up to n=20. My research found there are 3 possible scenarios depending on the remainder from n/6.

My function follows below. Interested in any and all different approaches to this puzzle.

=LAMBDA(n,LET(
    matrix, CHOOSECOLS(MUNIT(n), SEQUENCE(, n, n, -1)),
    odds, SEQUENCE(ROUND(n / 2, 0), , 1, 2),
    evens, odds + 1,
    odds_a, VSTACK({3; 1}, DROP(odds, 3), 5),
    evens_b, VSTACK(DROP(evens, 1), 2),
    odds_b, VSTACK(DROP(odds, 2), {1; 3}),
    case_a, VSTACK(evens, odds_a),
    case_b, VSTACK(evens_b, odds_b),
    case_c, VSTACK(evens, odds),
    scenario, SWITCH(MOD(n, 6), 2, case_a, 3, case_b, case_c),
    CHOOSECOLS(matrix, scenario)
))

[#2]

@Patrick2788 

Great case!

[#3 · Accepted solution]

@Patrick2788 I think i dun it ...  see attached

EDIT: I updated the function to take advantage of the fact that the 2nd 1/2 of the solutions are symmetric to the first 1/2 (I didn't optimize for the 1/2 of the middle value when n is odd) but now instead of crashing at n=12 it finds all the solutions for n=12 (14,200).  i also updated the sheet format to make entry and viewing a little easier.

EDIT2: I fixed the above version and added better format and added the checkerboard output with a pulldown selector to pick which solution to show on the board:

BTW: I just tried 13 and it found 73,712 solutions and 14 found 365,596 solutions.  Can you please verify them for me?

[#4]

At first glance it looks good. I had a list of all 92 solutions but cannot locate it at the moment to check against your results. I recall one thing all 92 solutions had in common was a standard deviation of 2.44949 (rounded) (Although, there are some combinations that are not solutions that have the same STDEV). Your solutions have that same STDEV. I'll try to find that list. I had moved on from this project and don't want to check these 1-by-1!

[#5]

@mtarler 

I've obtained a list of all 92 solutions and checked them against your formula where n=8.  The result was 92/92! (I've attached a simple workbook which lists all 92).

With your solution and the use of recursion it looks like you've found a way to do some backtracking.  I'd be interested in reading your approach to this problem.

[#6]

@Patrick2788  So by "I'd be interested in reading your approach to this problem." I'm guessing an explanation of the Lambda function.  So here is the Lambda:

queens(n,[Solutions]) = LET(CRows, SEQUENCE(, n),
    IF(ISOMITTED(Solutions),
       LET(firsthalf, IFERROR(REDUCE(0, SEQUENCE(, INT((n + 1) / 2)), LAMBDA(p, q, VSTACK(p, queens(n, q)))),0),
            tophalf, FILTER(firsthalf, INDEX(firsthalf, , 1) > 0, 0),
            SORT(VSTACK(tophalf, n + 1 - FILTER(tophalf, INDEX(tophalf, , 1) <= n / 2, 0)))
        ),
        LET(ThisSol, EXPAND(TAKE(Solutions, -1), , n, 0),
            ThisC, n + 1 - SUM(--(ThisSol = 0)),
            ThisC_used, TOROW(VSTACK(ThisSol, ThisSol + ThisC - CRows, ThisSol - ThisC + CRows) * (ThisSol > 0)),
            ThisC_open, IFERROR(UNIQUE(HSTACK(IF((ThisC_used <= 0) + (ThisC_used > n), 0, ThisC_used), CRows),1,1),0),
            out, IF(INDEX(ThisC_open, 1) > 0,
                    IFERROR(DROP(REDUCE(0,ThisC_open,LAMBDA(p, q,
                        LET(addSol, IF(ThisC = n,
                                        HSTACK(TAKE(ThisSol, 1, ThisC - 1), q),
                                        queens(n,IF(ThisC > 1, HSTACK(TAKE(ThisSol, 1, ThisC - 1), q), q))
                                    ),
                           IF(INDEX(addSol, 1, 1) > 0, VSTACK(p, addSol), p)
                           )
                    )),1),0),
                0),
            out)
    ))

so the basic idea is that given a beginning sequence of a solution for a NxN grid this function will find the rest.  There are also some things I could probably take out as they are relics of different avenues I tried going down.

So lines 2-6 are for the case you don't pass any prior solution and it just passes locations 1, 2, ... but because of symmetry it only goes to the halfway line (e.g. for 8 it does 1-4 and 9 it does 1-5) and then it flips all those solutions and stacks them to themselves to get the full set

Line 7 (ThisSol) takes the last row of the 'Solutions' (a relic from prior approach) but then expands it to have 0s for the rest of the N values needed

Line 8 (ThisC) finds what column we are solving for (again a relic as current use could just use COLUMNS(Solutions) but hey if it ain't broke ...)

Line 9 (ThisC_used) basically stacks the locations that each prior solution will 'attack' this column (horizontal, diagonal up, diagonal down)

Line 10 (ThisC_open) says any 'used' location <1 or >N =>0 and then combines SEQUENCE(N) and takes the UNIQUE so you find the possible solutions for that column (or returns 0)

Lines 11-20 then cycles through those possible solutions and calls itself recursively to find all the subsequent columns (note lines 13-14 check for it being column N and to 'end' the recursion)

[#7]

Thanks again for sharing. Impressive work!