

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


 
NQUEENS: PROC OPTIONS (MAIN);                                  
 DCL A(35) BIN FIXED(31) EXTERNAL;                             
 DCL COUNT BIN FIXED(31) EXTERNAL;                             
 COUNT = 0;                                                    
 DECLARE SYSIN FILE;                                           
 DCL ABS BUILTIN;                                              
 DECLARE SYSPRINT FILE;                                        
 DECLARE N BINARY FIXED (31); /* COUNTER */                    
 /* MAIN LOOP STARTS HERE */                                   
 GET LIST (N) FILE(SYSIN); /* N QUEENS, N X N BOARD */        
 PUT SKIP (1) FILE(SYSPRINT);                                  
 PUT SKIP LIST('BEGIN N QUEENS PROCESSING *****') FILE(SYSPRINT);    
 PUT SKIP LIST('SOLUTIONS FOR N: ',N) FILE(SYSPRINT);          
 PUT SKIP (1) FILE(SYSPRINT);                                  
  IF N < 4 THEN DO;                                            
    /* LESS THAN 4 MAKES NO SENSE  */                          
      PUT SKIP (2) FILE(SYSPRINT);                             
      PUT SKIP LIST (N,' N TOO LOW') FILE (SYSPRINT);               
      PUT SKIP (2) FILE(SYSPRINT);                             
      RETURN (1);                                              
   END;                                                        
   IF N > 35 THEN DO;                                                
     /* WOULD TAKE WEEKS    */                               
       PUT SKIP (2) FILE(SYSPRINT);                                  
       PUT SKIP LIST (N,' N TOO HIGH') FILE (SYSPRINT);                   
       PUT SKIP (2) FILE(SYSPRINT);                                  
       RETURN (1);                                                   
    END;                                                             
 
    CALL QUEEN(N);                                                   
 
     PUT SKIP (2) FILE(SYSPRINT);                                    
     PUT SKIP LIST (COUNT,' SOLUTIONS FOUND') FILE(SYSPRINT);             
     PUT SKIP (1) FILE(SYSPRINT);                                    
     PUT SKIP LIST ('END OF PROCESSING ****') FILE(SYSPRINT);             
     RETURN(0);                                                      
  /* MAIN LOOP ENDS ABOVE  */                                        
 
  PLACE: PROCEDURE (PS);                                             
     DCL PS BIN FIXED(31);                                           
     DCL I  BIN FIXED(31) INIT(0);                                  
     DCL A(50) BIN FIXED(31) EXTERNAL;                               
 
  DO I=1 TO PS-1;                                                    
       IF A(I) = A(PS) THEN  RETURN(0);                              
       IF ABS ( A(I) - A(PS) ) = (PS-I) THEN RETURN(0);              
  END;                                                               
    RETURN (1);                                                      
  END PLACE;                                                         
 
  QUEEN: PROCEDURE (N);                                          
      DCL N BIN FIXED (31);                                      
      DCL K BIN FIXED (31);                                      
      DCL A(50) BIN FIXED(31) EXTERNAL;                          
      DCL COUNT BIN FIXED(31) EXTERNAL;                          
      K = 1;                                                     
      A(K) = 0;                                                  
      DO WHILE (K > 0);                                          
         A(K) = A(K) + 1;                                        
         DO WHILE ( ( A(K)<= N) & (PLACE(K) =0) );               
             A(K) = A(K) +1;                                     
         END;                                     
         IF (A(K) <= N) THEN DO;                                 
           IF (K = N ) THEN DO;                                  
                         COUNT = COUNT + 1;                      
                 END;                                            
           ELSE DO;                                              
             K= K +1;                                            
             A(K) = 0;                                           
           END; /* OF INSIDE ELSE */                              
         END; /* OF FIRST IF */                                  
         ELSE DO;                                                
              K = K -1;                                          
         END;                                                    
      END;  /* OF EXTERNAL WHILE LOOP  */                                         
   END QUEEN;                                                    
 
 END NQUEENS;  