The Eight-Queen Puzzle in Programming in Lua Fourth Edition

Question

I'm currently reading Programming in Lua Fourth Edition and I'm already stuck on the first exercise of "Chapter 2. Interlude: The Eight-Queen Puzzle."

The example code is as follows:

N = 8 -- board size

-- check whether position (n, c) is free from attacks
function isplaceok (a, n ,c)
    for i = 1, n - 1 do -- for each queen already placed
        if (a[i] == c) or           -- same column?
        (a[i] - i == c - n) or      -- same diagonal?
        (a[i] + i == c + n) then    -- same diagonal?
            return false -- place can be attacked
        end
    end
    return true -- no attacks; place is OK
end

-- print a board
function printsolution (a)
    for i = 1, N do                 -- for each row
        for j = 1, N do             -- and for each column
            -- write "X" or "-" plus a space
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

-- add to board 'a' all queens from 'n' to 'N'
function addqueen (a, n)
    if n > N then -- all queens have been placed?
        printsolution(a)
    else -- try to place n-th queen
        for c = 1, N do
            if isplaceok(a, n, c) then
                a[n] = c -- place n-th queen at column 'c'
                addqueen(a, n + 1)
            end
        end
    end
end

-- run the program
addqueen({}, 1)

The code's quite commented and the book's quite explicit, but I can't answer the first question:

Exercise 2.1: Modify the eight-queen program so that it stops after printing the first solution.

At the end of this program, a contains all possible solutions; I can't figure out if addqueen (n, c) should be modified so that a contains only one possible solution or if printsolution (a) should be modified so that it only prints the first possible solution?

Even though I'm not sure to fully understand backtracking, I tried to implement both hypotheses without success, so any help would be much appreciated.

Answer 1

At the end of this program, a contains all possible solutions

As far as I understand the solution, a never contains all possible solutions; it either includes one complete solution or one incomplete/incorrect one that the algorithm is working on. The algorithm is written in a way that simply enumerates possible solutions skipping those that generate conflicts as early as possible (for example, if first and second queens are on the same line, then the second queen will be moved without checking positions for other queens, as they wouldn't satisfy the solution anyway).

So, to stop after printing the first solution, you can simply add os.exit() after printsolution(a) line.