Ways to solve a puzzle in C++ -- variety

[Alf P. Steinbach]

I'm writing a little piece on pointers, to be "bundled" with my attempted
correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at
least think about that again), and while thinking of good examples I came up
with the idea of solving the puzzle explained in code below, with the solver
optimized so that a state is never analysed more than once.

However, I soon realized that this could be done most naturally (for me, at
least) _without_ using any pointers -- but perhaps that's not so for you?

So now I'm interested in what's _your_ "natural" way to do this.

Please don't look at the old tutorial first, which has a similar example,
because that could influence the way you choose to tackle the problem.

I'm thinking that you can just post working code or URLs to working code here
in this thread, and to be able to compare solutions, please use the below spec
unchanged except perhaps for renaming, indentation and such, and fixing bugs,
if any (the spec compiles but I haven't tried it out yet).


namespace nac_puzzle
{
enum RiverSideEnum{ left, right }; // We have a river with a left and right bank.
inline RiverSideEnum opposite( RiverSideEnum side )
{
return RiverSideEnum( 1 - side );
}

enum PersonKindEnum{ cannibal, nun }; // There are cannibals and nuns, on the right.
inline PersonKindEnum opposite( PersonKindEnum kind )
{
return PersonKindEnum( 1 - kind );
}

enum { nPersonsOfAKind = 3, maxPerTransfer = 2 }; // The boat holds max 2 persons...

class State
{
private:
unsigned myNCannibalsAtLeft;
unsigned myNNunsAtLeft;
RiverSideEnum myBoatPosition;

public:
State(): myNCannibalsAtLeft( 0 ), myNNunsAtLeft( 0 ), myBoatPosition( right ) {}

State( unsigned nCannibalsAtLeft, unsigned nNunsAtLeft, RiverSideEnum aBoatPos )
:
myNCannibalsAtLeft( nCannibalsAtLeft ),
myNNunsAtLeft( nNunsAtLeft ),
myBoatPosition( aBoatPos )
{
assert( 0 <= myNCannibalsAtLeft && myNCannibalsAtLeft <= nPersonsOfAKind );
assert( 0 <= myNNunsAtLeft && myNNunsAtLeft <= nPersonsOfAKind );
assert( myBoatPosition == left || myBoatPosition == right );

assert( !(
n( cannibal, left ) + n( nun, left ) == 0 && boatPosition() == left
) );
assert( !(
n( cannibal, right ) + n( nun, right ) == 0 && boatPosition() == right
) );
}

unsigned n( PersonKindEnum kind, RiverSideEnum side ) const
{
unsigned const nOfKindAtLeft =
(kind == cannibal? myNCannibalsAtLeft : myNNunsAtLeft);
return (side == left? nOfKindAtLeft : nPersonsOfAKind - nOfKindAtLeft );
}

RiverSideEnum boatPosition() const { return myBoatPosition; }
unsigned nCannibalsAtBoat() const { return n( cannibal, boatPosition() ); }
unsigned nNunsAtBoat() const { return n( nun, boatPosition() ); }

bool isSolution() const
{
return
n( cannibal, left ) == nPersonsOfAKind &&
n( nun, left ) == nPersonsOfAKind;
}

bool isCannibalisticOrgy() const
{
return (
n( cannibal, left ) >= n( nun, left ) ||
n( cannibal, right ) >= n( nun, right )
);
}

bool canTransfer( unsigned nCannibals, unsigned nNuns )
{
return
!isCannibalisticOrgy() &&
nCannibals <= nCannibalsAtBoat() &&
nNuns <= nNunsAtBoat() &&
0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer;
}

void transfer( unsigned nCannibals, unsigned nNuns )
{
assert( canTransfer( nCannibals, nNuns ) );

if( myBoatPosition == left )
{
myNCannibalsAtLeft -= nCannibals;
myNNunsAtLeft -= nNuns;
}
else
{
myNCannibalsAtLeft += nCannibals;
myNNunsAtLeft += nNuns;
}
myBoatPosition = opposite( myBoatPosition );
}
}; // class State
} // namespace nac_puzzle

 

[Alf P. Steinbach]

* Alf P. Steinbach:

and fixing bugs, if any (the spec compiles but I haven't tried it out yet).

Of course the criterion for cannibals going amok should be that there are
_more_ of them on one side, otherwise one wouldn't even get started. I.e. the
comparision operator should be ">", not ">=" as I wrote... Grr. ;-)

 

[Alf P. Steinbach]

* Alf P. Steinbach:

* Alf P. Steinbach:

Of course the criterion for cannibals going amok should be that there are
_more_ of them on one side, otherwise one wouldn't even get started. I.e. the
comparision operator should be ">", not ">=" as I wrote... Grr. ;-)

