วิธีเขียนโปรแกรมเพื่อ Solve Puzzles

Published in

KBTG Life

12 min readSep 11, 2023

เรื่องมีอยู่ว่าวันนึงลูกผมเล่นเกมส์ Tricky Doors แล้วไปเจอ Puzzle ด่านนึงที่ให้ Chip ที่อยู่ติดกันกระโดดข้ามกัน เพื่อกิน Chip ในกระดานให้เหลือแค่ตัวเดียว

ลูกเล่นยังไงก็ไม่ผ่านสักที เลยเอามาให้ผมเล่น แต่ผมเองก็เล่นไม่ผ่านเหมือนกัน ทั้งๆ ที่บนกระดานมี Chip ตั้ง 18 ตัว แถมข้ามได้ทั้งขึ้นลงซ้ายขวา ทำให้มี Combination เยอะมาก เล่นยังไงก็ไม่ผ่าน

โชคดีที่สมัยเด็กผมเคยเขียนโปรแกรมเพื่อ Solve Puzzle จำพวก 180 IQ, Knight Tour, Red Stone, และ เลื่อนรถ (ขอบคุณ Bloggang ที่ยังเก็บ Blog เก่าๆ ของผมไว้อยู่)

ผมจึงต้องงัดท่าไม้ตาย เขียนโปรแกรมเพื่อ Solve มันซะเลย ดังนั้นในบทความนี้เราจะมา Walkthrough วิธีการเขียนโปรแกรมเพื่อ Solve Puzzle นี้กัน ซึ่งเทคนิคนี้สามารถประยุกต์ใช้กับ Puzzle ได้หลายแบบเลยทีเดียว

ขั้นตอนการเขียนโปรแกรมเพื่อ Solve Puzzle

1. Identify State

State คือข้อมูลที่เราจะใช้เพื่อเล่น Puzzle นั้นๆ เช่น กระดาน และ Chip บนกระดาน ทริคในการเขียน State ง่ายๆ คือ ถ้าเราเห็นอะไร เราก็ใส่ข้อมูลตามที่เราเห็นไปเลย เช่น จากตัวอย่างข้างบน ผมเขียน State ออกมาดังนี้

const board = [
  " o     xx",
  "  oo o  x",
  " o oo   x",
  "o oo oo x",
  " o  o  xx"
];

โดย o จะแทนช่องที่มี Chip, [space] แทนช่องที่ไม่มี Chip และ x คือช่องที่เดินไปไม่ได้

2. Identify Actions และตัวเลือกทั้งหมดของ Action

Action คือผู้เล่นจะทำอะไรกับ Puzzle นี้ได้บ้าง อย่างเกมส์นี้ Action คือจะเลือก Chip ตัวไหน และกระโดดไปทางไหน

Chip ตัวไหนอาจจะแทนด้วย 2 ตัวแปรก็คือ

Row แถวที่ Chip นั้นอยู่ มีตั้งแต่แถวที่ 0 ถึงแถวที่ 4
Col คอลัมน์ที่ Chip นั้นอยู่ มีตั้งแต่คอลัมน์ที่ 0 ถึงคอลัมน์ที่ 8

และการกระโดดก็แทนด้วย

Direction มีได้ 4 ทิศคือ Up, Down, Left, Right

3. Apply Action

คือการเขียน Function ที่รับ State หลังทำ Action แล้วเกิด State ใหม่ โดยการเขียน Function นี้จะประกอบไปด้วย 2 สเต็ป ได้แก่

3.1 Validate Action ในเกมส์นี้เราก็ต้อง Validate ว่า…

Row และ Col ที่ส่งเข้ามาต้องมี Chip อยู่
Row และ Col ในช่องถัดไปก็ต้องมี Chip อยู่ เพื่อให้โดนกิน
Row และ Col ใน 2 ช่องถัดไปต้องเป็นช่องว่าง เพื่อให้ Chip กระโดดลงไปได้

ในเกมส์นี้ถ้า Validate ไม่ผ่าน ก็จะ Return Null

3.2 Apply Action เมื่อมีการกระโดดข้ามแล้ว…

