Vietnamese snake puzzle - Closed

[Gerson W. Barbosa]

(05-23-2015 09:08 AM)Werner Wrote:  I've written an RPL solution as well that, on EMU48 at full pelt, cranks out all 136 solutions in 30 seconds. But I'm not happy with it yet.
I used Heap's algorithm to generate all permutations - then it took 256 seconds.
Including the condition that

Code:

MOD(13*b*i + g*h*c,c*i)=0

after having selected 5 numbers reduced the timing to 30 seconds.

I've decided to change my RPL program to handle c for other values than 1, since it was just a matter of including another loop and do the necessary modifications. Perhaps the most difficult one would be determining the new the MOD condition, but I shamelessly used yours above (Thanks! :-). I've obtained 34 solutions (136/4) as expected, in 49.47 seconds on the emulator (Debug4x, Emu-50g, WinXP, Intel Core Duo CPU @ 1.86 GHz) -- 23 minutes and 31.9 seconds on the physical HP 50g. Ok, each solution should be processed to generate three additional ones, but that would take irrelevant time so I won't mind doing it.

Cheers,

Gerson.

Code:


%%HP: T(3)A(D)F(.);
\<< { 1. 2. 3. 4. 5. 6. 7. 8. 9. } { } 1. 9.
  FOR i 1. 9.
    FOR c c i \=/
      IF
      THEN 1. 9.
        FOR b b c \=/ b i \=/ AND
          IF
          THEN b 13. * c / 87. - 1. 7.
            FOR e e b \=/ e c \=/ AND e i \=/ AND
              IF
              THEN e 12. * OVER + 4. PICK 1.
                \<<
                  IF DUPDUP DUPDUP i == SWAP c == OR SWAP b == OR SWAP e == OR
                  THEN DROP
                  END
                \>> DOLIST 1. 4.
                FOR j j 1. + 5.
                  FOR k DUP j GET OVER k GET DUP2 * c * b 13. * i * + i c * MOD
                    IF NOT
                    THEN 0. 0. 0. \-> g h a d f
                      \<< g h * i / PICK3 + OVER 1.
                        \<<
                          IF DUPDUP g == SWAP h == OR
                          THEN DROP
                          END
                        \>> DOLIST 1. 3.
                        START DUPDUP HEAD SWAP TAIL SWAP + SWAP PICK3 SWAP OBJ\-> DROP + NEG + - ABS .000001 <
                          IF
                          THEN DUP2 NIP OBJ\-> DROP 'f' STO 'd' STO 'a' STO a b c d e f g h i 9. \->LIST 1. \->LIST 7. ROLL SWAP + 6. ROLLD
                          END
                        NEXT DROP2
                      \>>
                    ELSE DROP2
                    END
                  NEXT
                NEXT DROP2
              END
            NEXT DROP
          END
        NEXT
      END
    NEXT
  NEXT NIP
\>>

{ { 7. 6. 4. 8. 5. 9. 1. 3. 2. } { 9. 6. 4. 3. 5. 8. 1. 7. 2. } { 1. 9. 6. 4. 5. 8. 3. 7. 2. } { 9. 4. 8. 5. 6. 7. 1. 3. 2. } { 2. 8. 6. 9. 4. 1. 5. 7. 3. } { 2. 6. 9. 8. 5. 1. 4. 7. 3. } { 6. 3. 1. 9. 2. 5. 7. 8. 4. } { 7. 3. 1. 5. 2. 6. 8. 9. 4. } { 7. 3. 2. 8. 5. 9. 1. 6. 4. } { 5. 7. 2. 8. 3. 9. 1. 6. 4. } { 8. 9. 2. 3. 1. 5. 6. 7. 4. } { 5. 9. 3. 6. 2. 1. 7. 8. 4. } { 3. 2. 8. 6. 5. 1. 7. 9. 4. } { 7. 2. 8. 9. 6. 5. 1. 3. 4. } { 3. 2. 1. 5. 4. 7. 8. 9. 6. } { 9. 4. 1. 5. 2. 7. 3. 8. 6. } { 1. 3. 2. 4. 5. 8. 7. 9. 6. } { 7. 5. 2. 8. 4. 9. 1. 3. 6. } { 8. 5. 2. 1. 4. 7. 3. 9. 6. } { 1. 5. 2. 3. 4. 8. 7. 9. 6. } { 9. 5. 3. 1. 4. 2. 7. 8. 6. } { 3. 2. 4. 8. 5. 1. 7. 9. 6. } { 1. 4. 8. 2. 7. 9. 3. 5. 6. } { 1. 3. 9. 4. 7. 8. 2. 5. 6. } { 9. 1. 2. 5. 6. 7. 3. 4. 8. } { 9. 3. 2. 1. 5. 6. 4. 7. 8. } { 7. 1. 4. 9. 6. 5. 2. 3. 8. } { 2. 1. 4. 3. 7. 9. 5. 6. 8. } { 7. 3. 4. 1. 6. 5. 2. 9. 8. } { 1. 3. 6. 2. 7. 9. 4. 5. 8. } { 7. 9. 6. 1. 5. 2. 3. 4. 8. } { 2. 9. 6. 3. 5. 1. 4. 7. 8. } { 7. 8. 3. 1. 4. 5. 2. 6. 9. } { 1. 2. 6. 4. 7. 8. 3. 5. 9. } }

I think this is correct, but I haven't checked it yet.