bool isCannibalisticOrgy() const
{
return (
n( cannibal, left ) > n( nun, left ) && n( nun, left ) > 0 ||
n( cannibal, right ) > n( nun, right ) && n( nun, right ) > 0
);
}

 

[int2str]

So now I'm interested in what's _your_ "natural" way to do this.

Are you talking about our way of doing this state class, or the solver?

bool canTransfer( unsigned nCannibals, unsigned nNuns )
{
return
!isCannibalisticOrgy() &&
nCannibals <= nCannibalsAtBoat() &&
nNuns <= nNunsAtBoat() &&
0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer;
}

canTransfer() dosn't check how many n/c are left on that side...

Cheers,
Andre

 

[Alf P. Steinbach]

* (e-mail address removed):

Are you talking about our way of doing this state class, or the solver?

I meant the solver, unless there's a radically different way of doing the
state class (not counting just a pure value class) ;-)

If anyone's interested I could post my own solver code; it's not that long.

But it's essentially the same as the one I presented in the tutorial (for a
similar problem), and I think that could influence how people choose to do
this, the angle of attack, so to speak.

canTransfer() dosn't check how many n/c are left on that side...

Yep. You're allowed to get to the state where the cannibals feast, but you're
not allowed to derive a new state from that state. I think in the original
formulation there was a big brush fire on the right hand side of the river,
which was the reason the nuns are trying -- with their lives at stake, given
the cannibals' diet -- to save the poor cannibals.

 

[int2str]

Yep. You're allowed to get to the state where the cannibals feast, but you're
not allowed to derive a new state from that state.

But, it looks like you're allowed a state where you've shipped more
people than actually exist .

Like the old saying goes, "if there's 3 people in a room, and 4
leave...."

Cheers,
Andre

 

[Alf P. Steinbach]

* (e-mail address removed):

But, it looks like you're allowed a state where you've shipped more
people than actually exist .

Like the old saying goes, "if there's 3 people in a room, and 4
leave...."

Well, here's that code, again:

bool canTransfer( unsigned nCannibals, unsigned nNuns )
{
return
!isCannibalisticOrgy() &&
nCannibals <= nCannibalsAtBoat() &&
nNuns <= nNunsAtBoat() &&
0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer;
}

