Vzorove reseni problemu koza,vlk,zeli

koza.c

/* Copyright (c) 2012 Mgr. Simon Toth ([email protected])
 * Licensed under the MIT license: http://www.opensource.org/licenses/mit-license.php
 */

#include <stdio.h>

#define STATE_BAD 1
#define STATE_FINAL 2

/** \brief Kodovaci funkce pro zakodovani expandovaneho stavu do unikatniho cisla
 *
 * Stavu je celkem 16, cislovanych 0..15
 */
unsigned encode(int koza, int vlk, int zeli, int lodka)
{
	return koza | (vlk << 1) | (zeli << 2) | (lodka << 3);
}

/* Tady by jsme spravne nemeli pouzivat globalni promenne,
 * ale predavat jako parametry
 */
const char *stavy[16];
int depth = -1;

void print_sol()
{
	for (int i = 0; i <= depth; i++)
		printf("%s\n",stavy[i]);
	printf("##################\n");
}


/** \brief Prohledavaci rekurzivni funkce
 *
 * Z kazdeho stavu se pokusime prozkoumat vsechny mozne varianty:
 * - prevez kozu
 * - prevez vlka
 * - prevez zeli
 * - prevez prazdnou lodku
 *
 * Testy korektnosti stavu jsou uvedene na zacatku funkce.
 * U slozitejsich testu muze byt vhodnejsi vyclenit do
 * samostatne funkce a testovat pred skokem na dalsi stav,
 * napr. if (koza == lodka && is_ok_state(....))
 */
int hledej(int koza, int vlk, int zeli, int lodka, unsigned *visited)
{
	/* stav je spatny, pokud uz byl navstiven */
	if (*visited & (1 << encode(koza,vlk,zeli,lodka))) return STATE_BAD;

	/* vlk sezere kozu pokud neni pod dozorem */
	if (vlk == koza && lodka != vlk) return STATE_BAD;

	/* koza sezere zeli pokud neni pod dozorem */
	if (koza == zeli && lodka != koza) return STATE_BAD;

	/* finalni stav - vsechny zvirata jsou na druhem brehu */
	if (!koza && !vlk && !zeli && !lodka) return STATE_FINAL;

	/* oznacime tento stav za navstiveny */
	*visited |= (1 << encode(koza,vlk,zeli,lodka));

	/* zvetsime hloubku po ucely zaznamu reseni */
	depth++;

	/* pokus o prevezeni kozy, koza musi byt na stejnem brehu jako lodka */
	if (koza == lodka)
	{
		stavy[depth] = "prevazim kozu"; /* zaznam reseni */
		/* pokud nam hledej vrati STATE_FINAL, vypiseme reseni */
		if (hledej(!koza,vlk,zeli,!lodka,visited) == STATE_FINAL) print_sol();
	}

	/* to same pro vlka */
	if (vlk == lodka)
	{
		stavy[depth] = "prevazim vlka";
		if (hledej(koza,!vlk,zeli,!lodka,visited) == STATE_FINAL) print_sol();
	}

	/* to same pro zeli */
	if (zeli == lodka)
	{
		stavy[depth] = "prevazim zeli";
		if (hledej(koza,vlk,!zeli,!lodka,visited) == STATE_FINAL) print_sol();
	}

	/* to same pro prazdnou lodku */
	stavy[depth] = "prevazim lodku";
	if (hledej(koza,vlk,zeli,!lodka,visited) == STATE_FINAL) print_sol();

	depth--; /* vraci se do nadrazene funkce, musime zmensit depth */

	/* a pokud chceme najit reseni ktere prochazeji timto stavem,
	 * ale vychazeji z jine cesty, musime smazat informaci o tom,
	 * ze tento uzel je navstiveny.
	 */
	*visited &= ~(1 << encode(koza,vlk,zeli,lodka));

	/* stav ze ktereho nevede zadna dobra cesta je spatny */
	return STATE_BAD;
}

int main()
{
	unsigned vis;
	/* pocatecni stav, kdy vsechno je na prvnim brehu */
	hledej(1,1,1,1,&vis);

	return 0;
}