N Queens Algorithm – Quick and Dirty
I saw this document today which solves N Queen puzzle.
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
- TYPES:
- BEGIN OF ty,
- x TYPE i,
- y TYPE i,
- END OF ty,
- tty TYPE TABLE OF ty.
- PARAMETERS pv_max TYPE i DEFAULT 8 OBLIGATORY.
- DATA: lt TYPE TABLE OF ty, “n Queen coordinates
- ls TYPE ty,
- lv_count TYPE decfloat34.
- DO pv_max TIMES.
- ls–x = sy–index. “avoids horizontal conflict
- APPEND ls TO lt.
- ENDDO.
- PERFORM solve USING lt.
- WRITE:/ ‘Total solutions: ‘, lv_count.
- *———————————————————————-*
- FORM solve USING lt TYPE tty.
- FIELD-SYMBOLS <fs> TYPE ty.
- DATA: ls TYPE ty,
- x TYPE i,
- y TYPE i,
- flag TYPE boolean.
- READ TABLE lt ASSIGNING <fs> WITH KEY y = 0.
- IF sy–subrc EQ 0.
- x = <fs>–x.
- DO pv_max TIMES.
- y = sy–index.
- READ TABLE lt TRANSPORTING NO FIELDS WITH KEY y = y.
- CHECK sy–subrc NE 0. “no vertical conflict
- ” avoid diagonal conflicts having / and \ direction
- flag = abap_true.
- LOOP AT lt INTO ls WHERE x > 0 AND y > 0.
- CHECK ls–x – x EQ ls–y – y OR
- ls–x – x EQ y – ls–y.
- flag = abap_false.
- EXIT.
- ENDLOOP.
- ” fill non-conflicting value and continue recursion
- CHECK flag EQ abap_true.
- <fs>–y = y.
- ” n values filled == solution
- IF x EQ pv_max.
- PERFORM valid_solution USING lt.
- ELSE.
- PERFORM solve USING lt.
- ENDIF.
- ENDDO.
- CLEAR <fs>–y.
- ENDIF.
- ENDFORM. “solve
- *———————————————————————-*
- FORM valid_solution USING lt.
- * n = 14 has 365,596 solutions. This takes about 300 seconds.
- lv_count = lv_count + 1.
- CHECK lv_count MOD 1000 EQ 0.
- CALL FUNCTION ‘SAPGUI_PROGRESS_INDICATOR’
- EXPORTING
- text = lv_count. ” Text to be Displayed
- ENDFORM. ” VALID_SOLUTION
/.
Hi Manish,
Awesome job!
Best regards.
Wow......
You sure saved ABAP honor.....
And another Wow.....
Regards.
Brilliant - I can get ur code only if I debug - common abaper brain 🙂