Backtracking ใน Turbo Prolog

 สมมุติปัญหาต้องการจับคู่ นักเรียนมาแข่งขันตอบปัญหาโดยที่จะต้องมีอายุเท่ากันตัวอย่าง ค่าความจริง (facts) ของนักเรียนในห้อง

domains
          learner = symbol
           age = integer
predicates
           student(learner, age)
clauses
            student(wichai, 21).
            student(somsak, 19).
            student(somsri, 21).
            student(somchai, 21).

 ให้จับคู่นักเรียน อายุ 21 ปี มาแข่งขันกัน 2 รอบ กำหนดเป้าประสงค์ (goal) แบบผสม (compound goal) ซึ่งจะมีเป้าประสงค์ย่อย (subgoals) หลาย ๆ เป้าประสงค์ดังนี้

student(Who1, 21) and
student(Who2, 21) and
Who1 <> Who2.

 โตยที่ Who1 และ Who2 เป็นคนละคนกัน การทำงานของ Turbo Prolog จะหาคำตอบจากเป้าประสงค์ย่อย (subgoal) อันแรก และจะหาจากเป้าประสงค์ย่อยอื่นต่อไปก็ต่อเมื่อ เจอเป้าประสงค์ย่อยแรกแล้ว จากตัวอย่าง Who1 คือ wichai Turbo Prolog จะหาเป้าประสงค์ย่อยอื่นต่อไป คือ student(Who2, 21) จะได้ Who2 มีค่าเป็น wichai ด้วย ลำดับต่อมาไปที่เป้าประสงค์ Who1 <> Who2 แต่จากที่หาได้มาจะได้ Who1 และ Who2 มีค่าเป็น wichai ทั้งคู่ ทำให้เป้าประสงค์ย่อยนี้เป็นเท็จ Turbo Prolog จะย้อนรอยกลับไปเริ่มค้นหาใหม่ (Backtrack) โดยย้อนกลับมาที่ เป้าประสงค์ย่อยตัวที่ 2 คือ student(Who2, 21) จะได้ Who2 มีค่าเป็น somsri ทำให้เป้าประสงค์ย่อยตัวที่ 3 เป็นจริง เพราะค่าของ Who1 และ Who2 ไม่ใช่คนเดียวกัน ทำให้เป้าประสงค์ทั้งหมดเป็นจริง (satisfy)
 แต่ Turbo Prolog จะต้องหาคำตอบที่เป็นไปได้ทั้งหมดตามเป้าประสงค์ ดังนั้นมันจะกระโดดกลับไป หรือย้อนรอยไปที่เป้าประสงค์ก่อนหน้านั้น คือ somchai แลยังคงสอดคล้องกับเป้าประสงค์ย่อยที่ 3 ที่ wichai และ somchai ไม่ใช่คนเดียวกัน
 เพื่อหาคำตอบอื่น ๆ อีก Turbo Prolog จะย้อนรอยกลับไปที่ เป้าประสงค์ย่อยที่ 2 อีก แต่ความเป็นไปได้ทั้งหมดเป้าประสงค์ย่อยที่ 2 ไม่มีแล้ว มันก็จะย้อนรอยกลับไปที่ เป้าประสงค์ย่อยที่ 1 อีก คือ Who1 มีค่าเป็น somsri และเป้าประสงค์ย่อยที่ 2 คือ Who2 มีค่าเป็นwichai ทำให้เป้าประสงค์ย่อยที่ 3 เป็นจริง คำตอบสุดท้าย Who1 และ Who2 มีค่าเป็น somchai เป้าประสงค์ย่อยสุดท้าย เป็นเท็จ Turbo Prolog จะย้อนรอยกลับไปที่เป้าประสงค์ย่อยที่ 2 แต่ไม่มีคำตอบที่เป็นไปได้ Turbo Prolog ก็จะย้อนรอยกลับไปที่เป้าประสงค์ย่อยที่ 1 แต่ไม่มีคำตอบที่เป็นไปได้อีกเช่นกัน การ ทำงานของโปรแกรมจะหยุด (Terminate) คำตอบทั้งหมดจะได้

Who1 = wichai ,Who2 = somsri
Who1 = wichai ,Who2 = somchai
Who1 = somsri ,Who2 = wichai
Who1 = somsri ,Who2 = somchai
Who1 = somchai ,Who2 = wichai
Who1 = somchai ,Who2 = somsri

Acknowledgment

Turbo Prolog is a registered trademark of Borland International, Inc. California 95066 USA.