

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
!------------------------------------------------
! QUEENS.R : solve queens problem on a NxN board
!------------------------------------------------
 
PROGRAM QUEENS
 
DIM COL%[15]
 
BEGIN
  MAXSIZE%=15
  PRINT(TAB(25);" --- PROBLEMA DELLE REGINE --- ")
  PRINT
  PRINT("Board dimension ";)
  INPUT(N%)
  PRINT
  IF (N%<1 OR N%>MAXSIZE%)
    THEN
      PRINT("Illegal dimension!!")
    ELSE
      FOR CURCOLNBR%=1 TO N%
        COL%[CURCOLNBR%]=0
      END FOR
      CURCOLNBR%=1
      WHILE CURCOLNBR%>0 DO
        PLACEDAQUEEN%=FALSE
        I%=COL%[CURCOLNBR%]+1
        WHILE (I%<=N%) AND NOT PLACEDAQUEEN% DO
          PLACEDAQUEEN%=TRUE
          J%=1
          WHILE PLACEDAQUEEN% AND (J%<CURCOLNBR%) DO
            PLACEDAQUEEN%=COL%[J%]<>I%
            J%=J%+1
          END WHILE
          IF PLACEDAQUEEN%
            THEN
              DIAGNBR%=I%+CURCOLNBR%
              J%=1
              WHILE PLACEDAQUEEN% AND (J%<CURCOLNBR%) DO
                PLACEDAQUEEN%=(COL%[J%]+J%)<>DIAGNBR%
                J%=J%+1
              END WHILE
            ELSE
          END IF
          IF PLACEDAQUEEN%
            THEN
              DIAGNBR%=I%-CURCOLNBR%
              J%=1
              WHILE PLACEDAQUEEN% AND (J%<CURCOLNBR%) DO
                 PLACEDAQUEEN%=(COL%[J%]-J%)<>DIAGNBR%
                 J%=J%+1
              END WHILE
            ELSE
          END IF
          IF NOT PLACEDAQUEEN%
            THEN
              I%=I%+1
            ELSE
              COL%[CURCOLNBR%]=I%
          END IF
        END WHILE
        IF NOT PLACEDAQUEEN%
          THEN
            COL%[CURCOLNBR%]=0
            CURCOLNBR%=CURCOLNBR%-1
          ELSE
            IF CURCOLNBR%=N%
              THEN
                NSOL%=NSOL%+1
                PRINT("Soluzione";NSOL%;":";)
                FOR I%=1 TO N%
                  PRINT(COL%[I%];)
                END FOR
                PRINT
              ELSE
                CURCOLNBR%=CURCOLNBR%+1
            END IF
        END IF
      END WHILE
      PRINT("Search completed")
      REPEAT
         GET(CH$)
      UNTIL CH$<>""
    END IF
END PROGRAM
 