การบ้านมีทั้งสิ้น 2 ข้อ

===== เกม o-x =====

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

<file>
 o |   | x
---+---+---
   | x |
---+---+---
 o |   |
</file>

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

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

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

===== sudoku =====

**sudoku** เป็นเกมกระดานที่เล่นคนเดียว โดยผู้เล่นจะต้องใส่ตัวเลขตั้งแต่ 1 - 9 ลงไปในตารางให้ตรงตามเงื่อนไขของเกม อ่านรายละเอียดได้จาก[[http://th.wikipedia.org/wiki/ซูโดะกุ|บทความในวิกิพีเดีย]]

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

<file>
1|2||3|4
-+-++-+-
3|4||1|2
=+=++=+=
2|3||4|1
-+-++-+-
4|1||2|3
</file>

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

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