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

/.

To report this post you need to login first.

3 Comments

You must be Logged on to comment or reply to a post.

Leave a Reply