After the line with 'return', the first line checks that there's no gourmet
h-meat dinner going on (can't proceed from that state), the second line, that
the number of cannibals to transfer is actually less than or equal to the
number of cannbibals on that side -- and so on.

Of course, the litmus test is that it works. From my own experience, to check
that a solver actually does work it should display the series of states that
leads to the solution. Otherwise it can seemingly work, but not actually, so
to anyone doing this, I recommend displaying the solution steps.

 

[int2str]

* (e-mail address removed):
Of course, the litmus test is that it works. From my own experience, to check
that a solver actually does work it should display the series of states that
leads to the solution. Otherwise it can seemingly work, but not actually, so
to anyone doing this, I recommend displaying the solution steps.

Yes, I agree.

Alright, here we go... It's undoubtably not the most efficient, nor
elegant solution, but I'd like to hear some comments on it anyway. and
to the best of my knowledge, it seems to be working.

Link:
http://www.eisenbach.com/~andre/posted/nac.cpp.txt

Cheers,
Andre

 

[int2str]

Link:
http://www.eisenbach.com/~andre/posted/nac.cpp.txt

I've updated the code slightly (only cleanups).
The current version (see top) is "1.03".

Cheers,
Andre

 

[Alf P. Steinbach]

* (e-mail address removed):

I've updated the code slightly (only cleanups).
The current version (see top) is "1.03".

I see no difference... ?

Comments, I'm not sure. It's a clean implementation, except for the
depth-search cutoff which had me baffled (it starts at 0 and the criterion for
not trying one more level is >=, which allows a 12-step solution to be found
for cutoff 10). What did you intend to use from <algorithm>? As it is I
can't see that anything's used from <algorithm>.

It would be interesting if someone had some very different kind of solution,
e.g., one using pointers (!); anyway, for comparision, here's mine:
<url: http://home.no.net/alfps/misc/nuns_and_cannibals/solveit.cpp.txt>.

 

[int2str]

I see no difference... ?

You must have missed the earlier revision(s). Syntactical cleanups
only.

Comments, I'm not sure. It's a clean implementation, except for the
depth-search cutoff which had me baffled (it starts at 0 and the criterion for
not trying one more level is >=, which allows a 12-step solution to be found
for cutoff 10).

The depth cutoff was only there to prevent runaway solutions where the
stats (possibly) repeat over and over again. This is not really an
issue with this "Cannibals and Nuns" problem, but I'm just used to it
from problems where you cannot search to the full depth.

I've removed it for this example though (see below).

What did you intend to use from <algorithm>? As it is I
can't see that anything's used from <algorithm>.

For some strange reason I thought std::min was in algorithm. But I

anyway, for comparision, here's mine:
<url: http://home.no.net/alfps/misc/nuns_and_cannibals/solveit.cpp.txt>.

It's funny, our two solutions both arrive at the same end result after
12 iterations, but take a different route getting there.

Also, I believe my solution is a little "cleaner" (may be not objective
enough to judge though ), but your solution was by a factor of 40
faster than mine! Loops beat recursion again .

However, I got the speed discrepancy down quite a bit by removing the
extra indirection that "GetValidMoves()" caused in my solution.

Here's an updated solution:
http://www.eisenbach.com/~andre/posted/SolverAndre.h

Also, just for fun, here's both solutions in one project:
http://www.eisenbach.com/~andre/posted/nac.tar

To swerve slightly back on topic, what would you think pointers could
be used for in this problem?

Cheers,
Andre

 

[Kai-Uwe Bux]

I'm writing a little piece on pointers, to be "bundled" with my attempted
correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at
least think about that again), and while thinking of good examples I came
up with the idea of solving the puzzle explained in code below, with the
solver optimized so that a state is never analysed more than once.

However, I soon realized that this could be done most naturally (for me,
at
least) _without_ using any pointers -- but perhaps that's not so for
you?

So now I'm interested in what's _your_ "natural" way to do this.

Please don't look at the old tutorial first, which has a similar example,
because that could influence the way you choose to tackle the problem.

I'm thinking that you can just post working code or URLs to working code
here in this thread, and to be able to compare solutions, please use the
below spec unchanged except perhaps for renaming, indentation and such,
and fixing bugs, if any (the spec compiles but I haven't tried it out
yet).

I refuse. The specs make is unnecessarily hard to use standard containers.
Thus, I added a total order and comparison on states:

#include <cassert>
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <stack>

