Jump to content

Solve a Numbrix puzzle: Difference between revisions

Solve a Numbrix puzzle (view source)

Revision as of 13:56, 30 June 2015

475 bytes removed ,  9 years ago
made more idiomatic, using vector in place of new array, etc
(Tcl implementation added)
(made more idiomatic, using vector in place of new array, etc)
Line 72:
#include <iostream>
#include <iterator>
#include <stdlib.hcstdlib>
#include <string.h>
#include <bitset>
 
 
using namespace std;
typedef bitset<4> hood_t;
 
struct node
{
int val;
unsigned char hood_t neighbors;
};
 
Line 87 ⟶ 88:
{
public:
nSolver()
{
dx[0] = -1; dy[0] = 0; dx[1] = 1; dy[1] = 0;
dx[2] = 0; dy[2] = -1; dx[3] = 0; dy[3] = 1;
}
 
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 ) );
weHave = new bool[len + 1]; memset( weHave, 0, len + 1 );
 
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
{
if (puzz.size() < 1) return;
if( ( *i ) == "*" ) { max--; arr[c++].val = -1; continue; }
wid = max_wid;
arr[c].val = atoi( ( *i ).c_str() );
hei = static_cast<int>(puzz.size()) / wid;
if( arr[c].val > 0 ) weHave[arr[c].val] = true;
max = wid * c++hei;
int len = max, c = 0;
}
arr = vector<node>(len, node({ 0, 0 }));
weHave = vector<bool>(len + 1, false);
 
for (const auto& s : puzz)
solveIt(); c = 0;
{
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
if (s == "*") { max--; arr[c++].val = -1; continue; }
{
arr[c].val = atoi(s.c_str());
if( ( *i ) == "." )
if (arr[c].val > 0) weHave[arr[c].val] = true;
{
c++;
ostringstream o; o << arr[c].val;
}
( *i ) = o.str();
 
}
solveIt(); c = c++0;
for (auto&& s : puzz)
{
if (s == ".")
s = std::to_string(arr[c].val);
c++;
}
}
delete [] arr;
delete [] weHave;
}
 
private:
bool search( int x, int y, int w, int dr )
{
if( ( w > max && dr > 0 ) || ( w < 1 && dr < 0 ) || ( w == max && weHave[w] ) ) return true;
 
node* n = &arr[x + y * wid];
n->neighbors = getNeighbors( x, y );
if( weHave[w] )
{
if ((w > max && dr > 0) || (w < 1 && dr < 0) || (w == max && weHave[w])) return true;
for( int d = 0; d < 4; d++ )
 
{
if(node& n->neighbors & (= 1arr[x <<+ dy )* )wid];
n.neighbors = getNeighbors(x, y);
if (weHave[w])
{
for (int d = 0; d < 4; d++)
{
if (n.neighbors[d])
{
int a = x + dx[d], b = y + dy[d];
if (arr[a + b * wid].val == w)
if (search(a, b, w + dr, dr))
return true;
}
}
return false;
}
 
for (int d = 0; d < 4; d++)
{
if (n.neighbors[d])
int a = x + dx[d], b = y + dy[d];
{
if( arr[a + b * wid].val == w )
if( search( int a, b,= wx + drdx[d], drb )= )y return+ truedy[d];
if (arr[a + b * wid].val == 0)
{
arr[a + b * wid].val = w;
if (search(a, b, w + dr, dr))
return true;
arr[a + b * wid].val = 0;
}
}
}
return false;
}
return false;
}
 
hood_t getNeighbors(int x, int y)
for( int d = 0; d < 4; d++ )
{
hood_t retval;
if( n->neighbors & ( 1 << d ) )
for (int xx = 0; xx < 4; xx++)
{
int a = x + dx[d], b = y + dy[d];
if( arr[a + b * wid].val == 0 )
{
int a = arr[ax + dx[xx], b *= wid].valy =+ wdy[xx];
if (a < 0 if(|| search(b a,< b,0 w|| +a dr,>= drwid )|| )b return>= hei) true;
continue;
arr[a + b * wid].val = 0;
if (arr[a + b * wid].val > -1)
retval.set(xx);
}
return retval;
}
}
return false;
}
 
void solveIt()
unsigned char getNeighbors( int x, int y )
{
unsigned char c = 0; int a, b;
for( int xx = 0; xx < 4; xx++ )
{
int x, y, z; a = findStart(x + dx[xx], b = y, + dy[xx]z);
if (z == 99999) { cout << "\nCan't find start point!\n"; return; }
if( a < 0 || b < 0 || a >= wid || b >= hei ) continue;
search(x, y, z + 1, 1);
if( arr[a + b * wid].val > -1 ) c |= ( 1 << xx );
if (z > 1) search(x, y, z - 1, -1);
}
return c;
}
 
void findStart(int& x, int& y, int& z)
void solveIt()
{
{
z = 99999;
int x, y, z; findStart( x, y, z );
for (int b = 0; b < hei; b++)
if( z == 99999 ) { cout << "\nCan't find start point!\n"; return; }
search for (int x,a y,= z0; +a 1,< 1wid; a++);
if (arr[a + wid * b].val > 0 if(&& zarr[a >+ 1wid )* search(b].val x, y,< z - 1, -1 );
{
}
x = a; y = b;
 
z = arr[a + wid * b].val;
void findStart( int& x, int& y, int& z )
{
z = 99999;
for( int b = 0; b < hei; b++ )
for( int a = 0; a < wid; a++ )
if( arr[a + wid * b].val > 0 && arr[a + wid * b].val < z )
{
x = a; y = b;
z = arr[a + wid * b].val;
}
 
}
}
 
vector<int> dx = vector<int>({ wid-1, hei1, max0, dx[4],0 dy[4]});
vector<int> dy = vector<int>({ 0, 0, -1, 1 });
node* arr;
int wid, hei, max;
bool* weHave;
vector<node> arr;
vector<bool> weHave;
};
 
//------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
int wid; string p;
//p = ". . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17 . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . ."; wid = 9;
//p = ". . . . . . . . . . 11 12 15 18 21 62 61 . . 6 . . . . . 60 . . 33 . . . . . 57 . . 32 . . . . . 56 . . 37 . 1 . . . 73 . . 38 . . . . . 72 . . 43 44 47 48 51 76 77 . . . . . . . . . ."; wid = 9;
p = "17 . . . 11 . . . 59 . 15 . . 6 . . 61 . . . 3 . . . 63 . . . . . . 66 . . . . 23 24 . 68 67 78 . 54 55 . . . . 72 . . . . . . 35 . . . 49 . . . 29 . . 40 . . 47 . 31 . . . 39 . . . 45"; wid = 9;
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 );
 
istringstream iss(p); vector<string> puzz;
int c = 0;
copy(istream_iterator<string>(iss), istream_iterator<string>(), back_inserter<vector<string> >(puzz));
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
nSolver s; s.solve(puzz, wid);
{
 
if( ( *i ) != "*" && ( *i ) != "." )
int c = 0;
for (const auto& s : puzz)
{
if( atoi(s (!= "*i" ).c_str()&& )s < 10 ) cout <<!= "0.";)
{
cout << ( *i ) << " ";
if (atoi(s.c_str()) < 10) cout << "0";
cout << s << " ";
}
else cout << " ";
if (++c >= wid) { cout << endl; c = 0; }
}
else cout << " endl << "endl;
return system("pause");
if( ++c >= wid ) { cout << endl; c = 0; }
}
cout << endl << endl;
return system( "pause" );
}
</lang>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/247277"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information