Solution to exercise 2.2 does not actually compute permutations

[jxlin123]

Hi, I noticed that the current solution given for exercise 2.2 (change the 8-queens code to instead generate all permutations of the set {1, ...8} ) does not actually generate permutations; it instead generates "permutations with repetition" (where numbers can be repeated).

The current code of the addqueen function is as follows:

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

Notice how the innermost for loop (for i = 1, n - 1 do ...) ends up being an expensive no-op, since the loop doesn't affect the remaining logic of the function.

If I understand correctly, the purpose of that inner loop is to prevent the function from assigning a queen to a column that's already "taken" by a previous queen (from an earlier row). For instance, if table a is currently {1, 2}, we do not want to assign either 1 or 2 to a[3], since in a permutations, elements can't be repeated.

Thus, if we determine (in the inner loop) that a[i] == c, I believe we should skip the remaining logic in the outer loop (i.e., the a[n] = c and addqueen (a, n + 1) lines), and move on to the next iteration of the outer loop.

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

      ::con::
    end
  end
end

My modified code (using my version of addqueen) ends up calling isplaceok 140756 times, which is still worse than the backtracking approach in the original Figure 2.1, but at least is better than the 50889536 invocations in the "permutations with repetition" code.