ช่วงนี้ไม่ค่อยมีเวลามาเขียนโปรแกรมแก้โจทย์ Algorithm เล่นนานละ
แต่ไปเจอโจทย์นึงที่ Web TwoGuru ชื่อว่า Knight's Tour
น่าสนใจเลยลองเขียนดูบ้าง



Knight's Tour คือ การเดินม้าในตารางหมากรุก 8x8
โดยเริ่มที่ช่องใดก็ได้ เดินไปเรื่อย ๆ ห้ามทับจุดเดิม และเดินให้ครบทุกช่อง
เห็นโจทย์ก็รู้เลยน่าสนใจ
ซึ่งดูผิวเผินน่าจะยาก จากการคำนวนของ Web TwoGuru เห็นว่ามีรูปแบบเป็น สี่แสนล้านล้านล้านล้านล้านล้านรูปแบบ !!!
แต่คิดว่าหลักการของ Functional Programming น่าจะแก้ปัญหานี้ได้ไม่ยาก

ไม่พูดพร่ำทำเพลง เขียนรูปแบบการเดินของม้าก่อนเลย

int[][] moves = new[] {
                    new[] {+1, -2},
                    new[] {+2, -1},
                    new[] {+2, +1},
                    new[] {+1, +2},
                    new[] {-1, +2},
                    new[] {-2, +1},
                    new[] {-2, -1},
                    new[] {-1, -2},
};

ต่อด้วยหากระดาน กระดาน 8x8 ซึ่งใช้ 64 ช่อง
ตอนแรกคิดว่าจะใช้ BitArray ขนาด 64 ช่อง แต่คิดไปคิดมา
ulong ก็เป็น Type ที่มี 64bit นี่หว่า เลยตัดสินใจใช้ ulong
ก็เลยต้องเขียนสูตรการแปลงจากตำแหน่งบนกระดานเป็น ulong และก็แปลงกลับ

Func<int[], ulong> positionToULong = pos => 1UL << (pos[1] * 8 + pos[0]);
Func<ulong, int[]> ulongToPosition = u => {
    int log2 = 0, x, y;
    while (u != 1) {
        log2++;
        u >>= 1;
    }
    y = Math.DivRem(log2, 8, out x);
    return new[] { x, y };
};

ต่อมาก็เขียนสูตรการเดินของม้าซะ
ในแต่ละช่องม้าสามารถเดินไปจุดไหนบ้างใช้สูตรนี้

Func<ulong, ulong[]> nextPoint = u => {
    var pos = ulongToPosition(u);
    return (from move in moves
            select new[] { pos[0] + move[0], pos[1] + move[1] } into nextPos
            where nextPos[0] >= 0 && nextPos[0] < 8 &&
                  nextPos[1] >= 0 && nextPos[1] < 8
            select positionToULong(nextPos)).ToArray();
};
nextPoint = nextPoint.Memoize();

ในสูตรถ้าม้าตัวไหนเดินออกนอกตารางก็ตัดทิ้งไป
แล้วก็จะเห็นคำสั่ง Memoize ในบรรทัดสุดท้าย
เป็นการทำให้ Function จำคำตอบได้ไม่ต้องคำนวณใหม่
อ่าน Article เก่า เพิ่มเติมครับ

และก็มาถึง Function สุดท้าย
เป็น Algorithm การเดินม้าให้ครบ 64 ตาแล้วครับ

Func<ulong, ulong, IEnumerable<IEnumerable<ulong>>> func = null;
func = (board, u) => {
    //ถ้าเดินทับจุดเดิม ก็ไม่มีผลลัพธ์
    if ((board & u) > 0)
        return Enumerable.Empty<IEnumerable<ulong>>();

    //ถ้าเดินครบ 64 ตา ก็คืนค่าตำแหน่งสุดท้าย
    var newBoard = board | u;
    if (newBoard == ulong.MaxValue)
        return u.ToEnumerable().ToEnumerable();

    //เอาตาเดินม้าถัดไป มาวนใส่ Function นี้
    //ได้ผลลัพธ์ ก็เอาตำแหน่งปัจจุบันมารวมกับคำตอบที่ได้
    return from px in nextPoint(u)
           from sol in func(newBoard, px)
           select new[] { u }.Concat(sol);
};

ป๊าด!!! จบแล้วครับ เริ่มรันได้เลย

var result = (from pos in func(0, 1).First().Select(ulongToPosition).WithIndex()
              group pos by pos.B[1] into g
              orderby g.Key
              select (from pos2 in g
                      orderby pos2.B[0]
                      select pos2.A.ToString("00")).Join(" ")).Join("rn");
Console.WriteLine(result);

//00 37 54 33 02 35 18 21
//53 46 01 36 19 22 03 16
//38 55 32 45 34 17 20 09
//47 52 39 56 23 10 15 04
//58 31 44 51 40 25 08 11
//43 48 57 24 61 14 05 26
//30 59 50 41 28 07 12 63
//49 42 29 60 13 62 27 06

ใช้เวลาไป 2 วินาทีกว่า ๆ!!
โค๊ดแปลงเป็นตารางมี Function แปลก ๆ ไม่ต้องงงว่ามาจากไหน
เป็น Function ที่ผมเขียนใช้เอง
สนใจไปหาดาวน์โหลดใน Framework ของผมนะครับ

เพื่อนผมมันบอกว่า Functional Programming อ่านยาก
เอาไปใช้ใน Production ไม่ได้
ผมก็ว่าจริงครับ ถ้าเขียนแล้วคนอื่นอ่านไม่เข้าใจ ก็เป็นโค๊ดที่ Maintain ไม่ได้
แต่มันก็เขียนสนุกครับ ตอนนี้เลยได้แต่เขียนคนเดียว มันส์คนเดียว
คนไหนเขียน Functional Programming บ้าง ยกมือขึ้นครับ !!! (จะมีมั้ยเนี่ย หายากจริง ๆ)

Create Date : 04 สิงหาคม 2552
Last Update : 4 สิงหาคม 2552 0:45:26 น.		4 comments
Counter : 2871 Pageviews.
Share Tweet