namespace nac_puzzle
{
enum RiverSideEnum{ left, right }; // We have a river with a left and
right bank.
inline RiverSideEnum opposite( RiverSideEnum side )
{
return RiverSideEnum( 1 - side );
}

enum PersonKindEnum{ cannibal, nun }; // There are cannibals and nuns,
on the right.
inline PersonKindEnum opposite( PersonKindEnum kind )
{
return PersonKindEnum( 1 - kind );
}

enum { nPersonsOfAKind = 3, maxPerTransfer = 2 }; // The boat holds max
2 persons...

class State
{
private:
unsigned myNCannibalsAtLeft;
unsigned myNNunsAtLeft;
RiverSideEnum myBoatPosition;

public:
State(): myNCannibalsAtLeft( 0 ), myNNunsAtLeft( 0 ),
myBoatPosition( right ) {}

State( unsigned nCannibalsAtLeft, unsigned nNunsAtLeft, RiverSideEnum
aBoatPos )
:
myNCannibalsAtLeft( nCannibalsAtLeft ),
myNNunsAtLeft( nNunsAtLeft ),
myBoatPosition( aBoatPos )
{
assert( 0 <= myNCannibalsAtLeft && myNCannibalsAtLeft <=
nPersonsOfAKind );
assert( 0 <= myNNunsAtLeft && myNNunsAtLeft <= nPersonsOfAKind );
assert( myBoatPosition == left || myBoatPosition == right );

assert( !(
n( cannibal, left ) + n( nun, left ) == 0 && boatPosition()
== left
) );
assert( !(
n( cannibal, right ) + n( nun, right ) == 0 &&
boatPosition() == right
) );
}

unsigned n( PersonKindEnum kind, RiverSideEnum side ) const
{
unsigned const nOfKindAtLeft =
(kind == cannibal? myNCannibalsAtLeft : myNNunsAtLeft);
return (side == left? nOfKindAtLeft : nPersonsOfAKind -
nOfKindAtLeft );
}

RiverSideEnum boatPosition() const { return myBoatPosition; }
unsigned nCannibalsAtBoat() const { return n( cannibal,
boatPosition() ); }
unsigned nNunsAtBoat() const { return n( nun, boatPosition() ); }

bool isSolution() const
{
return
n( cannibal, left ) == nPersonsOfAKind &&
n( nun, left ) == nPersonsOfAKind;
}

bool isCannibalisticOrgy() const
{
return (
n( cannibal, left ) > n( nun, left ) && n( nun, left ) > 0 ||
n( cannibal, right ) > n( nun, right ) && n( nun, right ) > 0
);
}


bool canTransfer( unsigned nCannibals, unsigned nNuns )
{
return
!isCannibalisticOrgy() &&
nCannibals <= nCannibalsAtBoat() &&
nNuns <= nNunsAtBoat() &&
0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer;
}

void transfer( unsigned nCannibals, unsigned nNuns )
{
assert( canTransfer( nCannibals, nNuns ) );

if( myBoatPosition == left )
{
myNCannibalsAtLeft -= nCannibals;
myNNunsAtLeft -= nNuns;
}
else
{
myNCannibalsAtLeft += nCannibals;
myNNunsAtLeft += nNuns;
}
myBoatPosition = opposite( myBoatPosition );
}

// fixed this:
bool operator< ( State const & other ) const {
if ( this->myNCannibalsAtLeft < other.myNCannibalsAtLeft ) {
return( true );
}
if ( other.myNCannibalsAtLeft < this-> myNCannibalsAtLeft ) {
return( false );
}
if ( this->myNNunsAtLeft < other.myNNunsAtLeft ) {
return( true );
}
if ( other.myNNunsAtLeft < this-> myNNunsAtLeft ) {
return( false );
}
if ( this->myBoatPosition < other.myBoatPosition ) {
return( true );
}
if ( other.myBoatPosition < this-> myBoatPosition ) {
return( false );
}
return( false );
}

bool operator== ( State const & other ) const {
if ( ( this->myNCannibalsAtLeft == other.myNCannibalsAtLeft )
&&
( this->myNNunsAtLeft == other.myNNunsAtLeft )
&&
( this->myBoatPosition == other.myBoatPosition ) ) {
return( true );
}
return( false );
}

bool operator!= ( State const & other ) const {
return( ! ( *this == other ) );
}

}; // class State

} // namespace nac_puzzle


// solver code goes here:
// ======================

