// See http://www.itmn.biz/
//      > ３×３魔方陣　問題
//     http://www.ne.jp/asahi/suzuki/hp/houjin3.htm
//      > 魔方陣
//     http://www.grogono.com/magic/makeyourown4.php
//     > Make Your Own 4x4 Magic Square
//     http://quasistoic.org/fun/magicsquare/
//       > 4x4 Magic Square Solver
//     http://quasistoic.org/ts/archives/2006/08/13/magic-square-solver/
//        > magic square generator

package perm

object MagicsquareCheck {

    def apply(n:Int) = {
        n match {
            case 3 => new MagicsquareCheck3x3
            case 4 => new MagicsquareCheck4x4
            case _ => null
        }
    }
}

abstract class Checker {
    def scan(ls:List[Int]):(BigInt, List[Int])
    def check(ls:List[Int]):Boolean
}

case class MagicsquareCheck3x3() extends Checker {

    //
    //  0 1 2
    //  3 4 5
    //  6 7 8

    def scan(ls:List[Int]):(BigInt,List[Int]) = {
        val s7 = ls.takeRight(7).sort(_ < _)
        if (ls.apply(0) + ls.apply(1) + s7(0) > 15) {
            (Fact.factMem(7), null)
        } else if (ls.apply(0) + ls.apply(1) + s7(6) < 15) {
            (Fact.factMem(7), null)
        } else if (ls.apply(0) + ls.apply(1) + ls.apply(2) != 15) {
            (Fact.factMem(6), null)
        } else {
            if (check(ls)) {
                (BigInt(1), ls)
            } else {
                (BigInt(1), null)
            }
        }
    }

    // 3 x 3 の魔法陣のためのチェック条件
    def check(ls:List[Int]) = (
        ls.apply(0) + ls.apply(1) + ls.apply(2) == 15 &
        ls.apply(3) + ls.apply(4) + ls.apply(5) == 15 &
        ls.apply(6) + ls.apply(7) + ls.apply(8) == 15 &

        ls.apply(0) + ls.apply(3) + ls.apply(6) == 15 &
        ls.apply(1) + ls.apply(4) + ls.apply(7) == 15 &
        ls.apply(2) + ls.apply(5) + ls.apply(8) == 15 &

        ls.apply(0) + ls.apply(4) + ls.apply(8) == 15 &
        ls.apply(2) + ls.apply(4) + ls.apply(6) == 15
    )
}

