You have a standard chess board, and as many queens as you need. What is the most queens that you can put on the board so that no two queens can attack each other? What is the formation to put them in?

Keep in mind that a chess board has 64 squares (8x8), and queens can go diagonal, up and down, and left and right.

(In reply to solution by Charlie)

As for the programming exercise, this is what I used. The first part finds all 92 (as it turns out) solutions. Phase 2 then reads the file produced in part 1 and copies to a second file only those that are not trivial rotations/reflections of one that had come before.

DECLARE SUB placeQueen (col!)
DIM SHARED board(8, 8), ct

OPEN "8queens.txt" FOR OUTPUT AS #1
placeQueen 1
PRINT ct
CLOSE

phase2:

OPEN "8queens.txt" FOR BINARY AS #1
OPEN "8queensc.txt" FOR OUTPUT AS #2
row$ = SPACE$(16)
FOR soln = 1 TO ct
  stPos = (soln - 1) * 18 * 9 + 1
  FOR row = 1 TO 8
    GET #1, stPos + (row - 1) * 18, row$
    FOR col = 1 TO 8
      IF MID$(row$, col * 2 - 1, 1) = "*" THEN
        board(row, col) = 1
      ELSE
        board(row, col) = 0
      END IF
    NEXT
  NEXT
  good = 1
  FOR solRef = 1 TO soln - 1
    stPos = (solRef - 1) * 18 * 9 + 1
    FOR row = 1 TO 8
      GET #1, stPos + (row - 1) * 18, row$
      FOR col = 1 TO 8
        IF MID$(row$, col * 2 - 1, 1) = "*" THEN
          board2(row, col) = 1
        ELSE
          board2(row, col) = 0
        END IF
      NEXT
    NEXT
    FOR rotRef = 1 TO 7
      bad = 1
      FOR r = 1 TO 8
        FOR c = 1 TO 8
          SELECT CASE rotRef
            CASE 1
              r2 = 9 - r
              c2 = c
            CASE 2
              r2 = 9 - r
              c2 = 9 - c
            CASE 3
              r2 = r
              c2 = 9 - c
            CASE 4
              r2 = 9 - c
              c2 = r
            CASE 5
              r2 = 9 - c
              c2 = 9 - r
            CASE 6
              r2 = c
              c2 = 9 - r
            CASE 7
              r2 = c
              c2 = r
          END SELECT
          IF board(r, c) <> board2(r2, c2) THEN bad = 0: EXIT FOR
        NEXT
        IF bad = 0 THEN EXIT FOR
      NEXT
      IF bad THEN good = 0: EXIT FOR
    NEXT
    IF good = 0 THEN EXIT FOR
  NEXT
  IF good THEN
    stPos = (soln - 1) * 18 * 9 + 1
    FOR row = 1 TO 9
      GET #1, stPos + (row - 1) * 18, row$
      PRINT #2, row$
    NEXT
    ct2 = ct2 + 1
  END IF
NEXT
PRINT ct2

SUB placeQueen (col)
  FOR row = 1 TO 8
    good = 1
    FOR c = 1 TO col - 1
      IF board(row, c) THEN good = 0: EXIT FOR
      r = row - (col - c)
      IF r > 0 THEN
        IF board(r, c) THEN good = 0: EXIT FOR
      END IF
      r = row + (col - c)
      IF r < 9 THEN
        IF board(r, c) THEN good = 0: EXIT FOR
      END IF
    NEXT
    IF good THEN
      board(row, col) = 1
      IF col = 8 THEN
        ct = ct + 1
        FOR r = 1 TO 8
         FOR c = 1 TO 8
          IF board(r, c) THEN
           PRINT #1, "* ";
          ELSE
           PRINT #1, ". ";
          END IF
         NEXT
         PRINT #1,
        NEXT
        PRINT #1, "--------------- "
      ELSE
        placeQueen col + 1
      END IF
      board(row, col) = 0
    END IF
  NEXT
END SUB

Posted by Charlie on 2003-06-03 08:30:47