Artificial Intelligence Problems and Their Solutions

This book lends insight into solving some well-known AI problems using the most efficient problem-solving methods by humans and computers. The book discusses the importance of developing critical-thinking methods and skills, and develops a consistent approach toward each problem. This book assembles in one place a set of interesting and challenging AI–type problems that students regularly encounter in computer science, mathematics, and AI courses. These problems are not new, and students from all backgrounds can benefit from the kind of deductive thinking that goes into solving them. The book is especially useful as a companion to any course in computer science or mathematics where there are interesting problems to solve.Features:•Addresses AI and problem-solving from different perspectives •Covers classic AI problems such as Sudoku, Map Coloring, Twelve Coins, Red Donkey, Cryptarithms, Monte Carlo Methods, Rubik's Cube, Missionaries/Cannibals, Knight's Tour, Monty Hall, and more•Includes a companion disc with source code, solutions, figures, and more•Offers playability sites where students can exercise the process of developing their solutions•Describes problem-solving methods that might be applied to a variety of situations eBook Customers: Companion files are available for downloading with order number/proof of purchase by writing to the publisher at info@merclearning.com. Contents......Page 3 Preface......Page 11 Figures & Tables......Page 13 1 Introduction......Page 21 --- Problem Solving & Traditional AI Problems......Page 27 POLyA’s five sTePs fOr PrOBLem sOLvinG......Page 28 PrOBLem-sOLvinG Techniques......Page 33 humAn WinDOW......Page 44 humAn WinDOW criTeriA & rAnkinG Of sOLuTiOns......Page 47 cLAssificATiOn......Page 50 Refs......Page 52 3 Missionaries & Cannibals......Page 53 chOOsinG An APPrOPriATe rePresenTATiOn......Page 55 sOLuTiOn......Page 58 humAn PrOBLem sOLvinG......Page 60 humAn WinDOW AnALysis Of sOLuTiOns......Page 65 BesT mAchine sOLuTiOn......Page 70 reLATeD PrOBLems......Page 71 PLAyABLe PrOGrAm......Page 72 references......Page 73 4 The 12 Coins......Page 74 sOLvinG A smALLer PrOBLem......Page 75 sOLuTiOn......Page 79 humAn PrOBLem sOLvinG......Page 85 humAn WinDOW AnALysis Of sOLuTiOns......Page 86 BesT mAchine sOLuTiOn......Page 91 references......Page 92 5 Cryptarithms......Page 93 PrOBLem-sOLvinG Techniques......Page 94 sOLuTiOn......Page 95 humAn PrOBLem sOLvinG......Page 107 humAn WinDOW AnALysis Of sOLuTiOns......Page 108 BesT mAchine sOLuTiOn......Page 112 reLATeD PrOBLems......Page 113 PLAyABLe PrOGrAm......Page 114 references......Page 116 6 Red Donkey Puzzle......Page 117 sOLuTiOn......Page 119 humAn PrOBLem sOLvinG......Page 123 humAn WinDOW AnALysis Of sOLuTiOns......Page 124 BesT mAchine sOLuTiOn......Page 130 PLAyABLe PrOGrAm......Page 131 references......Page 132 7 The 15 Puzzle......Page 133 PrOBLem-sOLvinG Techniques......Page 134 sOLuTiOn......Page 135 humAn WinDOW AnALysis Of sOLuTiOns......Page 148 BesT mAchine sOLuTiOn......Page 152 reLATeD PrOBLems......Page 154 references......Page 155 8 Knight's Tour......Page 157 PrOBLem-sOLvinG Techniques......Page 158 sOLuTiOn......Page 159 humAn WinDOW AnALysis Of sOLuTiOns......Page 168 BesT mAchine sOLuTiOn......Page 174 PLAyABLe PrOGrAm......Page 176 references......Page 177 9 Mastermind......Page 178 PrOBLem-sOLvinG Techniques......Page 179 sOLuTiOn......Page 180 humAn PrOBLem sOLvinG......Page 189 humAn WinDOW AnALysis Of sOLuTiOns......Page 190 BesT mAchine sOLuTiOn......Page 191 PLAyABLe PrOGrAm......Page 192 references......Page 193 10 Monty Hall Problem......Page 194 PrOBLem-sOLvinG Techniques......Page 195 humAn PrOBLem sOLvinG......Page 197 reLATeD PrOBLems......Page 198 references......Page 199 11 Rubik Cube......Page 200 PrOBLem-sOLvinG Techniques......Page 201 sOLuTiOn......Page 202 humAn PrOBLem sOLvinG......Page 220 humAn WinDOW AnALysis Of sOLuTiOns......Page 221 BesT mAchine sOLuTiOn......Page 227 PLAyABLe PrOGrAm......Page 229 references......Page 230 The TrADiTiOnAL PrOBLem......Page 232 APPLicATiOns in Diverse AreAs......Page 235 references......Page 238 --- Computer Solutions......Page 240 13 Sudoku......Page 241 mAThemATicAL AnALysis......Page 244 PrOBLem sOLvinG Techniques AnD sTrATeGies......Page 249 A reAL Life exPerimenT......Page 254 ALGOriThms fOr cOmPuTer sOLuTiOns......Page 258 humAn WinDOW AnALysis Of sOLuTiOns......Page 259 PLAyABLe OnLine......Page 268 references......Page 269 14 Map Coloring & Chromatic Number......Page 271 iLLusTrATinG The TheOrem......Page 273 eArLy ATTemPTs AT PrOOf......Page 275 summAry Of evenTs ThAT LeD TO The DefiniTiOn AnD sOLuTiOn TO The fOur cOLOr PrOBLem......Page 278 sAmPLe Of cODe frOm The PrOOf......Page 280 references......Page 282 15 Cryptography......Page 283 symmeTric key encryPTiOn......Page 285 PuBLic key encryPTiOn......Page 288 rsA encryPTiOn......Page 290 issues reGArDinG rsA cryPTOGrAPhic sysTems......Page 293 references......Page 296 16 Random Walks on Graphs & Monte Carlo Methods......Page 298 TheOreTicAL APPLicATiOns......Page 301 random Walks on Graphs......Page 303 mArkOv chAins AnD mOnTe cArLO meThODs......Page 306 references......Page 307 --- Smaller Problems & Theory......Page 309 cArDs/cOins in The DArk......Page 310 Ten PirATes AnD Their GOLD......Page 313 hALmOs’s hAnDshAke PrOBLem......Page 317 rAnDOm AirLine seATs PrOBLem......Page 325 The BirThDAy PrOBLem......Page 328 neWer ArTificiAL inTeLLiGence PrOBLem sOLvinG Techniques......Page 330 references......Page 335 humAn WinDOW sTuDy......Page 338 LessOns LeArneD......Page 339 reTrOsPecTive, cOncLusiOns, AnD fuTure WOrk......Page 346 suPPLemenTAL references......Page 347 cOmPOsiTe PrOBLem PLAyABiLiTy siTes......Page 349 Companion Disc......Page 351 Index......Page 353 This book lends insight into solving some well-known AI problems using the most efficient problem-solving methods by humans and computers. The book discusses the importance of developing critical-thinking methods and skills, and develops a consistent approach toward each problem. This book assembles in one place a set of interesting and challenging AItype problems that students regularly encounter in computer science, mathematics, and AI courses. These problems are not new, and students from all backgrounds can benefit from the kind of deductive thinking that goes into solving them. The book is especially useful as a companion to any course in computer science or mathematics where there are interesting problems to solve. Addresses AI and problem-solving from different perspectives Covers classic AI problems such as Sudoku, Map Coloring, Twelve Coins, Red Donkey, Cryptarithms, Monte Carlo Methods, Rubiks Cube, Missionaries/Cannibals, Knights Tour, Monty Hall, and more Includes a companion disc with source code, solutions, figures, and more Offers playability sites where students can exercise the process of developing their solutions Describes problem-solving methods that might be applied to a variety of situations eBook Companion files are available for downloading with order number/proof of purchase by writing to the publisher at info@merclearning.com. This book lends insight into solving some well-known AI problems using the most efficient methods by humans and computers. The book discusses the importance of developing critical-thinking methods and skills, and develops a consistent approach toward each problem: 1) a precise description of a well-known AI problem coupled with an effective graphical representation; 2) discussion of possible approaches to solving each problem; 3) identifying and presenting the best known human solution to each problem; 4) evaluation and discussion of the Human Window aspects for the best solution; 5) a playability site where students can exercise the process of developing their solutions, as well as experiencing the best solution; 6) code or pseudo-code implementing the solution algorithm, and 7) academic references for each problem. The book also addresses popular AI problems from different perspectives and covers classic AI problems such as Twelve Coins, Red Donkey, Cryptarithms, Rubik's Cube, Missionaries/Cannibals, Knight's Tour, Monty Hall, and more Offers insight into solving some well-known Al problems using the most efficient methods by humans and computers. This book covers classic Al problems such as Twelve Coins, Red Donkey, Cryptarithms, Rubik's Cube, Missionaries/Cannibals, Knight's Tour, Monty Hall, and more. Discusses the importance of developing critical-thinking methods and skills, and using well-known artificial intelligence problems, develops a consistent approach to solving each problem using methods applicable to a variety of situations.