Row และ Col จะต้องเป็นช่องว่าง เพราะ Chip กระโดดไปแล้ว
Row และ Col ช่องถัดไปก็ต้องว่าง เพราะโดนกิน
Row และ Col ใน 2 ช่องถัดไปจะต้องมี Chip อยู่ เพราะเป็นช่องที่ Chip กระโดดลงมา

เขียนเป็นโค้ดได้ดังนี้

function calNextBoard(board, row, col, direction) {

  // คำนวนตำแหน่งจากทิศทางที่ chip จะกระโดดข้าม
  const [killRow, killCol, moveToRow, moveToCol] = calcPosition(row, col, direction);

  // - row และ col ในช่องถัดไปก็ต้องมี chip อยู่ เพื่อให้โดนกิน
  if (board[killRow]?.[killCol] !== 'o') {
    return null;
  }
  // - row และ col ใน 2 ช่องถัดไปต้องเป็นช่องว่าง เพื่อให้ chip กระโดดลงไปได้
  if (board[moveToRow]?.[moveToCol] !== ' ') {
    return null;
  }

  // 3.2 Apply Action
  const array = board.map(it => it.split(''));
  // - row และ col จะต้องเป็นช่องว่าง เพราะ chip กระโดดไปแล้ว
  array[row][col] = ' ';
  // - row และ col ช่องถัดไปก็ต้องว่าง เพราะโดนกิน
  array[killRow][killCol] = ' ';
  // - row และ col ใน 2 ช่องถัดไปจะต้องมี chip อยู่เพราะเป็นช่องที่ chip กระโดดลงมา
  array[moveToRow][moveToCol] = 'o';

  // return
  return array.map(it => it.join(''));
}

function calcPosition(row, col, direction) {
  switch (direction) {
    case 'up':
      return [row - 1, col, row - 2, col];
    case 'down':
      return [row + 1, col, row + 2, col];
    case 'left':
      return [row, col - 1, row, col - 2];
    case 'right':
      return [row, col + 1, row, col + 2];
  }
}

4. Try All Actions and Recursive

Function นี้เป็นส่วนที่ยากที่สุด เนื่องจากการใช้จะต้องอาศัย Generator Function ของภาษาที่ซัพพอร์ต เช่น JS, Python, และ C# (ในตัวอย่างนี้ใช้ JS) และมีการ Recursive กลับเข้าไปที่ Function นี้

ไอเดียของ Function นี้คือลองทุกๆ Action เพื่อหา State ถัดไป แล้วส่ง State ถัดไปกลับเข้ามาที่ Function นี้เรื่อยๆ จนกระทั่งเจอผลลัพธ์

เราสามารถ Break Down Function นี้ออกเป็น 4 สเต็ป คือ

4.1 Validate ว่า State ปัจจุบันคือคำตอบแล้วหรือยัง ถ้าเจอคำตอบแล้ว จะได้ไม่ต้องทำต่อ Yield ผลลัพธ์ออกมาได้เลย ในกรณีของ Puzzle นี้คือต้องเหลือ Chip แค่อันเดียว

4.2 หมุนทุกๆ Action (Row, Col, Direction) ก็คือ For-loop Combination ของ Action ต่างๆ เลยครับ ระหว่างหมุน Action จะ Validate Action ที่ Invalid ออกไปก่อนเลยก็ได้ เพื่อให้คำนวนเร็วขึ้น

4.3 Apply Action โดยใช้ Function ในข้อที่ 3 เพื่อหา State ถัดไป แต่ถ้า Function นี้หา State ถัดไปไม่ได้ ก็ไม่ไปต่อ

4.4 Recursive ส่ง Next State เข้า Function เดิม เพื่อหา Solution ถ้าเจอ Solution แล้ว ก็เติมข้อมูลของ State และ Action ปัจจุบันเข้าไปด้วย เพื่อแสดงเป็นผลลัพธ์

เขียนเป็นโค้ดได้ดังนี้

