Help get this topic noticed by sharing it on Twitter, Facebook, or email.

How do I pass along a question about "Algorithms in a Nutshell" to any of the authors? I can't find a link on the blog page(s) to do so.

I have a specific question regarding this book's discussion of the 15-puzzle (and an unsolvable initial state). How do I pass along my question to one or more of the authors?
1 person has
this question
+1
Reply
  • Hi Thomas,

    Thanks for your interest in Algorithms in a Nutshell. If you let me know your question I'll work on passing it along to one of the authors to see if they can get an answer for you.

    Kind regards,
    Paul Fichera
    Customer Service Representative
    O'Reilly Media
  • (some HTML allowed)
    How does this make you feel?
    Add Image
    I'm

    e.g. sad, anxious, confused, frustrated kidding, amused, unsure, silly indifferent, undecided, unconcerned happy, confident, thankful, excited

  • I’m curious
    Okay, then here is my question:

    In "Algorithms in a Nutshell", Chapter 7, page 202, there is shown a "more complicated initial board" for which the A*SEARCH method ran out of memory before finding a solution.

    My question is, was this initial board created (a) randomly or (b) by shuffling the tiles of a solved 15-puzzle to produce the board shown?

    I ask this because the 15-puzzle is known to have a "parity" of 2; in other words, all possible permutations of the 15 tiles plus the vacant space can be divided into two sets. From any initial board configuration, only those which have the same parity (are in the same set) are reachable at all. For example, if you take a solved puzzle and (through partial disassembly) swap two adjacent tiles, the parity of the arrangement changes, and the puzzle can no longer be solved without disassembling it again. If the answer to my question above is (a), then you had a 50% chance of presenting an initial configuration of the wrong (unsolvable) parity. If the answer is (b), then the parity could not have changed, and the original statement in the book stands.

    As another example, the original Rubik's cube has a parity of 12. If you ever disassemble your Rubik's cube, always reassemble it solved. And don't swap stickers on the faces.

    I ran into a similar situation in writing a Prolog program to solve the triangular 15-holes-and-14-pegs puzzle you sometimes see on the tables at Cracker Barrel restaurants. The "genius" solution has the final peg (or golf tee) in the same hole that was initially vacant. This is solvable if the initial hole is any of the exterior 12 holes... but not if it's one of the three interior holes.

    Just wondering....

    Thomas W. Rackers, Ph.D.
    Montgomery Village, MD, USA
  • (some HTML allowed)
    How does this make you feel?
    Add Image
    I'm

    e.g. sad, anxious, confused, frustrated kidding, amused, unsure, silly indifferent, undecided, unconcerned happy, confident, thankful, excited

  • Hello Thomas,

    I'll pass your question on to one of the authors of Algorithms in a Nutshell. Once I hear back I'll be in touch.

    Kind regards,
    Paul Fichera
    Customer Service Representative
    O'Reilly Media
  • (some HTML allowed)
    How does this make you feel?
    Add Image
    I'm

    e.g. sad, anxious, confused, frustrated kidding, amused, unsure, silly indifferent, undecided, unconcerned happy, confident, thankful, excited