Hello Brent, Sunday, July 2, 2006, 3:58:11 AM, you wrote:
We recently began considering another benchmark for the shootout, namely a Magic Square via best-first search. This is fairly
i've slightly beautified your printMatrix code: ..... where showMatrix n grid = join "\n" [ showRow y | y<-[1..n] ] where showRow y = join " " [ show $ grid!(x,y) | x<-[1..n] ] join filler pss = concat (intersperse filler pss)
inefficient, and we may need to shift to another approach due to the extremely large times required to find a solution for larger squares.
it's interesting to see one more compiler-dependent (as opposite to libraries-dependent) benchmark in shootout. It seems that the devil hides in the last function, possibleMoves. i tried to replace using of Data.Set with Data.Set.Enum by David F. Place, but got only 5% improvement. This procedure heavily uses lists and that is not the fastest data structure, especially in Haskell where lists are lazy. One possible solution may be to use lists of strict (and automatically unboxed) elements and/or lists that are strict in their links. Another possible solution will be to use unboxed arrays and implement all the required List routines for them. About the overall algorithm - it tends to recompute data that is almost not changed, such as list of already used numbers. It resembles me sudoku solvers that was discussed here several months ago - its highly possible that optimization tricks developed for this task will be appropriate to speed up magic squares too. -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com