// Graph data structure:
// ---------------------
// the Graph is directed so that graph[state].first is a
// predecessor state from which state is obtained by the
// transfer graph[state].second.

typedef nac_puzzle::State Vertex;
typedef std:air< unsigned, unsigned > Move;
typedef std:air< Vertex, Move > DirectedEdge;
typedef std::map< Vertex, DirectedEdge > Graph;


// output support:
// ---------------

namespace std {
std:stream & operator<< ( std:stream & ostr,
Move const & move ) {
ostr << "transfer " << move.first
<< " cannibals and " << move.second << " nuns.";
return( ostr );
}
}

// collecting vertices until a solution state is encountered:
// ----------------------------------------------------------
void solve ( Vertex current_vertex, Graph & graph ) {
if ( current_vertex.isSolution() ) {
throw ( current_vertex );
}
if ( current_vertex.isCannibalisticOrgy() ) {
return;
}
for ( unsigned nPersons = 0;
nPersons <= nac_puzzle::maxPerTransfer;
++ nPersons ) {
for ( unsigned nCannibals = 0;
nCannibals <= nPersons;
++ nCannibals ) {
unsigned nNuns = nPersons - nCannibals;
Move current_move ( nCannibals, nNuns );
if ( current_vertex.canTransfer( current_move.first,
current_move.second ) ) {
Vertex next = current_vertex;
next.transfer( current_move.first, current_move.second );
if ( graph.find( next ) == graph.end() ) {
graph[next] = DirectedEdge( current_vertex, current_move );
solve( next, graph );
}
}
}
}
}


int main ( void ) {
Graph graph;
try {
solve( Vertex(), graph );
std::cout << "Sorry, I did not find a solution.\n";
}
catch ( Vertex solution ) {
std::stack< Move > reverse;
while ( solution != Vertex() ) {
reverse.push( graph[solution].second );
solution = graph[solution].first;
}
std::cout << "Yay, I found a solution.\nPlease, proceed as follows:\n";
while ( ! reverse.empty() ) {
std::cout << " " << reverse.top() << '\n';
reverse.pop();
}
}
}


And now, I am going to have a look at the posted solution.


Best

Kai-Uwe Bux

 

[Alf P. Steinbach]

* Kai-Uwe Bux:

I refuse. The specs make is unnecessarily hard to use standard containers.
Thus, I added a total order and comparison on states:

Yes, but the public interface is suffient to do that in e.g. a wrapper class,
not to mention a derived class.

I think your solution is the most innovative so far, a fresh breath of outside
air! E.g. the way you use 'throw' to break out of a recursively nested call,
to indicate _success_. Also, your loop for generating transfer() arguments is
both more clear and more efficient than mine and Andre Eisenbach's (you avoid
generating (0, 0), we didn't). And using a std::map.

Here's a reworked version of your code so that the spec is left unchanged and
just assumed to be in a header file (the operators could be put in a class
instead of extending the namespace), which I think better shows what's part of
the solver code:

#include "NacPuzzle.h" // nac_puzzle::*

#include <cassert>
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <stack>

// State comparision:
// ------------------

namespace nac_puzzle
{
bool operator< ( State const & lhs, State const & rhs ) {
if ( lhs.n( cannibal, left ) < rhs.n( cannibal, left ) ) {
return( true );
}
if ( rhs.n( cannibal, left ) < lhs. n( cannibal, left ) ) {
return( false );
}
if ( lhs.n( nun, left ) < rhs.n( nun, left ) ) {
return( true );
}
if ( rhs.n( nun, left ) < lhs. n( nun, left ) ) {
return( false );
}
if ( lhs.boatPosition() < rhs.boatPosition() ) {
return( true );
}
if ( rhs.boatPosition() < lhs. boatPosition() ) {
return( false );
}
return( false );
}

bool operator== ( State const & lhs, State const & rhs ) {
if ( ( lhs.n( cannibal, left ) == rhs.n( cannibal, left ) )
&&
( lhs.n( nun, left ) == rhs.n( nun, left ) )
&&
( lhs.boatPosition() == rhs.boatPosition() ) ) {
return( true );
}
return( false );
}

bool operator!= ( State const & lhs, State const & rhs ) {
return( ! ( lhs == rhs ) );
}
} // namespace nac_puzzle


