Pohyb koně po toroidu – C / C++ – Fórum – Programujte.com

Potřebuju poradit, nevím si s tím rady, ale po šachovnici mám toto:

#include <stdio.h>

//nejmensi sachovnice musi byt 5

//nejvetsi sachovnice musi byt 8

//velikost sachovnice

const int BoardSize = 8;



//deklarace typu sachovnice

typedef int tBoard[BoardSize][BoardSize];



//pocet moznych tahu

const int NoOfHorseMoves = 8;



//zmeny souradnic pro jednotlive tahy

const int RowMoveDelta[NoOfHorseMoves] = {-2, -1, +1, +2, +2, +1, -1, -2};

const int ColMoveDelta[NoOfHorseMoves] = {+1, +2, +2, +1, -1, -2, -2, -1};



//deklarace typu pro ulozeni pozice

struct Position

{

	int Row;

	int Col;

};



//inicializace sachovnice

void InitBoard(tBoard& Board)

{

	for(int i = 0; i < BoardSize; i++)

		for(int j = 0; j < BoardSize; j++)

			Board[i][j] = 0;

}



//zobrazeni sachovnice

void PrintBoard(const tBoard& Board)

{

	for(int i = 0; i < BoardSize; i++)

	{

		for(int j = 0; j < BoardSize; j++)

			printf("%4i", Board[i][j]);

		printf("\n");

	}

	printf("\n");

}



//posun kone po sachovnici

Position Move(const Position& Pos, const int MoveIndex)

{

	Position p;

	p.Row = Pos.Row + RowMoveDelta[MoveIndex];

	p.Col = Pos.Col + ColMoveDelta[MoveIndex];

	return p;

}



//test zde je tah platny

//vraci true pokud je tah na pozici Pos na sachovnici dane parametrem Board mozny

bool IsValidMove(const Position& Pos, const tBoard Board)

{

	bool Result = true;

	Result &= 0 <= Pos.Row;

	Result &= Pos.Row < BoardSize;

	Result &= 0 <= Pos.Col;

	Result &= Pos.Col < BoardSize;

	Result &= Board[Pos.Row][Pos.Col] == 0;

	return Result;

}



//rekurzivni hledani reseni problemu metoda backtracking

// Parametry:

// Board -- aktualni sachovnice, 0 znamena volne policko, cislo ruzne od 0 znamena poradi tahu kterym se sem kun dostal

// CurrentPos -- aktualni poloha kone

// MoveNumber -- poradi tahu, ktery provadime

// Funkce vraci true , pokud bylo nalezeno reseni

bool Horse(tBoard& Board, const Position& CurrentPos, 

	  const int MoveNumber)

{

	if (MoveNumber == BoardSize*BoardSize)

		return true;



	for(int i = 0; i < NoOfHorseMoves; i++)

	{

		Position p = Move(CurrentPos, i);

		if (IsValidMove(p, Board))

		{

			Board[p.Row][p.Col] = MoveNumber;

			if (Horse(Board, p, MoveNumber+1))

				return true;

			else

				Board[p.Row][p.Col] = 0;

		}

	}

	return false;

}





void main()

{

	tBoard Board;

	Position InitPos = {0,0};



	InitBoard(Board);

	bool HasSolution = Horse(Board, InitPos, 1);

	if (HasSolution)

	{

		PrintBoard(Board);

	}

	else

	{

		printf("Reseni nenalezeno!\n");

	}

}

zdravím,
pokud jsi chtěl koněm prolézt všechny pole na šachovnici, tak ten kód se zdá být v pořádku. Na co se ale ptáš??? Chceš to samé provést na povrchu toroidu??? Tam by mělo fungovat z principu stejné řešení, jenže... pro větší rozměry šachovnice by ses výsledku při použití backtrackingu nedočkal, takže to bude chtít použít nějakou heuristiku - zkus přemýšlet, zkoušet nebo googlit. Další problém je reprezentace "šachovnice", můžeš zůstat u toho pole, jen si uvědom, že lze skákat kolem dokola toho toroidu, to musíš zohlednit v té fukci IsValidMove(), představ si to třeba na speciálním případě toroidu - toru (1.pád torus, taková ta americká kobliha).

To ian :
Všechno, co jsi říkal vím, problém je, že toroid je v podstatě nekonečný a jak to napsat v algoritmech nevím.

Když si vezmeš šachovnici a spojíš protilehlé strany (šachovnici "sroluješ"), tak dostaneš válec (trubku).
Když ten válec vezmeš za konce a ty zase spojíš, tak dostaneš koblihu :smile1: .
Takže při testu, jestli jde o validní tah (tj. jestli nejsi za okrajem šachovnice) to "pouze" přepočítáš na souřadnice na druhé straně.

A jen tak mimochodem k tomu kód. Když testuješ validnost tahu a ten tah je mimo šachovnici, tak nuluješ jednu buňku pole:
Board[p.Row][p.Col] = 0;
Představ si, že testuješ pozici -1, -1 ...

To liborb :
Nejvíce jsi mi pomohl asi s tady tím:
(tj. jestli nejsi za okrajem šachovnice) to "pouze" přepočítáš na souřadnice na druhé straně.
Stejně ale nevím jak přepočítat za okrajem, ani jak inicializovat toroid. Podle toho, co vím stačí jen upravit v programu IsValidMove, ale jak, to už právě nevím. Čili potřebuju poradit, jak kontrolovat tah po toroidu.

Už jsi blízko. Jak jsem psal, toroid je po rozvinutí zase šachovnice. Takže se inicializuje podobně ne-li stejně.
A přepočítávání ... pokud máš po ruce šachovnici, tak si to zkus ... když by se ti kůň měl dostat mimo šachovnici, tak "skoč" na protilehlý okraj a pokračuj v jeho pohybu.
Tj. pokud máš šachovnici 8x8 a kůň by měl jít na sloupec 9 , tak v toroidu se objeví ve sloupci 1.

Už jsi blízko. Jak jsem psal, toroid je po rozvinutí zase šachovnice. Takže se inicializuje podobně ne-li stejně.
A přepočítávání ... pokud máš po ruce šachovnici, tak si to zkus ... když by se ti kůň měl dostat mimo šachovnici, tak "skoč" na protilehlý okraj a pokračuj v jeho pohybu.
Tj. pokud máš šachovnici 8x8 a kůň by měl jít na sloupec 9 , tak v toroidu se objeví ve sloupci 1. A u řádků je to stejné. Editoval liborb: grrr T9

To vím, že přeskočí, ale jak to realizovat v c++ :) to je ten háček, že zase tak zkušený nejsem...

To Rygy : nova_pozice % 8 v případě, že indexuješ od 0 - 7. Je to celočíslený zbytek po dělení osmi (8 % 8 = 0 --> 1. sloupec / řádek)

Ono by spíše stačilo změnit IsValidMove, aby se protilehlé strany spojily. Jak to udělat nevíte?

Konkrétně potřebuju, aby to dělalo něco stylu
Pos.Row a Pos.Col bylo někde mezi a
Kontrolovalo by to od BoardSize do BoardSize a mezi tím uložit Pos.Row a Pos.Col

V tom programu měníš pozici (Move) a pak testuješ validnost této nové pozice. A právě mezi tyto 2 části vložíš přepočet na souřadnice na protilehlé straně.
Pokud ti nevoní použití zbytku po dělení, tak to můžeš udělat přes podmínky (když je pozice -1, tak ji změň na šířku šachovnice - 1 atd.).