case class MagicsquareCheck4x4() extends Checker {
    //
    //  0  1  2  3
    //  4  5  6  7
    //  8  9 10 11
    // 12 13 14 15
    //
    def scan(ls:List[Int]):(BigInt,List[Int]) = {
        val s14 = ls.takeRight(14).sort(_ < _)
        val s13 = ls.takeRight(13).sort(_ < _)
        val s12 = ls.takeRight(12).sort(_ < _)
        val s11 = ls.takeRight(11).sort(_ < _)
        val s10 = ls.takeRight(10).sort(_ < _)
        val s09 = ls.takeRight(9).sort(_ < _)
        //val s08 = ls.takeRight(8).sort(_ < _)
        //val s07 = ls.takeRight(7).sort(_ < _)
        //val s06 = ls.takeRight(6)
        if (ls.apply(0) + ls.apply(1) + s14.apply(0) + s14(1) > 34) {
            //println("skip 14!")
            //println(ls)
            (Fact.factMem(14), null)
        } else if (ls.apply(0) + ls.apply(1) + s14.apply(12) + s14(13) < 34) {
            //println("skip 14!")
            //println(ls)
            (Fact.factMem(14), null)

        } else if (ls.apply(0) + ls.apply(1) + ls.apply(2) + s13(0) > 34) {
            //println("skip 13!")
            //println(ls)
            (Fact.factMem(13), null)
        } else if (ls.apply(0) + ls.apply(1) + ls.apply(2) + s13(12) < 34) {
            //println("skip 13!")
            //println(ls)
            (Fact.factMem(13), null)

        } else if (ls.apply(0) + ls.apply(1) + ls.apply(2) + ls.apply(3) != 34) {
            //println("skip 12!")
            //println(ls)
            (Fact.factMem(12), null)

        } else if (ls.apply(0) + ls.apply(4) + s11(0) + s11(1) > 34) {
            //println("skip 11!")
            //println(ls)
            (Fact.factMem(11), null)
        } else if (ls.apply(0) + ls.apply(4) + s11(9) + s11(10)  < 34) {
            //println("skip 11!")
            //println(ls)
            (Fact.factMem(11), null)
        } else if (ls.apply(4) + ls.apply(5) + s10(0) + s10(1) > 34) {
            //println("skip 10!")
            //println(ls)
            (Fact.factMem(10), null)
        } else if (ls.apply(4) + ls.apply(5) + s10(8) + s10(9) < 34) {
            //println("skip 10!")
            //println(ls)
            (Fact.factMem(10), null)
        } else if (ls.apply(1) + ls.apply(5) + s10(0) + s10(1) > 34 ) {
            //println("skip 10!")
            //println(ls)
            (Fact.factMem(10), null)
        } else if (ls.apply(1) + ls.apply(5) + s10(8) + s10(9) < 34 ) {
            //println("skip 10!")
            //println(ls)
            (Fact.factMem(10), null)
        } else if (ls.apply(0) + ls.apply(5) + s10(0) + s10(1)  > 34) {
            //println("skip 10!")
            //println(ls)
            (Fact.factMem(10), null)
        } else if (ls.apply(0) + ls.apply(5) + s10(8) + s10(9) < 34) {
            //println("skip 10!")
            //println(ls)
            (Fact.factMem(10), null)
        } else if (ls.apply(4) + ls.apply(5) + ls.apply(6) + s09(0) > 34) {
            //println("skip 9!")
            (Fact.factMem(9), null)
        } else if (ls.apply(4) + ls.apply(5) + ls.apply(6) + s09(8) < 34) {
            // println("skip 9!")
            (Fact.factMem(9), null)
        } else if (ls.apply(2) + ls.apply(6) + s09(0) + s09(1) > 34) {
            //println("skip 9!")
            (Fact.factMem(9), null)
        } else if (ls.apply(2) + ls.apply(6) + s09(7) + s09(8) < 34) {
            //println("skip 9!")
            (Fact.factMem(9), null)
        } else if (ls.apply(3) + ls.apply(6) + s09(0) + s09(1) > 34) {
            //println("skip 9!")
            (Fact.factMem(9), null)
        } else if (ls.apply(3) + ls.apply(6) + s09(7) + s09(8) < 34) {
            //println("skip 9!")
            (Fact.factMem(9), null)
        } else if (ls.apply(4) + ls.apply(5) + ls.apply(6) + ls.apply(7) != 34) {
            // println("skip 8!")
            (Fact.factMem(8), null)
        } else if (ls.apply(0) + ls.apply(4) + ls.apply(8) != ls.apply(3) + ls.apply(6) + ls.apply(9)) {
            //println("skip 6!")
            (Fact.factMem(6), null)
        } else if (ls.apply(8) + ls.apply(9) + ls.apply(10) + ls.apply(11) != 34) {
            // println("skip 4!")
            (Fact.factMem(4), null)
        } else if (ls.apply(0) + ls.apply(4) + ls.apply(8) + ls.apply(12) != 34) {
            // println("skip 3!")
            (Fact.factMem(3), null)
        } else {
            if (check(ls)) {
                //verify(ls)
                //println("" + ls)
                (BigInt(1), ls)
            } else {
                (BigInt(1), null)
            }
        }
    }

    // 4 x 4 の魔法陣のためのチェック条件
    def check(ls:List[Int]) = (
        ls.apply(0) + ls.apply(1) + ls.apply(2) + ls.apply(3) == 34 &
        ls.apply(4) + ls.apply(5) + ls.apply(6) + ls.apply(7) == 34 &
        ls.apply(8) + ls.apply(9) + ls.apply(10) + ls.apply(11) == 34 &
        ls.apply(12) + ls.apply(13) + ls.apply(14) + ls.apply(15) == 34 &

        ls.apply(0) + ls.apply(4) + ls.apply(8) + ls.apply(12) == 34 &
        ls.apply(1) + ls.apply(5) + ls.apply(9) + ls.apply(13) == 34 &
        ls.apply(2) + ls.apply(6) + ls.apply(10) + ls.apply(14) == 34 &
        ls.apply(3) + ls.apply(7) + ls.apply(11) + ls.apply(15) == 34 &

        ls.apply(0) + ls.apply(5) + ls.apply(10) + ls.apply(15) == 34 &
        ls.apply(3) + ls.apply(6) + ls.apply(9) + ls.apply(12) == 34
    )

    def verify(ls:List[Int]) = {
        println(ls.apply(0) + ls.apply(1) + ls.apply(2) + ls.apply(3))
        println(ls.apply(4) + ls.apply(5) + ls.apply(6) + ls.apply(7))
        println(ls.apply(8) + ls.apply(9) + ls.apply(10) + ls.apply(11))
        println(ls.apply(12) + ls.apply(13) + ls.apply(14) + ls.apply(15))

        println(ls.apply(0) + ls.apply(4) + ls.apply(8) + ls.apply(12))
        println(ls.apply(1) + ls.apply(5) + ls.apply(9) + ls.apply(13))
        println(ls.apply(2) + ls.apply(6) + ls.apply(10) + ls.apply(14))
        println(ls.apply(3) + ls.apply(7) + ls.apply(11) + ls.apply(15))

        println(ls.apply(0) + ls.apply(5) + ls.apply(10) + ls.apply(15))
        println(ls.apply(3) + ls.apply(6) + ls.apply(9) + ls.apply(12))
    }
}