Solve a Hopido puzzle: Difference between revisions
Content added Content deleted
No edit summary |
No edit summary |
||
Line 22: | Line 22: | ||
* [[Solve a Numbrix puzzle]] |
* [[Solve a Numbrix puzzle]] |
||
* [[Knight's tour]] |
* [[Knight's tour]] |
||
=={{header|C++}}== |
|||
<lang cpp> |
|||
#include <vector> |
|||
#include <sstream> |
|||
#include <iostream> |
|||
#include <iterator> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
using namespace std; |
|||
struct node |
|||
{ |
|||
int val; |
|||
unsigned char neighbors; |
|||
}; |
|||
class nSolver |
|||
{ |
|||
public: |
|||
nSolver() |
|||
{ |
|||
dx[0] = -2; dy[0] = -2; dx[1] = -2; dy[1] = 2; |
|||
dx[2] = 2; dy[2] = -2; dx[3] = 2; dy[3] = 2; |
|||
dx[4] = -3; dy[4] = 0; dx[5] = 3; dy[5] = 0; |
|||
dx[6] = 0; dy[6] = -3; dx[7] = 0; dy[7] = 3; |
|||
} |
|||
void solve( vector<string>& puzz, int max_wid ) |
|||
{ |
|||
if( puzz.size() < 1 ) return; |
|||
wid = max_wid; hei = static_cast<int>( puzz.size() ) / wid; |
|||
int len = wid * hei, c = 0; max = len; |
|||
arr = new node[len]; memset( arr, 0, len * sizeof( node ) ); |
|||
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) |
|||
{ |
|||
if( ( *i ) == "*" ) { max--; arr[c++].val = -1; continue; } |
|||
arr[c].val = atoi( ( *i ).c_str() ); |
|||
c++; |
|||
} |
|||
solveIt(); c = 0; |
|||
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) |
|||
{ |
|||
if( ( *i ) == "." ) |
|||
{ |
|||
ostringstream o; o << arr[c].val; |
|||
( *i ) = o.str(); |
|||
} |
|||
c++; |
|||
} |
|||
delete [] arr; |
|||
} |
|||
private: |
|||
bool search( int x, int y, int w ) |
|||
{ |
|||
if( w > max ) return true; |
|||
node* n = &arr[x + y * wid]; |
|||
n->neighbors = getNeighbors( x, y ); |
|||
for( int d = 0; d < 8; d++ ) |
|||
{ |
|||
if( n->neighbors & ( 1 << d ) ) |
|||
{ |
|||
int a = x + dx[d], b = y + dy[d]; |
|||
if( arr[a + b * wid].val == 0 ) |
|||
{ |
|||
arr[a + b * wid].val = w; |
|||
if( search( a, b, w + 1 ) ) return true; |
|||
arr[a + b * wid].val = 0; |
|||
} |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
unsigned char getNeighbors( int x, int y ) |
|||
{ |
|||
unsigned char c = 0; int a, b; |
|||
for( int xx = 0; xx < 8; xx++ ) |
|||
{ |
|||
a = x + dx[xx], b = y + dy[xx]; |
|||
if( a < 0 || b < 0 || a >= wid || b >= hei ) continue; |
|||
if( arr[a + b * wid].val > -1 ) c |= ( 1 << xx ); |
|||
} |
|||
return c; |
|||
} |
|||
void solveIt() |
|||
{ |
|||
int x, y, z; findStart( x, y, z ); |
|||
if( z == 99999 ) { cout << "\nCan't find start point!\n"; return; } |
|||
search( x, y, z + 1 ); |
|||
} |
|||
void findStart( int& x, int& y, int& z ) |
|||
{ |
|||
for( int b = 0; b < hei; b++ ) |
|||
for( int a = 0; a < wid; a++ ) |
|||
if( arr[a + wid * b].val == 0 ) |
|||
{ |
|||
x = a; y = b; z = 1; |
|||
arr[a + wid * b].val = z; |
|||
return; |
|||
} |
|||
} |
|||
int wid, hei, max, dx[8], dy[8]; |
|||
node* arr; |
|||
}; |
|||
int main( int argc, char* argv[] ) |
|||
{ |
|||
int wid; string p; |
|||
p = "* . . * . . * . . . . . . . . . . . . . . * . . . . . * * * . . . * * * * * . * * *"; wid = 7; |
|||
istringstream iss( p ); vector<string> puzz; |
|||
copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( puzz ) ); |
|||
nSolver s; s.solve( puzz, wid ); |
|||
int c = 0; |
|||
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) |
|||
{ |
|||
if( ( *i ) != "*" && ( *i ) != "." ) |
|||
{ |
|||
if( atoi( ( *i ).c_str() ) < 10 ) cout << "0"; |
|||
cout << ( *i ) << " "; |
|||
} |
|||
else cout << " "; |
|||
if( ++c >= wid ) { cout << endl; c = 0; } |
|||
} |
|||
cout << endl << endl; |
|||
return system( "pause" ); |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
01 04 12 03 |
|||
27 16 19 22 15 18 21 |
|||
05 08 11 02 07 10 13 |
|||
23 26 17 20 25 |
|||
06 09 14 |
|||
24 |
|||
</pre> |
|||
==Icon and {{header|Unicon}}== |
==Icon and {{header|Unicon}}== |