How much memory may a HPPL program use on a G2?

[Stefan Falk]

Hello everybody,

Sorry for the delay, but here is my N-Queens program:

Code:

LOCAL
 POSI,SOLCNT,UNICNT,
 COLS,DU,DD,ALLSOLS,UNISOLS;
LOCAL LASTP;

EXPORT QUEENS(DIMENSION)
BEGIN
 LOCAL N,START;
 START:=TICKS;
 N:=DIMENSION;
 //PRINT(N+" Queens");
 SOLCNT:=0;
 UNICNT:=0;
 POSI:=MAKELIST(0,X,1,N,1);
 COLS:=MAKELIST(0,X,1,N,1);
 DU:=MAKELIST(0,X,1,2*N-1,1);
 DD:=MAKELIST(0,X,1,2*N-1,1);
 ALLSOLS:={};
 UNISOLS:={};
 TRY(N,1);
 SOLCNT:=SOLCNT*2;
 //PRINT(SOLCNT+" solutions, "+UNICNT+" unique");
 //PRINT((TICKS-START)/1000+" seconds")
 TEXTOUT_P("FIN",0,40);
 WAIT(0)
END;

LOCAL TRY(N,ROW)
BEGIN
 LOCAL M,COL,DUI,DDI,DUP,DUP2,I;
 IF ROW>2 THEN
  M:=N
 ELSE
  IF ROW=1 THEN
   M:=IP((N+1)/2)
  ELSE
   IF N MOD 2=1 AND POSI(1)=(N+1)/2 THEN
    M:=IP(N/2)
   ELSE
    M:=N
   END
  END
 END;
 FOR COL FROM 1 TO M DO
  DUI:=ROW-COL+N;
  DDI:=ROW+COL-1;
  IF COLS(COL)=0 AND DU(DUI)=0 AND DD(DDI)=0 THEN
   POSI(ROW):=COL;
   IF ROW=N THEN
    SOLCNT:=SOLCNT+1;
    IF POS(ALLSOLS,POSI)=0 THEN
     ALLSOLS:=CONCAT(ALLSOLS,{POSI});
     DUP:=POSI;
     DUP2:=MIRR(N,DUP);
     ALLSOLS:=CONCAT(ALLSOLS,{DUP2});
     FOR I FROM 1 TO 3 DO
      DUP:=TURN(N,DUP);
      ALLSOLS:=CONCAT(ALLSOLS,{DUP});
      DUP2:=MIRR(N,DUP);
      ALLSOLS:=CONCAT(ALLSOLS,{DUP2}); 
     END;
     UNISOLS:=CONCAT(UNISOLS,{POSI});
     UNICNT:=UNICNT+1;
     SHOW(N,POSI)
    END
   ELSE
    COLS(COL):=1; DU(DUI):=1; DD(DDI):=1;
    TRY(N,ROW+1);
    COLS(COL):=0; DU(DUI):=0; DD(DDI):=0
   END
  END
 END
END;

LOCAL MIRR(N,P)
BEGIN
 LOCAL R,M;
 M:=P;
 FOR R FROM 1 TO N DO
  M(R):=N+1-P(R)
 END;
 RETURN M; 
END;

LOCAL TURN(N,P)
BEGIN
 LOCAL R,T;
 T:=P;
 FOR R FROM 1 TO N DO
  T(P(R)):=N+1-R
 END;
 RETURN T;
END;

LOCAL SHOW(N,P)
BEGIN
 LOCAL D,I,T,E,OX,OY,M;
 LOCAL GRAY,WHITE,BLACK,CLR;
 D:=IP(237/N);
 OY:=IP((239-N*D)/2);
 OX:=319-N*D-OY;
 GRAY:=RGB(224,224,224);
 WHITE:=RGB(255,255,255);
 BLACK:=RGB(0,0,0);
 M:=IP(D/6);
 IF UNICNT=1 THEN
  RECT();
  E:=N*D;
  FOR I FROM 0 TO N DO
   T:=I*D; 
   LINE_P(OX,T+OY,E+OX,T+OY);
   LINE_P(T+OX,OY,T+OX,E+OY)
  END;
  FOR I FROM 1 TO N DO
   FOR E FROM 1 TO N DO
    IF (E+I) MOD 2 = 0 THEN
     RECT_P((E-1)*D+1+OX,(N-I)*D+1+OY,E*D-1+OX,(N-I+1)*D-1+OY,GRAY)
    END;
    IF P(I)=E THEN
     RECT_P((E-1)*D+M+OX,(N-I)*D+M+OY,E*D-M+OX,(N-I+1)*D-M+OY,WHITE,BLACK)
    END
   END
  END
 ELSE
  FOR I FROM 1 TO N DO
   IF P(I)≠LASTP(I) THEN
    RECT_P((LASTP(I)-1)*D+M+OX,(N-I)*D+M+OY,LASTP(I)*D-M+OX,(N-I+1)*D-M+OY,IFTE((LASTP(I)+I) MOD 2=0,GRAY,WHITE));
    RECT_P((P(I)-1)*D+M+OX,(N-I)*D+M+OY,P(I)*D-M+OX,(N-I+1)*D-M+OY,WHITE,BLACK)
   END 
  END
 END;
 LASTP:=P;
 TEXTOUT_P(UNICNT,0,0,3,BLACK,100,WHITE);
 TEXTOUT_P(SOLCNT,0,20,3,BLACK,100,WHITE)
END;

Or should I post that elsewhere?

The program runs, on my HP Prime G2 with current firmware, fine for up to 11x11 queens, but fails with out of memory for 12x12 and above. For 12x12, there are a few hundred different solutions, and for each 8 variants are stored (original, turned 3 times, and each mirrored). That should be much less than 1000 elements, each a 12-element array of real numbers. I guess that should easily fit in main memory.

Best Regards,
Stefan