[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]


Poblem DescriptionGiven the twenty five
numbers. 1,1,2,2,2,2,2,3,3,3,3,3,3,4,5,5,5,5,6,6,6,6,6,7,9, arrange them in a
5x5 grid in such a way that each horizontal row, vertical column and the
two main diagonals all sum to 20.

One of 12 solutions from candidate column set 11279 22556 23366 23456 33356 
We're getting closer, but not there yet. We can take any of the Phase 2 results and build 5x5 grid in which each group of 5 digits becomes a column which sum to 20, but it is unlikely that the sums in the other direction (the rows) will all be 20, Phase 3 works on one of the Phase 2 results at a time. forming 5 columns and then permuting the numbers contained in each column looking for rows which all sum to 20. Since there are 5! (=120) ways to arrange each column, there could be as many as 120^{5} (25 billion) possibilities to check. In practice, there are many fewer than that because, again, many of the permutations will have only 30 or 60 unique permutations because of duplicate number values in the column. The search space is also reduced by abandoning any solution if the row sum of the columns placed so far exceeds 20. I have not evaluated all 110 possibilities, but in the first and last 10 groups, produced from 0 to 56 solutions each with run times per group ranging from 1 to 23 seconds. The program does not rearrange the columns during the search, only the row positions within each column, so there are likely hundreds or thousands more solutions than this version finds.
Nonprogrammers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.
The program uses the TComboset class to produce the required combinations and permutations. Recompiling will require a download of any version of our DFF Library zip file.
To save time during searching, Phase 1 attaches a string list with all of the unique permutations to each of the 30 potential columns and Phase 3 reads this list rather than recomputing them each time. Phase 3 process uses calls to recursive local function GetNextPermute to add columns to the potential solution being tested. As each permutation of each potential column is added, the row sums of the columns added so far is kept and if the row sum total exceeds 20, the search for that branch is abandoned. This was a late addition which reduced search times from minutes to seconds for each Phase 2 line being tested.
The code is well commented and time is short, so I'll leave this section at that for now.
???  
Original: March 10, 2012 
Modified: February 18, 2016 
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 20002016, Gary Darby All rights reserved. 