Pohyb koně po toroidu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Rygy0
Newbie
11. 11. 2009   #1
-
0
-

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");
}
}

Nahlásit jako SPAM
IP: 89.29.97.–
Reklama
Reklama
ian0
Stálý člen
12. 11. 2009   #2
-
0
-

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).

Nahlásit jako SPAM
IP: 89.24.135.–
-- ian
Rygy0
Newbie
22. 11. 2009   #3
-
0
-

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.

Nahlásit jako SPAM
IP: 89.29.97.–
liborb
~ Redaktor
+18
Guru
23. 11. 2009   #4
-
0
-

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 ...

Nahlásit jako SPAM
IP: 85.207.166.–
Rygy0
Newbie
23. 11. 2009   #5
-
0
-

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.

Nahlásit jako SPAM
IP: 89.29.97.–
liborb
~ Redaktor
+18
Guru
23. 11. 2009   #6
-
0
-

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.

Nahlásit jako SPAM
IP: 195.189.143.–
liborb
~ Redaktor
+18
Guru
23. 11. 2009   #7
-
0
-

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

Nahlásit jako SPAM
IP: 195.189.143.–
Rygy0
Newbie
23. 11. 2009   #8
-
0
-

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

Nahlásit jako SPAM
IP: 89.29.97.–
Bald3rr0
Super člen
23. 11. 2009   #9
-
0
-

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)

Nahlásit jako SPAM
IP: 82.100.0.–
Rygy0
Newbie
24. 11. 2009   #10
-
0
-

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

Nahlásit jako SPAM
IP: 89.29.97.–
Rygy0
Newbie
24. 11. 2009   #11
-
0
-

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

Nahlásit jako SPAM
IP: 89.29.97.–
liborb
~ Redaktor
+18
Guru
24. 11. 2009   #12
-
0
-

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.).

Nahlásit jako SPAM
IP: 195.189.143.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 51 hostů

Podobná vlákna

Pohyb oknem — založil dyžon

Pohyb s myší — založil radar.sm

Animovaný pohyb — založil Luky C.

Pohyb TEXTU — založil Michal

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý