ปัญหาสี่เหลี่ยมเรขาคณิต: 8 Queens Problem ในภาษา Delphi Object Pascal

 

 

บทนำ

8 Queens Problem คือปัญหาที่น่าสนใจในศาสตร์การเขียนโปรแกรมและอัลกอริธึมที่ได้เป็นที่รู้จักอย่างกว้างขวาง โดยเฉพาะในสายงานการสอนและการแข่งขันเขียนโปรแกรม ปัญหานี้มีวัตถุประสงค์คือการวางตำแหน่งราชินี 8 ตัวบนกระดานหมากรุก 8x8 โดยไม่ให้มีราชินีตัวใดที่สามารถโจมตีกันได้ ไม่ให้มีการเรียงจำนวนตามแนวนอน แนวตั้ง หรือแนวทแยง

 

อัลกอริธึม

การแก้ปัญหา 8 Queens Problem สามารถทำได้หลายวิธี แต่ที่นิยมใช้กันก็คืออัลกอริธึมการค้นหากลับ (Backtracking) ซึ่งช่วยให้เราทดสอบความเป็นไปได้ในการวางราชินี โดยการทดลองวางราชินีทีละตัว จากนั้นตรวจสอบว่าผลลัพธ์ที่ได้เป็นไปตามเงื่อนไขหรือไม่ หากไม่เป็นไปตามเงื่อนไข จะถอยกลับไปลบการวางราชินีก่อนหน้าแล้วลองวางอีกครั้ง

 

ตัวอย่างโค้ดใน Delphi Object Pascal

มาสร้างตัวอย่างโค้ดในภาษา Delphi Object Pascal กันดีกว่า โดยโค้ดนี้จะช่วยให้เราหาและแสดงผลลัพธ์ตำแหน่งของราชินีในกระดาน 8x8:

 program EightQueens;

uses crt;

var
  board: array[1..8, 1..8] of integer;
  solutionCount: integer;

procedure PrintBoard;
var
  i, j: integer;
begin
  writeln('Solution ', solutionCount);
  for i := 1 to 8 do begin
    for j := 1 to 8 do begin
      if board[i, j] = 1 then
        write(' Q ')
      else
        write(' . ');
    end;
    writeln;
  end;
  writeln;
end;

function IsSafe(row, col: integer): boolean;
var
  i: integer;
begin
  for i := 1 to col - 1 do
    if (board[row, i] = 1) or
       (row - (col - i) >= 1) and (board[row - (col - i), i] = 1) or
       (row + (col - i) <= 8) and (board[row + (col - i), i] = 1) then
      exit(false);
  exit(true);
end;

procedure SolveNQueens(col: integer);
var
  i: integer;
begin
  if col > 8 then begin
    Inc(solutionCount);
    PrintBoard;
    exit;
  end;

  for i := 1 to 8 do begin
    if IsSafe(i, col) then begin
      board[i, col] := 1;
      SolveNQueens(col + 1);
      board[i, col] := 0; // Backtrack
    end;
  end;
end;

begin
  clrscr;
  solutionCount := 0;
  FillChar(board, SizeOf(board), 0);
  SolveNQueens(1);
  if solutionCount = 0 then
    writeln('No solution exists!');
  readln;
end.

การทำงานของโค้ด

- PrintBoard: ฟังก์ชันนี้ใช้แสดงผลกระดานที่มีราชินี - IsSafe: ใช้ตรวจสอบว่าราชินีที่วางจะไม่โจมตีราชินีตัวอื่น - SolveNQueens: ฟังก์ชันหลักที่ทำการวางราชินีและเรียกใช้การค้นหาแบบกลับไปกลับมา

 

Use Case ในโลกจริง

แม้ว่า 8 Queens Problem จะดูเหมือนเป็นปัญหาที่เกิดจากการเล่นเกม แต่แนวทางการแก้ปัญหาแบบ Backtracking นี้ยังมีการนำไปใช้ในสถานการณ์อื่น ๆ เช่น:

- ศิลปะแต่ละด้าน: การวางแบบสถาปัตย์ที่จำกัดหรือในการสร้างภาพวาดแบบที่มีความซับซ้อน - การจัดตารางเวลา: การจัดการตารางเวลาหรืองานในโครงการที่จำกัด โดยต้องมีการคำนึงถึงเวลาและพื้นที่ - ปัญหาการจัดกลุ่ม: ปัญหาที่เกี่ยวข้องกับการจัดกลุ่มข้อมูลหรือการจัดที่นั่งในงานสัมมนา

 

วิเคราะห์ความซับซ้อน

ความซับซ้อนของอัลกอริธึม Backtracking ในปัญหา 8 Queens อยู่ที่ O(N!), ซึ่ง N คือจำนวนราชินี โดยเราจะต้องตรวจสอบแต่ละกรณีที่เป็นไปได้ แต่เนื่องจากปัญหานี้มีแนวโน้มที่จะลดความซับซ้อนลงผ่านการใช้เทคนิคการตัดสินใจจึงส่งผลให้ใช้งานได้จริงในเวลาอันสั้น

ข้อดีและข้อเสีย

ข้อดี

:

- สามารถแก้ปัญหาที่ซับซ้อนได้ด้วยการกำหนดเงื่อนไขง่าย ๆ

- ใช้งานง่ายและเข้าใจง่าย แม้สำหรับผู้เริ่มต้น

ข้อเสีย

:

- ไม่สามารถใช้ได้ดีในปัญหาที่มีความซับซ้อนสูง อาจใช้เวลานานในการประมวลผล

- การทำงานจะลดลงตามจำนวนข้อมูลที่เพิ่มมากขึ้น

 

บทสรุป

8 Queens Problem เป็นปัญหาที่มีทั้งความสนุกและความท้าทายในการเขียนโปรแกรม ซึ่งสามารถนำไปใช้ในหลายสถานการณ์ในโลกแห่งความจริง หากคุณสนใจในศาสตร์การเขียนโปรแกรมและเทคนิคการแก้ปัญหา เราขอเชิญคุณเข้าร่วมการเรียนรู้ที่ EPT (Expert-Programming-Tutor) ที่จะพาคุณไปสู่การพัฒนาในด้านการเขียนโปรแกรมอย่างมีประสิทธิภาพ!

การเรียนรู้การเขียนโปรแกรมจะไม่เหลือเพียงแค่ทักษะทางเทคนิคเท่านั้น แต่ยังเป็นเครื่องมือที่สามารถเปิดโอกาสให้คุณสร้างสรรค์สิ่งใหม่ ๆ ที่จะช่วยเปลี่ยนแปลงโลกได้ในอนาคต!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง