8 Queens Problem in JavaScript

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

ปัญหา 8 Queens คืออะไร?

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

แอลกอริธึม (Algorithm) ที่ใช้แก้ปัญหา

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

ตัวอย่างโค้ดเบื้องต้นในภาษา JavaScript:

const SIZE = 8;
let solutions = 0;
let board = new Array(SIZE).fill().map(() => new Array(SIZE).fill('.'));

function isSafe(row, col) {
  for (let i = 0; i < row; i++) {
    if (board[i][col] === 'Q') {
      return false;
    }
  }
  for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 'Q') {
      return false;
    }
  }
  for (let i = row, j = col; i >= 0 && j < SIZE; i--, j++) {
    if (board[i][j] === 'Q') {
      return false;
    }
  }
  return true;
}

function solveNQ(row = 0) {
  if (row === SIZE) {
    console.log(`Solution ${++solutions}:`);
    printBoard();
    return;
  }
  for (let i = 0; i < SIZE; i++) {
    if (isSafe(row, i)) {
      board[row][i] = 'Q';
      solveNQ(row + 1);
      board[row][i] = '.';
    }
  }
}

function printBoard() {
  board.forEach(row => console.log(row.join(' ')));
}

solveNQ();

Usecase ในโลกจริง

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

Complexity ของ Algorithm

ในเบื้องต้น วิธีการแบ็คทราคคิงอาจมีความซับซ้อนโดยประมาณ O(n!) เนื่องจากราชินีแต่ละตัวมีโอกาสที่จะวางใน n จุด แต่ด้วยการเพิ่มเช็คเงื่อนไข isSafe เข้าไป จึงช่วยลดความซับซ้อนของปัญหาลงมาอย่างมาก

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

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

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