Notes about some of the functions

Discussion:

(too old to reply)

Alexander Smith

2004-03-02 23:00:21 UTC

Hi everyone,

There are a few questions about the assignment that have come up several
times in the lab. Here are the answers, in case you haven't heard them
yet.

makeAssignment():
- If "variable" is unassigned, you must assign it a value. That involves
doing two things:
a) You must insert an entry into the assignment stack at "dlevel".
b) You must set its value in the "solver->variables" array.
- DO NOT loop through the entire assignment stack looking for a previous
assignment to the variable. That would be an O(n) operation. It's trivial
to do it in O(1) instead: just look up the value of the variable in
solver->variables.
- It turns out you can actually write this lab without bothering to use
the return value of makeAssignment(). The return value was a bit of a
hold-over from an old draft of the lab; we didn't notice that it had
become redundant. You should write your solution so that it still gives
the correct return value, though. It only takes about four extra lines of
code to do it.

branch():
- It turns out the call to backtrack() inside branch() (in Figure 5) is
actually redundant, because it will always already have just been called
inside solve(). You can safely remove it.

solve():
- After the line "var = next unassigned variable", you should check to see
what value getNextVar() returned. If it returns 0, it means you have no
more unassigned variables. If this is the case, you should return SAT,
because you have found a satisfying assignment.

Alexander

Moon Sam Dae-Sun

2004-03-04 17:25:46 UTC

Permalink

hi Alexander

I think that you do need the backtrack in Branch becuase i experimented
with this before and didnt get the required value. The backtrack in solve
is a different at a different level than the backtrack in branch. Both
backtracks are needed if u want to backtrack both the deduce assumptions,
and assignments that led to the assumptions.

Well, this is what i found out from my experience, but maybe it is because
of the way that i set up my algorithm

pls reply and tell me if im right nor not

thx
sam

Post by Alexander Smith
Hi everyone,
There are a few questions about the assignment that have come up several
times in the lab. Here are the answers, in case you haven't heard them
yet.
- If "variable" is unassigned, you must assign it a value. That involves
a) You must insert an entry into the assignment stack at "dlevel".
b) You must set its value in the "solver->variables" array.
- DO NOT loop through the entire assignment stack looking for a previous
assignment to the variable. That would be an O(n) operation. It's trivial
to do it in O(1) instead: just look up the value of the variable in
solver->variables.
- It turns out you can actually write this lab without bothering to use
the return value of makeAssignment(). The return value was a bit of a
hold-over from an old draft of the lab; we didn't notice that it had
become redundant. You should write your solution so that it still gives
the correct return value, though. It only takes about four extra lines of
code to do it.
- It turns out the call to backtrack() inside branch() (in Figure 5) is
actually redundant, because it will always already have just been called
inside solve(). You can safely remove it.
- After the line "var = next unassigned variable", you should check to see
what value getNextVar() returned. If it returns 0, it means you have no
more unassigned variables. If this is the case, you should return SAT,
because you have found a satisfying assignment.
Alexander

Greg Sinclair

2004-03-04 19:34:01 UTC

Permalink

Hey all,

I agree with Moon, you need to put backtrack in branch() only.

-Greg

Post by Moon Sam Dae-Sun
hi Alexander
I think that you do need the backtrack in Branch becuase i experimented
with this before and didnt get the required value. The backtrack in solve
is a different at a different level than the backtrack in branch. Both
backtracks are needed if u want to backtrack both the deduce assumptions,
and assignments that led to the assumptions.
Well, this is what i found out from my experience, but maybe it is because
of the way that i set up my algorithm
pls reply and tell me if im right nor not
thx
sam

Fo Sing Renno

2004-03-04 21:03:00 UTC

Permalink

I have it in solve() only and it works fine.

Post by Greg Sinclair
Hey all,
I agree with Moon, you need to put backtrack in branch() only.
-Greg

trivial

Post by Moon Sam Dae-Sun

Post by Alexander Smith
to do it in O(1) instead: just look up the value of the variable in
solver->variables.
- It turns out you can actually write this lab without bothering to use
the return value of makeAssignment(). The return value was a bit of a
hold-over from an old draft of the lab; we didn't notice that it had
become redundant. You should write your solution so that it still gives
the correct return value, though. It only takes about four extra lines

Post by Moon Sam Dae-Sun

Post by Alexander Smith
code to do it.
- It turns out the call to backtrack() inside branch() (in Figure 5) is
actually redundant, because it will always already have just been called
inside solve(). You can safely remove it.
- After the line "var = next unassigned variable", you should check to

see

Post by Moon Sam Dae-Sun

Post by Alexander Smith
what value getNextVar() returned. If it returns 0, it means you have no
more unassigned variables. If this is the case, you should return SAT,
because you have found a satisfying assignment.
Alexander

Greg Sinclair

2004-03-04 21:41:18 UTC

Permalink

Actually, either one works.

-Greg

Post by Fo Sing Renno
I have it in solve() only and it works fine.

Post by Greg Sinclair
Hey all,
I agree with Moon, you need to put backtrack in branch() only.
-Greg

Post by Moon Sam Dae-Sun
hi Alexander
I think that you do need the backtrack in Branch becuase i

experimented