Skip to Content
Actions

N Queens Algorithm – Quick and Dirty

June 5, 2014 | 49 Views |
 abapchessmanish kumar s blogmathematicspuzzlesqueenscn
Follow

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

/.

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