N Queens Algorithm - Quick and Dirty

[Former Member]

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

/.