รู้จัก 8 queens puzzle มั้ยครับ?
กฎของ 8 queens puzzle มีอยู่ว่า
ให้วาง queen 8 ตัว บนตาราง 8x8
โดยที่ queen แต่ละตัว ไม่กินกันเอง



เอาล่ะครับ คุณลองเขียน Code ของคุณดู ภาษาอะไรก็ได้ เขียนยังไงครับ
นี่เป็นตัวอย่าง Code 8 queens ของ Python นะครับ

def n_queens(n, width):
     if n == 0:
        return [[]] # one solution, the empty list
    else:
        return add_queen(n-1, width, n_queens(n-1, width))

def add_queen(new_row, width, previous_solutions):
    solutions = []
    for sol in previous_solutions:
        # Try to place a queen on each column on row new_row.
        for new_col in range(width):
            # print 'trying', new_col, 'on row', new_row
            if safe_queen(new_row, new_col, sol):
                # No interference, so add this solution to the list.
                solutions.append(sol + [new_col])
    return solutions

def safe_queen(new_row, new_col, sol):
    # Check against each piece on each of the new_row existing rows.
    for row in range(new_row):
        if (sol[row] == new_col or                  # same column clash
            abs(sol[row] - new_col) == abs(row - new_row)):   # diagonal clash
                return 0
    return 1

for sol in n_queens(8, 8):
   print sol

Code Python ผมคัดลอกมาจาก wiki นะครับ

Code Python ที่ว่าสั้น ลองเปรียบเทียบกับ C# ดูกัน
โดยใช้หลักของ Functional Programming และ Linq

//ประกาศ function สำหรับทำ NQueens
Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> nQueens = null;

                    //queen ตัวปัจจุบัน
nQueens = queens => from q in queens

                    //join กับ NQueens จาก queens ตัวที่เหลือ, ตัวที่เหลือต้องมีค่าไม่เท่ากับตัวปัจจุบัน
                    from qs in nQueens(queens.Where(t => t != q))

                    //queen ตัวปัจจุบัน ต้องมีเส้นทะแยงมุม ไม่เท่ากับ NQueens ตัวใดเลย
                    where !qs.Where((t, i) => i + 1 == Math.Abs(q - t)).Any()
                   
                    //เชื่อม queen ตัวปัจจุบันกับ NQueens
                    select new[] { q }.Concat(qs);

//ถ้า queen เหลือตัวเดียว, NQueens ก็มีแค่ solution เดียว
nQueens = nQueens.When(queens => queens.Count() == 1, queens => new[] { queens });

จบแล้วครับ
ใช้แค่ 3 statements สำหรับเขียน Function
Method ชื่อ When เอามาจาก Post นี้ นะครับ

ลอง Output ออกมาเป็นแบบ Console ดู

Console.WriteLine("  A B C D E F G H");
nQueens(0.To(7)).First().ForEach((q, i) =>
    Console.WriteLine("{0} " + "_ ".Repeat(q) + "Q " + "_ ".Repeat(7 - q), i + 1)
);
//  A B C D E F G H
//1 Q _ _ _ _ _ _ _
//2 _ _ _ _ Q _ _ _
//3 _ _ _ _ _ _ _ Q
//4 _ _ _ _ _ Q _ _
//5 _ _ Q _ _ _ _ _
//6 _ _ _ _ _ _ Q _
//7 _ Q _ _ _ _ _ _
//8 _ _ _ Q _ _ _ _

คำตอบถูกต้อง

เมื่อเปรียบเทียบกับ Code ของ Python ด้านบน
จะพบว่าประหยัดบรรทัดไปเยอะ แถมอ่านง่าย
อ่านแล้วเข้าใจการทำงานของ Function ได้ทันที

อีกสักตัวอย่างจาก โจทย์ในห้องหว้ากอ ของ คุณศล
"จากรูปด้านล่าง ใส่เลข 2-8 ลงในวงกลมที่ว่าง
โดยใช้เลขละหนึ่งครั้ง มีเงื่อนไขคือเลขแต่ละตัวจะต้อง
อยู่ระหว่าง (มีเพื่อนบ้านเป็น) เลขที่ใหญ่กว่ามัน หรือเล็กกว่ามันทั้งซ้าย-ขวา
ถามว่า เราสามารถใส่เลขได้กี่แบบ?

(ตัวอย่างเช่น 4-2-1 เลข 2 ตรงกลางผิดเงื่อนไข หรือ 4-2-3 เลข 2 ไม่ผิดเงื่อนไข)"



ใช้ for-loop คงดูซับซ้อน
แต่ถ้าเราใช้หลักการเดียวกับ N-Queens ด้านบน
รับรองง่ายนิดเดียว

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> func = null;
func = set => from x in set
              from xs in func(set.Where(t => t != x))
              where (xs.Count() % 2 == 1) ? x > xs.First() : x < xs.First()
              select new[] { x }.Concat(xs);
func = func.When(set => !set.Any(), set => new[] { new[] { 1 } });

Console.WriteLine(func(2.To(8)).Count());
//272

เขียนเสร็จแล้ว
จะเห็นว่า Code ส่วนใหญ่จะคล้ายกับ N-Queens
แต่ต่างกันแค่ส่วนของ Where
ซึ่งบอกว่า ถ้าจำนวนเลขในวงแหวนเป็นเลขคี่ เลขปัจจุบันต้องมากกว่าเลขล่าสุด
แต่ถ้าจำนวนเลขในวงแหวนเป็นเลขคู่ เลขปัจจุบันต้องน้อยกว่าเลขล่าสุด

จบแล้วครับ
Post หน้ามาทำ Extension Methods กันดีกว่าครับ

* อ่านจบแล้ว กรุณา Comment ด้วยครับ เพื่อเป็น Feedback และเป็นกำลังใจ
* บทความนี้คัดลอกได้ แต่ต้องมี Link หรือ Url กลับมาที่หน้านี้ และเมื่อคัดลอกแล้วกรุณา Comment แจ้งด้วยครับ

Create Date : 31 สิงหาคม 2551
Last Update : 31 สิงหาคม 2551 1:34:00 น.		5 comments
Counter : 2220 Pageviews.
Share Tweet