function* tryMove(board) {

  // 4.1 Validate ว่า state ปัจจุบันคือคำตอบแล้วหรือยัง
  // - ในกรณีของ puzzle นี้คือต้องเหลือ chip แค่อันเดียว
  if (board.join('').match(/o/g).length === 1) {
    return yield [{ board }];
  }

  // 4.2 หมุนทุกๆ action (row, col, direction)
  for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[0].length; col++) {

      // - ระหว่างหมุน action จะ validate action ที่ invalid ออกไปก่อนเลยก็ได้เพื่อให้คำนวนเร็วขึ้น
      // - ถ้าไม่มี chip ใน row+col ก็ไม่ทำต่อ
      if (board[row][col] !== 'o') {
        continue;
      }

      for (const direction of ['up', 'down', 'left', 'right']) {

        // 4.3 Apply action โดยใช้ function ในข้อที่ 3
        const nextBoard = calNextBoard(board, row, col, direction);

        // - แต่ถ้า function นี้หา state ถัดไปไม่ได้ก็ไม่ไปต่อ
        if (nextBoard === null) {
          continue;
        }

        // 4.4 Recursive ส่ง next state เข้า function เดิม เพื่อหา solution
        for (const solution of tryMove(nextBoard)) {

          // - ถ้าเจอ solution แล้วก็เติมข้อมูลของ state และ action ปัจจุบันเข้าไปด้วย เพื่อแสดงเป็นผลลัพธ์
          const action = { row, col, direction };
          yield [{ board, action}, ...solution];
        }
      }
    }
  }
}

5. เขียน Function เพื่อแสดงผลลัพธ์

เขียนผลลัพธ์นี่ไม่มี Logic อะไรมากครับ แค่ Loop จาก Solution คุณก็จะได้ State และ Action ที่เป็นคำตอบ เสร็จแล้วคุณแค่ Print มันออกมา

เขียนเป็นโค้ดได้ดังนี้

const result = tryMove(board);
const solution = result.next().value;
for (const {board, action} of solution) {
  console.table(board)
  console.log(action);
}

เมื่อ Run คำสั่งทั้งหมดจะได้ผลลัพธ์ตามนี้ครับ

┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ ' ' │ 'o' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 1, col: 3, direction: 'left' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 2, col: 3, direction: 'down' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ 'o' │ 'o' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 3, col: 6, direction: 'left' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 3, col: 4, direction: 'up' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 1, col: 5, direction: 'left' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 4, col: 4, direction: 'left' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 4, col: 2, direction: 'left' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 4, col: 0, direction: 'up' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ 'o' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 2, col: 0, direction: 'right' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ 'o' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 0, col: 1, direction: 'down' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 2, col: 1, direction: 'right' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 1, col: 3, direction: 'down' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ ' ' │ ' ' │ 'o' │ 'o' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
{ row: 3, col: 2, direction: 'right' }
┌─────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ (index) │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │
├─────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│    0    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
│    1    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    2    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │
│    3    │ ' ' │ ' ' │ ' ' │ ' ' │ 'o' │ ' ' │ ' ' │ ' ' │ 'x' │
│    4    │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ ' ' │ 'x' │ 'x' │
└─────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

ใครอยากได้โค้ดเต็มๆ ไป Run ในเครื่อง ก็ใช้จากลิงก์นี้ได้เลยครับ

และในที่สุดผมก็ Solve Puzzle นี้สำเร็จซะที

ดู Video อธิบายแต่ละขั้นตอนได้ที่นี่ครับ

สำหรับใครที่ชื่นชอบบทความนี้ อย่าลืมกดติดตาม Medium: KBTG Life เรามีสาระความรู้และเรื่องราวดีๆ จากชาว KBTG พร้อมเสิร์ฟให้ที่นี่ที่แรก

วิธีเขียนโปรแกรมเพื่อ Solve Puzzles

ขั้นตอนการเขียนโปรแกรมเพื่อ Solve Puzzle

1. Identify State

2. Identify Actions และตัวเลือกทั้งหมดของ Action

3. Apply Action

4. Try All Actions and Recursive

5. เขียน Function เพื่อแสดงผลลัพธ์

Written by Chaowlert Chaisrichalermpol