8 Queens Problem กับการเขียนโปรแกรมด้วยภาษา Fortran

 

 

ความรู้เบื้องต้นเกี่ยวกับ 8 Queens Problem

8 Queens Problem

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

ปัญหานี้เป็นที่นิยมในหมู่นักเรียนโปรแกรมมิ่งเพราะมันนำเสนอวิธีการแก้ปัญหาที่มีความซับซ้อน และยังสอนให้เราเข้าใจเกี่ยวกับการค้นหาเชิงลึก (backtracking) ซึ่งเป็นเทคนิคที่ใช้ในการแก้ปัญหาที่มีตัวแปรหลายตัว

 

องค์ประกอบของ Algorithm

Algorithm ที่ใช้ในการแก้ปัญหา 8 Queens นี้ใช้แนวทางที่เรียกว่า Backtracking ซึ่งหมายถึงการทดลองวางควีนในตำแหน่งต่าง ๆ และถ้าพบว่าตำแหน่งนั้นไม่สามารถวางได้ ก็จะย้อนกลับไปยังตำแหน่งก่อนหน้าและลองที่ตำแหน่งใหม่

ขั้นตอนการทำงานของ Algorithm

1. เริ่มที่แถวแรกของกระดาน

2. ลองวางควีนในคอลัมน์ที่แตกต่างกันในแต่ละแถว

3. ตรวจสอบว่าตำแหน่งนั้นปลอดภัยหรือไม่

4. หากปลอดภัย ให้วางควีนและไปที่แถวถัดไป

5. ถ้าพบว่าตำแหน่งไม่สามารถวางควีนได้ ก็ให้ย้อนกลับ (backtrack) และลองตำแหน่งใหม่

 

Code ตัวอย่างในภาษา Fortran

นี่คือตัวอย่างโค้ดในภาษา Fortran ที่ใช้ในการแก้ไข 8 Queens Problem

 program EightQueens
    implicit none
    integer, parameter :: N = 8
    integer :: board(N, N)
    integer :: count

    ! Initialize the board
    board = 0
    count = 0

    call solve_NQueens(board, 0, count)

    print *, 'Total Solutions: ', count

contains

    subroutine solve_NQueens(board, row, count)
        integer, intent(inout) :: board(:,:)
        integer, intent(in) :: row
        integer :: col

        if (row >= N) then
            count = count + 1
            call printBoard(board)
            return
        end if

        do col = 1, N
            if (isSafe(board, row, col)) then
                board(row, col) = 1
                call solve_NQueens(board, row+1, count)
                board(row, col) = 0  ! Backtracking
            end if
        end do
    end subroutine solve_NQueens

    logical function isSafe(board, row, col)
        integer, intent(in) :: board(:,:)
        integer, intent(in) :: row, col
        integer :: i

        ! Check the column
        do i = 1, row-1
            if (board(i, col) == 1) return .false.
        end do

        ! Check the diagonal
        do i = 1, row-1
            if (col - i >= 1 .and. board(i, col - i) == 1) return .false.
            if (col + i <= N .and. board(i, col + i) == 1) return .false.
        end do

        isSafe = .true.
    end function isSafe

    subroutine printBoard(board)
        integer, intent(in) :: board(:,:)
        integer :: i, j

        do i = 1, N
            do j = 1, N
                if (board(i, j) == 1) then
                    write(*, "(A)", advance="no") " Q "
                else
                    write(*, "(A)", advance="no") " . "
                end if
            end do
            print *
        end do
        print *
    end subroutine printBoard

end program EightQueens

การวิเคราะห์ Complexity

1. Time Complexity: การวิเคราะห์เวลาของ Algorithm นี้โดยเฉลี่ยจะเป็น O(N!), ซึ่ง N คือจำนวนควีน ในกรณีที่เลวร้ายที่สุดจะต้องทำการตรวจสอบทุกค่าของ N คอลัมน์ 2. Space Complexity: การใช้หน่วยความจำจะเป็น O(N) เนื่องจากต้องรักษาตำแหน่งของควีนแต่ละตัวในแต่ละแถว

 

Use Case ในโลกจริง

การใช้ 8 Queens Problem สามารถเชื่อมโยงไปถึงการวางแผนในทางธุรกิจ เช่น การจัดตารางเวลาการประชุม การจัดการที่นั่งในโรงละครหรือสนามกีฬาให้มีประสิทธิภาพ โดยไม่ให้เกิดความขัดแย้งระหว่างกิจกรรมหรือผู้ใช้งานต่างๆ

 

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

ข้อดี

- ง่ายต่อการเข้าใจและสามารถนำไปประยุกต์ใช้กับปัญหาที่มีความซับซ้อนได้

- ใช้งานได้ง่ายในโปรแกรมที่ต้องการย้อนกลับไปตรวจสอบ (backtrack)

ข้อเสีย

- ความซับซ้อนของเวลาอาจสูงในกรณีที่มีปัญหาขนาดใหญ่

- ประสิทธิภาพอาจลดลงในกรณีที่มีสถานการณ์หลากหลาย ซึ่งอาจใช้งานได้ดีกว่าความเชี่ยวชาญในวิธีการอื่น ๆ

 

สรุป

8 Queens Problem

เป็นตัวอย่างที่ดีของการนำแนวคิด backtracking มาประยุกต์ใช้ในการแก้ปัญหา นอกจากจะช่วยให้เราเข้าใจการพัฒนา Algorithm รวมถึงการเขียนโปรแกรมแล้ว ยังให้เราเห็นภาพรวมของความซับซ้อนและความสามารถในการแก้ปัญหาที่เราเผชิญในชีวิตจริง

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

 

 

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