Magic Square Sets
Problem Description
We propose a collection of magic square problems for System Competition under ASP-RFC. These problems can be easily encoded using aggregates, in a nontrivial way (meaning they are not easily reduced to ASP-core), and thus may serve as benchmarks for testing the effectiveness of the aggregate handling by a solver. The problem instances can also be generated by adding additional constraints.
Input Predicates: data/1, num/1
Output Predicates: sqr/3
Problem Description:
Normal magic squares: a magic square of order 'n' is an arrangement of n2 numbers, 1..n2, in a square, such that the 'n' numbers in all rows, all columns, and both diagonals sum to the same constant n*(n^2+1)/2. It is known that the magic square of any order exists. But the exact complexity is unknown to our best knowledge.
Semimagic squares: it is a relaxed normal magic square in the sense that only the rows and columns but not necessarily the diagonals sum to the magic constant n*(n^2+1)/2.
Panmagic squares: a panmagic square is a magic square with the additional property that the broken diagonals, i.e. the diagonals that wrap round at the edges of the square, also add up to the magic constant n*(n^2+1)/2. The Number of distinct (modulo rotation and reflection) panmagic square of order n=1,2,3,4,5,6 are 1, 0, 0, 48, 3600, 0 respectively. (Cf. http://oeis.org/searchq=panmagic+square&sort=&language=english&go=Search)
Associative magic squares: An associative magic square is a magic square for which every pair of numbers symmetrically opposite to the center sum up to the same value n^2+1. The number of distinct (modulo rotation and reflection) associative magic squares of order n=1,2,3,4,5,6 are 1,0,1,48,48544,0 respectively. (cf. http://oeis.org/search?q=associative+magic+square&sort=&language=english&go=Search)
Bimagic squares: A bimagic square is a magic square that also remains magic if all of the numbers it contains are squared.
Trimagic squares: A trimagic square is a magic square that also remains magic if all of the numbers it contains are squared or cubed. In the benchmark, we require for the cubed cases only.
Author(s)
- Yisong Wang
- Guizhou University, China
- Jia-Huai You
- University of Alberta, Canada