Knights Tour Problem in Python

การเดินของม้าในหมากรุกหรือที่เรารู้จักกันในชื่อ Knight's Tour Problem เป็นปริศนาทางคณิตศาสตร์ที่แสดงถึงการเดินของม้าในเกมหมากรุกบนกระดานขนาด N x N เพื่อให้ม้านั้นเยือนทุกช่องบนกระดานหมากรุกพอดีเพียงครั้งเดียวและไม่ซ้ำตำแหน่งเดิม

Algorithm ที่ใช้แก้ปัญหา Knight's Tour นั้นมีหลายประเภท แต่อัลกอริทึมทั่วไปที่นิยมใช้กันคือ Backtracking algorithm, Warnsdorff's Rule algorithm, และ Divide and conquer algorithm. ในบทความนี้ ผมขอนำเสนอการใช้ Backtracking เพราะมันเป็นวิธีที่เข้าใจง่ายและสามารถนำไปใช้ได้กับกระดานขนาดใดๆ โดยภาษา Python.

ประการแรก เรามาทำความเข้าใจตัวอย่างโค้ดสำหรับ Backtracking ในการแก้ปัญหานี้:

def is_valid_move(x,y,board):
    if x >= 0 and y >= 0 and x < len(board) and y < len(board) and board[x][y] == -1:
        return True
    return False

def print_solution(n, board):
    for i in range(n):
        for j in range(n):
            print(board[i][j], end=' ')
        print()

def solve_knights_tour(n):
    # สร้างกระดานหมากรุก n x n พร้อมเตรียมค่าให้เป็น -1 ทุกช่อง
    board = [[-1 for i in range(n)] for i in range(n)]
    # กำหนดการเดินของม้าในรูปแบบ x และ y offset
    move_x = [2, 1, -1, -2, -2, -1, 1, 2]
    move_y = [1, 2, 2, 1, -1, -2, -2, -1]

    # ม้าเริ่มต้นที่ช่อง 0,0
    board[0][0] = 0

    # ถ้าหากม้าสามารถเดินครบทุกช่อง เราจะพิมพ์ลำดับการเดิน
    if not solve_util(n, board, 0, 0, 1, move_x, move_y):
        print("Solution does not exist")
    else:
        print_solution(n, board)

def solve_util(n, board, curr_x, curr_y, move_i, move_x, move_y):
    if move_i == n**2:
        return True

    # ลองเดินทุกทิศทางจากการเดินของม้า
    for i in range(8):
        next_x = curr_x + move_x[i]
        next_y = curr_y + move_y[i]
        if is_valid_move(next_x, next_y, board):
            board[next_x][next_y] = move_i
            if solve_util(n, board, next_x, next_y, move_i+1, move_x, move_y):
                return True
            # ถ้าเดินไม่สำเร็จ กลับไปยังเซลก่อนหน้า
            board[next_x][next_y] = -1
    return False

# ทดลองเริ่มเล่นเกมด้วยขนาดกระดาน 8 x 8
solve_knights_tour(8)

ปัญหานี้ใช้ประโยชน์ในโลกจริงได้หลายอย่าง เช่น การวางแผนเส้นทางสำหรับหุ่นยนต์เพื่อทำภารกิจสำรวจพื้นที่หรืออาคาร โดยให้หุ่นยนต์นั้นเดินผ่านทุกจุดในพื้นที่ หรือการคำนวณเส้นทางที่เหมาะสมสำหรับการตรวจสอบบนการผลิตในโรงงานอุตสาหกรรมต่างๆ.

ยังไงก็ตาม การใช้ Backtracking algorithm มีทั้งข้อดีและข้อเสีย:

ข้อดี:

- ง่ายต่อการเข้าใจและปรับใช้

- สามารถหาได้ทุกโซลูชันโดยไม่พลาด

ข้อเสีย:

- ไม่มีประสิทธิภาพสูง เนื่องจากอาจต้องทดลองเดินในทุกๆ ความเป็นไปได้ก่อนจะหาคำตอบที่ถูกต้อง (High time complexity)

- Complexity ของการแก้ปัญหาด้วยวิธีนี้มักเป็น O(n!) ซึ่งนับว่าสูงมากถ้าหากพูดถึงกระดานขนาดใหญ่

สำหรับคุณผู้อ่านที่สนใจในการเขียนโปรแกรมและอยากทำความเข้าใจลึกซึ้งถึงหลักการและทฤษฎีของการแก้ปัญหาด้านคอมพิวเตอร์อย่างนี้ โรงเรียน Expert-Programming-Tutor (EPT) เป็นจุดเริ่มต้นที่ดีที่สุดสำหรับคุณ มาร่วมเรียนรู้และเป็นส่วนหนึ่งของเรา เพื่อเปิดโลกความรู้ด้านการเขียนโค้ดและค้นหาโซลูชันสำหรับปัญหาต่างๆ โดยการเรียนการสอนที่สนุกสนานและตรงกับประสบการณ์จริง.

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