// Graph data structure:
// ---------------------
// the Graph is directed so that graph[state].first is a
// predecessor state from which state is obtained by the
// transfer graph[state].second.

typedef nac_puzzle::State Vertex;
typedef std:air< unsigned, unsigned > Move;
typedef std:air< Vertex, Move > DirectedEdge;
typedef std::map< Vertex, DirectedEdge > Graph;


// output support:
// ---------------

namespace std {
std:stream & operator<< ( std:stream & ostr,
Move const & move ) {
ostr << "transfer " << move.first
<< " cannibals and " << move.second << " nuns.";
return( ostr );
}
}

// collecting vertices until a solution state is encountered:
// ----------------------------------------------------------
void solve ( Vertex current_vertex, Graph & graph ) {
if ( current_vertex.isSolution() ) {
throw ( current_vertex );
}
if ( current_vertex.isCannibalisticOrgy() ) {
return;
}
for ( unsigned nPersons = 0;
nPersons <= nac_puzzle::maxPerTransfer;
++ nPersons ) {
for ( unsigned nCannibals = 0;
nCannibals <= nPersons;
++ nCannibals ) {
unsigned nNuns = nPersons - nCannibals;
Move current_move ( nCannibals, nNuns );
if ( current_vertex.canTransfer( current_move.first,
current_move.second ) ) {
Vertex next = current_vertex;
next.transfer( current_move.first, current_move.second );
if ( graph.find( next ) == graph.end() ) {
graph[next] = DirectedEdge( current_vertex, current_move );
solve( next, graph );
}
}
}
}
}

int main ( void ) {
Graph graph;
try {
solve( Vertex(), graph );
std::cout << "Sorry, I did not find a solution.\n";
}
catch ( Vertex solution ) {
std::stack< Move > reverse;
while ( solution != Vertex() ) {
reverse.push( graph[solution].second );
solution = graph[solution].first;
}
std::cout << "Yay, I found a solution.\nPlease, proceed as follows:\n";
while ( ! reverse.empty() ) {
std::cout << " " << reverse.top() << '\n';
reverse.pop();
}
}
}

And now, I am going to have a look at the posted solution.

As you'll see, while you and Andre Eisenbach have chosen to use recursion in
the algorithm and iteration in the results display, I chose to use iteration
in the algorithm and recursion in the results display... Otherwise your and
Andre's algorithms are pretty much identical, but expressed very differently
in C++. I guess this can rightly be called a multi-paradigm language!

Cheers,

- Alf

 

[Kai-Uwe Bux]

* Kai-Uwe Bux:

Yes, but the public interface is suffient to do that in e.g. a wrapper
class, not to mention a derived class.

You are right. I just didn't understand the interface correctly. Once I saw
your solution, it dawned upon me that there is a way to peek into a state.
I guess I should make it a habit to understand what I read before I start
coding. Oh well.


Thanks

Kai-Uwe Bux

 

[Branimir Maksimovic]

I'm writing a little piece on pointers, to be "bundled" with my attempted
correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at
least think about that again), and while thinking of good examples I came
up
with the idea of solving the puzzle explained in code below, with the
solver
optimized so that a state is never analysed more than once.

However, I soon realized that this could be done most naturally (for me,
at
least) _without_ using any pointers -- but perhaps that's not so for
you?

So now I'm interested in what's _your_ "natural" way to do this.

