2 Interlude: The Eight-Queen Puzzle

In this chapter we make a short interlude to present a simple but complete program in Lua that solves the eight-queen puzzle: its goal is to position eight queens in a chessboard in such a way that no queen can attack another one.

The code here does not use anything specific to Lua; we should be able to translate the code to several other languages with only cosmetic changes. The idea is to present the general flavor of Lua, in particular how the Lua syntax looks like, without going into details. We will cover all missing details in subsequent chapters.

A first step to solving the eight-queen puzzle is to note that any valid solution must have exactly one queen in each row. Therefore, we can represent potential solutions with a simple array of eight numbers, one for each row; each number tells at which column is the queen at that row. For instance, the array {3, 7, 2, 1, 8, 6, 5, 4} means that the queens are in the squares (1,3), (2,7), (3,2), (4,1), (5,8), (6,6), (7,5), and (8,4). (By the way, this is not a valid solution; for instance, the queen in square (3,2) can attack the one in square (4,1).) Note that any valid solution must be a permutation of the integers 1 to 8, as a valid solution also must have exactly one queen in each column.

The complete program is in Figure 2.1, “The eight-queen program”.

Figure 2.1. The eight-queen program

      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 first function is isplaceok, which checks whether a given position on a board is free from attacks from previously placed queens. More specifically, it checks whether putting the n-th queen in column c will conflict with any of the previous n-1 queens already set in the array a. Remember that, by representation, two queens cannot be in the same row, so isplaceok checks whether there are no queens in the same column or in the same diagonals of the new position.

Next we have the function printsolution, which prints a board. It simply traverses the entire board, printing an X at positions with a queen and a - at other positions, without any fancy graphics. (Note its use of the and–or idiom to select the character to print at each position.) Each result will look like this:

      X - - - - - - -
      - - - - X - - -
      - - - - - - - X
      - - - - - X - -
      - - X - - - - -
      - - - - - - X -
      - X - - - - - -
      - - - X - - - -

The last function, addqueen, is the core of the program. It tries to place all queens larger than or equal to n in the board. It uses backtracking to search for valid solutions. First, it checks whether the solution is complete and, if so, prints that solution. Otherwise, it loops through all columns for the n-th queen; for each column that is free from attacks, the program places the queen there and recursively tries to place the following queens.

Finally, the main body simply calls addqueen on an empty solution.

Exercises

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

Exercise 2.2: An alternative implementation for the eight-queen problem would be to generate all possible permutations of 1 to 8 and, for each permutation, to check whether it is valid. Change the program to use this approach. How does the performance of the new program compare with the old one? (Hint: compare the total number of permutations with the number of times that the original program calls the function isplaceok.)