Skip to Content
Author's profile photo Former Member
Former Member
June 5, 2014 2 minute read

N Queens Algorithm – Quick and Dirty

I saw this document today which solves N Queen puzzle.

N Queens Algorithm – ABAP

Here is my attempt to find all possible solutions to N Queen puzzle using least lines of code.

As a result, code does not have proper variable naming and output display part.

Technically the program is capable of running for any value of n>3, but execution times rise exponentially.

For n = 14, there are total 365,596 solutions and my program took 300 seconds to find them.

Output can be seen in debug mode. The internal table has (x,y) coordinates of n Queens.

The program shows count of possible solutions as output and individual solutions can be seen in debug mode in subroutine named valid_solution.

Here is the mockup of first result found for Eight Queens puzzle.

Equivalent program output is:

Full code snippet

  1. TYPES:
  2. BEGIN OF ty,
  3.   x TYPE i,
  4.   y TYPE i,
  5. END OF ty,
  6. tty TYPE TABLE OF ty.
  8. PARAMETERS pv_max TYPE i DEFAULT 8 OBLIGATORY.
  10. DATA: lt TYPE TABLE OF ty,  “n Queen coordinates
  11.       ls TYPE ty,
  12.       lv_count TYPE decfloat34.
  14. DO pv_max TIMES.
  15.   ls–x = sy–index.  “avoids horizontal conflict
  16.   APPEND ls TO lt.
  17. ENDDO.
  19. PERFORM solve USING lt.
  21. WRITE:/ ‘Total solutions: ‘, lv_count.
  23. *———————————————————————-*
  24. FORM solve USING lt TYPE tty.
  25.   FIELD-SYMBOLS <fs> TYPE ty.
  26.   DATA: ls TYPE ty,
  27.         x TYPE i,
  28.         y TYPE i,
  29.         flag TYPE boolean.
  31.   READ TABLE lt ASSIGNING <fs> WITH KEY y = 0.
  32.   IF sy–subrc EQ 0.
  33.     x = <fs>–x.
  34.     DO pv_max TIMES.
  35.       y = sy–index.
  36.       READ TABLE lt TRANSPORTING NO FIELDS WITH KEY y = y.
  37.       CHECK sy–subrc NE 0.  “no vertical conflict
  38.       ” avoid diagonal conflicts having / and \ direction
  39.       flag = abap_true.
  40.       LOOP AT lt INTO ls WHERE x > 0 AND y > 0.
  41.         CHECK ls–x – x  EQ  ls–y – y      OR
  42.               ls–x – x  EQ  y    – ls–y.
  43.         flag = abap_false.
  44.         EXIT.
  45.       ENDLOOP.
  46.       ” fill non-conflicting value and continue recursion
  47.       CHECK flag EQ abap_true.
  48.       <fs>–y = y.
  49.       ”  n values filled == solution
  50.       IF x EQ pv_max.
  51.         PERFORM valid_solution USING lt.
  52.       ELSE.
  53.         PERFORM solve USING lt.
  54.       ENDIF.
  55.     ENDDO.
  56.     CLEAR <fs>–y.
  57.   ENDIF.
  58. ENDFORM.                    “solve
  59. *———————————————————————-*
  60. FORM valid_solution  USING    lt.
  61. * n = 14 has 365,596 solutions. This takes about 300 seconds.
  62.   lv_count = lv_count + 1.
  63.   CHECK lv_count MOD 1000 EQ 0.
  64.   CALL FUNCTION ‘SAPGUI_PROGRESS_INDICATOR’
  65.     EXPORTING
  66.       text = lv_count.    ” Text to be Displayed
  67. ENDFORM.                    ” VALID_SOLUTION

/.

Assigned Tags

      3 Comments
      You must be Logged on to comment or reply to a post.
      Author's profile photo Ruben Hernan Mircin Ramirez
      Ruben Hernan Mircin Ramirez

      Hi Manish,

      Awesome job!

      Best regards.

      Author's profile photo Eitan Rosenberg
      Eitan Rosenberg

      Wow......

      You sure saved ABAP honor.....

      And another Wow.....

      Regards.

      Author's profile photo Former Member
      Former Member

      Brilliant - I can get ur code only if I debug - common abaper brain 🙂