Well, I couldn't see need for pointers in this case. This is my solution
(though I didn't test it for all cases).

int main(int argc, char *argv[])
{
using namespace nac_puzzle;
assert(!(maxPerTransfer%2));
State s;
while(!s.isSolution())
{
unsigned nc = s.n(cannibal,s.boatPosition());
unsigned nn = s.n(nun,s.boatPosition());
printf("nc:%u\n",nc);
printf("nn:%u\n",nn);
printf("Nuns left:%u Cannibals left:%u\n",
s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle::left));
fflush(stdout);
if(s.boatPosition() == nac_puzzle::left)
{
if(nn==nc)
s.transfer(1,1);
else
s.transfer(1,0);
}
else
{
if((nn>nc && nn-nc == maxPerTransfer) ||
(nn==nc && nn == maxPerTransfer))
{
s.transfer(0,maxPerTransfer);
}
else
{
if(nn==nc && nn+nc == maxPerTransfer)
s.transfer(1,1);
else
s.transfer(nc>maxPerTransfer?maxPerTransfer:nc,0);
}
}
}
printf("Nuns left:%u Cannibals left:%u\n",
s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle::left));
fflush(stdout);
return 0;
}

You should assert for (3,0) (0,3) and boat on the nuns side and for
(1,2) (2,1), I think.

Greetings, Bane.

 

[Branimir Maksimovic]

This is finished version which uses linked list
as required by asignment. This is still not thoroughly
tested, but it should work.
Basically if solution can be found then assert, otherwise,
display.

------- nac_puzzle.h

#include <cassert>

namespace nac_puzzle
{
enum RiverSideEnum{ left, right }; // We have a river with a
left and right bank.
inline RiverSideEnum opposite( RiverSideEnum side )
{
return RiverSideEnum( 1 - side );
}

enum PersonKindEnum{ cannibal, nun }; // There are cannibals and
nuns, on the right.
inline PersonKindEnum opposite( PersonKindEnum kind )
{
return PersonKindEnum( 1 - kind );
}

enum { nPersonsOfAKind = 3, maxPerTransfer = 2 }; // The boat
holds max 2 persons...

class State
{
private:
unsigned myNCannibalsAtLeft;
unsigned myNNunsAtLeft;
RiverSideEnum myBoatPosition;

public:
State(): myNCannibalsAtLeft( 0 ), myNNunsAtLeft( 0 ),
myBoatPosition( right ) {}

State( unsigned nCannibalsAtLeft, unsigned nNunsAtLeft,
RiverSideEnum aBoatPos )
:
myNCannibalsAtLeft( nCannibalsAtLeft ),
myNNunsAtLeft( nNunsAtLeft ),
myBoatPosition( aBoatPos )
{
assert( 0 <= myNCannibalsAtLeft && myNCannibalsAtLeft <=
nPersonsOfAKind );
assert( 0 <= myNNunsAtLeft && myNNunsAtLeft <=
nPersonsOfAKind );
assert( myBoatPosition == left || myBoatPosition == right
);

assert( !(
n( cannibal, left ) + n( nun, left ) == 0 &&
boatPosition() == left
) );
assert( !(
n( cannibal, right ) + n( nun, right ) == 0 &&
boatPosition() == right
) );
}

unsigned n( PersonKindEnum kind, RiverSideEnum side ) const
{
unsigned const nOfKindAtLeft =
(kind == cannibal? myNCannibalsAtLeft : myNNunsAtLeft);
return (side == left? nOfKindAtLeft : nPersonsOfAKind -
nOfKindAtLeft );
}

RiverSideEnum boatPosition() const { return myBoatPosition; }
unsigned nCannibalsAtBoat() const { return n( cannibal,
boatPosition() ); }
unsigned nNunsAtBoat() const { return n( nun,
boatPosition() ); }

bool isSolution() const
{
return
n( cannibal, left ) == nPersonsOfAKind &&
n( nun, left ) == nPersonsOfAKind;
}

bool isCannibalisticOrgy() const
{
return (
n( cannibal, left ) > n( nun, left ) && n( nun, left ) > 0 ||
n( cannibal, right ) > n( nun, right ) && n( nun, right ) > 0
);

}

bool canTransfer( unsigned nCannibals, unsigned nNuns )
{
return
!isCannibalisticOrgy() &&
nCannibals <= nCannibalsAtBoat() &&
nNuns <= nNunsAtBoat() &&
0 < (nCannibals + nNuns) && (nCannibals + nNuns) <=
maxPerTransfer;
}

void transfer( unsigned nCannibals, unsigned nNuns )
{
assert( canTransfer( nCannibals, nNuns ) );

if( myBoatPosition == left )
{
myNCannibalsAtLeft -= nCannibals;
myNNunsAtLeft -= nNuns;
}
else
{
myNCannibalsAtLeft += nCannibals;
myNNunsAtLeft += nNuns;
}
myBoatPosition = opposite( myBoatPosition );
}
}; // class State

} // namespace nac_puzzle

