Solve a Numbrix puzzle: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Tcl implementation added
made more idiomatic, using vector in place of new array, etc
Line 72: Line 72:
#include <iostream>
#include <iostream>
#include <iterator>
#include <iterator>
#include <stdlib.h>
#include <cstdlib>
#include <string.h>
#include <string>
#include <bitset>



using namespace std;
using namespace std;
typedef bitset<4> hood_t;


struct node
struct node
{
{
int val;
int val;
unsigned char neighbors;
hood_t neighbors;
};
};


Line 87: Line 88:
{
{
public:
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 )
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;
c++;
max = wid * 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();

}
c++;
solveIt(); c = 0;
for (auto&& s : puzz)
{
if (s == ".")
s = std::to_string(arr[c].val);
c++;
}
}
}
delete [] arr;
delete [] weHave;
}


private:
private:
bool search( int x, int y, int w, int dr )
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( n->neighbors & ( 1 << d ) )
node& n = arr[x + y * 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( a, b, w + dr, dr ) ) return true;
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 + 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 )
{
{
arr[a + b * wid].val = w;
int a = x + dx[xx], b = y + dy[xx];
if( search( a, b, w + dr, dr ) ) return true;
if (a < 0 || b < 0 || a >= wid || b >= hei)
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++ )
{
{
a = x + dx[xx], b = y + dy[xx];
int x, y, z; findStart(x, y, 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( x, y, z + 1, 1 );
for (int a = 0; a < wid; a++)
if( z > 1 ) search( x, y, z - 1, -1 );
if (arr[a + wid * b].val > 0 && arr[a + wid * b].val < z)
{
}
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;
}
}


}
}


int wid, hei, max, dx[4], dy[4];
vector<int> dx = vector<int>({ -1, 1, 0, 0 });
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 main(int argc, char* argv[])
{
{
int wid; string p;
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 = ". . . . . . . . . . . 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 = ". . . . . . . . . . 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;
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( ( *i ).c_str() ) < 10 ) cout << "0";
if (s != "*" && s != ".")
{
cout << ( *i ) << " ";
if (atoi(s.c_str()) < 10) cout << "0";
cout << s << " ";
}
else cout << " ";
if (++c >= wid) { cout << endl; c = 0; }
}
}
else cout << " ";
cout << endl << endl;
return system("pause");
if( ++c >= wid ) { cout << endl; c = 0; }
}
cout << endl << endl;
return system( "pause" );
}
}
</lang>
</lang>
Retrieved from "https://rosettacode.org/wiki/Solve_a_Numbrix_puzzle"