I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used.
choose (x from S: P(x)) is defined as follows:

  • Return some element x of S such that P(x) halts with a value other than False, if there is one.
  • If there is no such element, then choose will:
    • Halt and return False if it can be determined that, for all elements x of S, P(x) is not satisfied. This will happen if S is finite and there is a procedure for checking P that always halts. It may also happen, even if S is infinite, if there is some way, short of checking all the elements, to determine that no elements that satisfy P exist.
    • Fail to halt if there is no mechanism for determining that no elements of S that satisfy P exist. This may happen either because S is infinite or because there is no algorithm, guaranteed to halt on all inputs, that checks for P and returns False when necessary.

The problem and it's solution from the book

How does choose "picks one with the property that, once it has been appended to position-list, solve-15 can continue and find a solution"?, do we code that in, or do we accept any legal position ? if the latter is true, what's to guarantee that it will ever arrive to a solution, what if it gets stuck in loop where it does a legal action and then undoes it, thus getting stuck.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.