------ end


------ nac_puzzle.cpp

#include <cstdio>
#include <algorithm>
#include <list>
#include "nac_puzzle.h"

using namespace std;
using namespace nac_puzzle;

struct print_list{

void operator()(const State& s)const
{
printf("Nuns left:%u Cannibals left:%u"
"\tNuns right:%u Cannibals right%u"
"\tBoat position:%s\n",
s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle::left),

s.n(nun,nac_puzzle::right),s.n(cannibal,nac_puzzle::right),
s.boatPosition() == nac_puzzle::left?"left":"right"
);
fflush(stdout);
}

};

int main(int argc, char *argv[])
{
assert(maxPerTransfer>nPersonsOfAKind/2);
// no solution for such cases at least for me

unsigned max =
maxPerTransfer>=nPersonsOfAKind?nPersonsOfAKind-1:maxPerTransfer;
// this is just to simplify algo

list<State> l;
l.push_back(State());
while(!l.back().isSolution())
{
l.push_back(l.back());
unsigned nc = l.back().n(cannibal,l.back().boatPosition());
unsigned nn = l.back().n(nun,l.back().boatPosition());
if(l.back().boatPosition() == nac_puzzle::left)
{
if(nn==nc)
l.back().transfer(1,1);
else
l.back().transfer(nc>max?nc-max:1,0);
}
else
{
if((nn>nc && nn-nc >= max) ||
(nn==nc && nn <= max))
{
l.back().transfer(0,nn<max?nn:max);
}
else
{
if(nn==nc && nn+nc <= max)
{
l.back().transfer(nc,nn);
}
else
l.back().transfer(nc>max?max:nc,0);
}
}
}

printf("Solution:\n");
for_each(l.begin(),l.end(),print_list());

return 0;

}

------- end

 

[Branimir Maksimovic]

This is finished version which uses linked list
as required by asignment. ....
if(nn==nc)
l.back().transfer(1,1);
else
l.back().transfer(nc>max?nc-max:1,0);

quick fix and I think that's it:

if(nn==nc)
{
if(l.back().n(nun,nac_puzzle::right)>max-1)
l.back().transfer(0,nn);
else
l.back().transfer(1,1);
}

 

[Branimir Maksimovic]

Of course, else stays.

quick fix and I think that's it:

if(nn==nc)
{
if(l.back().n(nun,nac_puzzle::right)>max-1)
l.back().transfer(0,nn);
else
l.back().transfer(1,1);
}

else
l.back().transfer(nc>max?nc-max:1,0);

 

[Old Wolf]

namespace nac_puzzle
{
enum RiverSideEnum{ left, right };
// We have a river with a left and right bank.
inline RiverSideEnum opposite( RiverSideEnum side )
{
return RiverSideEnum( 1 - side );
}

etc.

Can you specify the problem? I've heard of wolf, goat and cabbage
crossing the river, but not nun and cannibal.

 

[int2str]

The problem is layed out in the comments:

// We have a river with a left and right bank.
// There are cannibals and nuns, on the right.
// The boat holds max 2 persons...

The only ommited part is:
"There's a wildfire on the right. The nuns and cannibals need to get to
the left side. If there's more cannibals than nuns on either side of
the river, the cannibals will eat the nuns".

Cheers,
Andre