พิจารณาตารางเกม o-x ที่เล่นค้างอยู่ด้านล่าง

 o |   | x
---+---+---
   | x |
---+---+---
 o |   |

สมมติว่าผู้เล่นเป็นผู้เล่นฝ่าย o และเป็นตาต่อไปที่จะเดิน

เราจะให้ค่าของสถานะของตารางที่ฝ่าย o ชนะมีค่า utility เป็น 1, สถานะที่ o แพ้มี utility เป็น -1 และสถานะที่เสมอมี utility เป็น 0

ให้เขียน minimax tree เพื่อหาทางเดินที่ดีที่สุดของผู้เล่น o ให้ระบุประเภทของโหนดว่าเป็น min node หรือ max node โดยใช้รูปสามเหลี่ยมลักษณะเดียวกับในเอกสาร ให้ utility ที่ได้ในแต่ละโหนดด้วย

sudoku เป็นเกมกระดานที่เล่นคนเดียว โดยผู้เล่นจะต้องใส่ตัวเลขตั้งแต่ 1 - 9 ลงไปในตารางให้ตรงตามเงื่อนไขของเกม อ่านรายละเอียดได้จากบทความในวิกิพีเดีย

พิจารณาเกม sudoku ขนาด 4 x 4 โดยในตารางดังกล่าวจะให้ใส่เลขตั้งแต่ 1 - 4 โดยมีตารางแบ่งเป็น 4 กลุ่มย่อยขนาด 2 x 2 (ตัวอย่างตารางที่เติมเต็มแล้วเป็นดังรูปด้านล่าง)

1|2||3|4
-+-++-+-
3|4||1|2
=+=++=+=
2|3||4|1
-+-++-+-
4|1||2|3

ให้ตาราง sudoku ที่ยังเติมไม่เต็ม ให้พิจารณาปัญหาดังกล่าวเป็นปัญหาการ search

• ให้อธิบายคร่าว ๆ ว่าจะใช้วิธีการ search ในการหาทางเติมตารางให้เต็มได้อย่างไร
• branching factor b เป็นเท่าใด
• ความลึกไปยังคำตอบ m เป็นเท่าใด
• ให้ยกตัวอย่างกรณีที่วิธีการลดทอนความซับซ้อนในการค้นหาที่เรียนในบท CSP สามารถนำมาใช้ได้ในปัญหานี้ (วิธีการที่ยกมาอาจเป็น forward checking หรือ arc consistency หรืออื่น ๆ ก็ได้) ให้ยกตัวอย่างให้ชัดเจน