visual c++ 8 (.net 2005) has unresolved external symbol errors
The error is LNK2001: unresolved external symbol "protected: static
bool solver<typename, typename, int, int, int, int,
int>::solution" (<vc++ mangled name>)
Code (sudoku.cpp):
// Sudoku.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <vector>
#include <stdexcept>
#include <cstdlib>
#include <cmath>
#include <cstring>
#ifdef _MSC_VER
#define inline __inline
#endif
typedef unsigned __int8 u8;
typedef signed __int8 s8;
typedef unsigned __int16 u16;
typedef signed __int16 s16;
typedef unsigned __int32 u32;
typedef signed __int32 s32;
typedef signed __int64 u64;
typedef signed __int64 s64;
#define nullptr(T) (T *)0
#define check_calloc(ptr, ptrname, type, n, if_fail, if_fail_msg) \
if (ptr == nullptr(type)) {\
cerr << "calloc could not allocate " << ptrname << " [n=" << n <<
"], " << if_fail_msg; \
if_fail; \
}
//safety check: at least 1 _N must be defined
#if (!(defined _4) && !(defined _9) && !(defined _16) \
&& !(defined _25) && !(defined _36) && !(defined _49) && !(defined
_64))
#error "No _N(s) declared!!!"
#endif
using namespace std;
template <typename T, int n> struct sumOfBits {
static const T value = (T)((1 << (n - 1)) + sumOfBits<T, n -
1>::value);
};
template<typename T> struct sumOfBits<T, 0> {
static const T value = (T)0;
};
template <typename T>
class array {
public:
size_t length;
array(size_t _length) {
data = new T[_length];
length = _length;
}
T& operator[](unsigned int n) {
if ((size_t)n >= length) {
clog << "Array index out of range (n=" << n << ", length=" <<
length << "\"\n";
throw out_of_range("Array index out of range");
}
return data[n];
}
T& elem(unsigned int n) {
return data[n];
}
~array() { delete[] data; }
private:
T* data;
};
//templates: flexible hardcoding :P
template <typename cell_t = u16, typename pos_t = u8,
unsigned int width = 9, unsigned int width_rt = 3, int width_sq = 81,
cell_t val_mask = sumOfBits<u16, 9>::value,
unsigned int zb_len = 11>
class solver {
public:
solver() {
cells = (cell_t *)calloc(width_sq, sizeof(cell_t));
zeroBit = (char *)calloc(zb_len, 1);
}
//garbage collection
~solver() {
free(cells);
cells = (cell_t *)0;
free(zeroBit);
zeroBit = (char *)0;
}
static u8 *solve(u8 *board) {
solver *s = encode(board);
solver *s_copy = s;
u8 *sol = nullptr(u8);
solution = false;
s = s->search();
if (solution) {
sol = s->decode();
delete s;
} else
delete s_copy;
return sol;
}
protected:
//data
cell_t *cells;
//0th bit
char *zeroBit;
//is the puzzle solved
static bool solution;
//copy current solver
solver *duplicate(void) {
solver *dest = new solver();
pos_t i;
for (i = 0; i < width_sq; i++) {
dest->cells[i] = cells[i];
dest->zeroBit[i] = zeroBit[i];
}
return dest;
}
//check zeroBit
inline bool checkBit(pos_t i, char bit) {
u8 _byte = (u8)floor((i + 1) / 8.0);
return ((zeroBit[_byte] & (1 << (i % 8))) == bit) ? true : false;
}
//find most constrained position
pos_t constrained(void) {
u8 max = sumOfBits<u8, 7>::value;
pos_t maxp = (pos_t)max, i;
u8 j, v;
for (i = 0; i < width_sq; ++i) {
if (checkBit(i, 0)) {
v = 0;
for (j = 0; j < width; ++j)
if (((1 << j) & cells[i]) != 0)
++v;
if (v >= max || max >= sumOfBits<u8, 7>::value) {
max = v;
maxp = i;
}
}
}
return maxp;
}
//get all available options for value val
array<u8> *options(cell_t val) {
vector<u8> cc(0);
array<u8> *arr;
u8 i;
//find and add avialbale numbers
for (i = 0; i < width; ++i)
if (((1 << i) & val) == 0)
cc.push_back(i + 1);
arr = new array<u8>(cc.size());
for (i = 0; i < arr->length; i++)
arr->elem(i) = cc[i];
return arr;
}
//set value val in position pos, NOT-masking the other positions in
the group
void set(pos_t pos, u8 val) {
//column
u8 x = pos % width;
//row
u8 y = (u8)floor((pos * 1.0) / width);
//zone column, row
u8 zx = (u8)floor((x * 1.0) / width_rt) * width_rt;
u8 zy = (u8)floor((y * 1.0) / width_rt) * width_rt;
//value bit
cell_t add = 1 << ((cell_t)val - 1);
u8 k;
//NOT-mask the other positions in the group
for (k = 0; k < width; ++k) {
//mask column
cells[x + k * width] |= add;
//mask row
cells[k + y * width] |= add;
//mask zone
cells[zx + (k % width_rt) + width * (zy + (u8)floor((k * 1.0) /
width_rt))] |= add;
}
//unmask pos
cells[pos] = val_mask - add;
}
//sanity check
inline bool okay(void) {
pos_t i;
for (i = 0; i < width_sq; ++i)
if (((cells[i] & val_mask) == val_mask) && checkBit(i, 0))
return false;
return true;
}
//check if solved
inline bool solved(void) {
pos_t i;
for (i = 0; i < width_sq; ++i) {
if (checkBit(i, 0))
return false;
}
return true;
}
//search for solutions, return pointer to solution or null pointer
solver *search(void) {
pos_t p;
array<u8> *l;
u8 i;
solver *ns;
solver *ns_backup; //avoid memory leaks by backing up pointer
while (okay()) {
if (solved()) {
solution = true;
return this;
}
//start solving from most constrained position
p = constrained();
//no solution
if (p < 0)
return nullptr(solver);
//get all the available options for cell p
l = options(cells[p]);
//no solution
if (l->length < 1)
return nullptr(solver);
//try each option in cell p by recursing ourselves
//(i.e., (...(ns = this) ... = this))
for (i = 0; i < l->length; ++i) {
//recurse
ns = duplicate();
ns->set(p, l->elem(i));
ns_backup = ns; //avoid memory leaks
ns = ns->search();
//solution found, recurse back up
if (ns != nullptr(solver))
return ns;
else //solution not found, deallocate ns using backup
delete ns_backup;
}
//try first option
set(p, l->elem(0));
}
//failed sanity check
return nullptr(solver);
}
//decode bitmask solution to numerical solution
u8 *decode(void) {
u8 *arr = (u8 *)calloc(width_sq, sizeof(u8));
if (arr == nullptr(u8))
return arr;
pos_t i;
u8 j;
for (i = 0; i < width_sq; ++i)
for (j = 0; j < width; ++j)
if (((cells[i] | (cell_t)(1 << j)) == val_mask) && checkBit(i, 1))
{
arr[i] = j + (width < 10 ? 1 : 0);
break;
}
return arr;
}
static solver *encode(u8 *arr) {
solver *a = new solver();
pos_t i;
for (i = 0; i < width_sq; ++i) {
/* MAKE SURE that the number is between 1 and 9, inclusive so that
the
* solver does NOT mask 0 because that would break function isOK()
and
* hence prevent the solver from reaching a solution.
*/
if (width < 10) {
if (arr[i] >= 1 && arr[i] <= width)
a->set(i, arr[i]);
} else {
if (arr[i] >= 0 && arr[i] < width)
a->set(i + 1, arr[i]);
}
}
return a;
}
solver<cell_t, pos_t, width, width_rt, width_sq, val_mask, zb_len>::
};
//pase sIng to array
u8 *parse (char *str, unsigned __int8 base) {
u8 i;
u16 b2;
b2 = base * base;
u8 *arr = (u8 *)calloc(b2, 1);
if (arr == nullptr(u8))
return nullptr(u8);
for (i = 0; i < b2; i++) {
if (str[i] >= 0x30 && str[i] <= 0x39) //'0'-'9'
arr[i] = str[i] - 0x30;
else if (base >= 11) { //'a'-'z'
if (str[i] >= 0x61 && str[i] <= 0x7a)
arr[i] = str[i] - 0x57;
}
else if (base >= 37) { //'A'-'Z'
if (str[i] >= 0x41 && str[i] <= 0x5a)
arr[i] = str[i] - 0x1d;
}
else if (base >= 62) { //','-'.'
if (str[i] == 0x2c || str[i] == 0x2e)
arr[i] = (str[i] == 0x2c ? 62 : 63);
}
else
arr[i] = 1 << 7;
}
return arr;
}
//create sIng from array
char *arr_str(const u8 *arr, u16 len) {
char *str = (char *)calloc(len, 1);
u16 i;
if (str == nullptr(char))
return nullptr(char);
for (i = 0; i < len; i++) {
if (arr[i] < 10) str[i] = arr[i] + 0x30; //0-9
else if (arr[i] < 37) str[i] = arr[i] + 0x57; //a-z
else if (arr[i] < 62) str[i] = arr[i] + 0x1d; //A-Z
else if (arr[i] == 62) str[i] = 0x2c; //,
else if (arr[i] == 63) str[i] = 0x2e; //.
else str[i] = 0x3f; //?
}
return str;
}
int main(int argc, char *argv[]) {
u8 doku;
u8 *arr;
u8 *sol;
char *sIn = nullptr(char);
if (argc == 3)
doku = (strncmp(argv[1], "16", 3) == 0) ? 16
: (strncmp(argv[1], "25", 3) == 0) ? 25
: (strncmp(argv[1], "36", 3) == 0) ? 36
: (strncmp(argv[1], "4", 2) == 0) ? 4
: (strncmp(argv[1], "49", 3) == 0) ? 49
: (strncmp(argv[1], "64", 3) == 0) ? 64
: (strncmp(argv[1], "9", 2) == 0) ? 9
: 0;
else
doku = 9; //sudoku (9)
switch (argc) {
case 2: //puzzle from argv[1]
#if ((defined _4) && !(defined _9) && !(defined _16) \
&& !(defined _25) && !(defined _36) && !(defined _49) && !(defined
_64))
arr = parse(argv[1], 16);
check_calloc(arr, "arr", u8, 16, goto error, "exiting...\n");
goto doku4;
#endif //(_4)
#ifdef _9
arr = parse(argv[1], 81);
check_calloc(arr, "arr", u8, 81, goto error, "exiting...\n");
goto doku9;
#endif //_9
#if (!(defined _4) && !(defined _9) && (defined _16) \
&& !(defined _25) && !(defined _36) && !(defined _49) && !(defined
_64))
arr = parse(argv[1], 256);
check_calloc(arr, "arr", u8, 256, goto error, "exiting...\n");
goto doku16;
#endif //(_16)
#if (!(defined _4) && !(defined _9) && !(defined _16) \
&& (defined _25) && !(defined _36) && !(defined _49) && !(defined
_64))
arr = parse(argv[1], 625);
check_calloc(arr, "arr", u8, 625, goto error, "exiting...\n");
goto doku25;
#endif //(_25)
#if (!(defined _4) && !(defined _9) && !(defined _16) \
&& !(defined _25) && (defined _36) && !(defined _49) && !(defined
_64))
arr = parse(argv[1], 1296);
check_calloc(arr, "arr", u8, 1296, goto error, "exiting...\n");
goto doku36;
#endif //(_36)
#if (!(defined _4) && !(defined _9) && !(defined _16) \
&& !(defined _25) && !(defined _36) && (defined _49) && !(defined
_64))
arr = parse(argv[1], 2401);
check_calloc(arr, "arr", u8, 2401, goto error, "exiting...\n");
goto doku49;
#endif //(_49)
#if (!(defined _4) && !(defined _9) && !(defined _16) \
&& !(defined _25) && !(defined _36) && !(defined _49) && (defined
_64))
arr = parse(argv[1], 4096);
check_calloc(arr, "arr", u8, 4096, goto error, "exiting...\n");
goto doku64;
#endif //(_64)
case 3: //puzzle from argv[2]
switch (doku) {
#ifdef _4
case 4:
arr = parse(argv[2], 16);
check_calloc(arr, "arr", u8, 16, goto error, "exiting...\n");
goto doku4;
#endif //_4
#ifdef _9
case 9:
arr = parse(argv[2], 81);
check_calloc(arr, "arr", u8, 81, goto error, "exiting...\n");
goto doku9;
#endif //_9
#ifdef _16
case 16:
arr = parse(argv[2], 256);
check_calloc(arr, "arr", u8, 256, goto error, "exiting...\n");
goto doku16;
#endif //_16
#ifdef _25
case 25:
arr = parse(argv[2], 625);
check_calloc(arr, "arr", u8, 625, goto error, "exiting...\n");
goto doku25;
#endif //_25
#ifdef _36
case 36:
arr = parse(argv[2], 1296);
check_calloc(arr, "arr", u8, 1296, goto error, "exiting...\n");
goto doku36;
#endif //_36
#ifdef _49
case 49:
arr = parse(argv[2], 2401);
check_calloc(arr, "arr", u8, 2401, goto error, "exiting...\n");
goto doku49;
#endif //_49
#ifdef _64
case 64:
arr = parse(argv[2], 4096);
check_calloc(arr, "arr", u8, 4096, goto error, "exiting...\n");
goto doku64;
#endif //_64
} //case 3 switch (doku)
case 1: //puzzle from stdin
switch (doku) {
#ifdef _4
case 4:
sIn = (char *)calloc(17, 1);
check_calloc(sIn, "sIn", char, 17, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 16);
check_calloc(arr, "arr", u8, 16, goto error, "exiting...\n");
goto doku4;
#endif //_4
#ifdef _9
case 9:
sIn = (char *)calloc(82, 1);
check_calloc(sIn, "sIn", char, 82, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 81);
check_calloc(arr, "arr", u8, 81, goto error, "exiting...\n");
goto doku9;
#endif //_9
#ifdef _16
case 16:
sIn = (char *)calloc(257, 1);
check_calloc(sIn, "sIn", char, 257, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 256);
check_calloc(arr, "arr", u8, 256, goto error, "exiting...\n");
goto doku16;
#endif //_16
#ifdef _25
case 25:
sIn = (char *)calloc(626, 1);
check_calloc(sIn, "sIn", char, 626, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 625);
check_calloc(arr, "arr", u8, 625, goto error, "exiting...\n");
goto doku25;
#endif //_25
#ifdef _36
case 36:
sIn = (char *)calloc(1297, 1);
check_calloc(sIn, "sIn", char, 1297, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 1296);
check_calloc(arr, "arr", u8, 1296, goto error, "exiting...\n");
goto doku36;
#endif //_36
#ifdef _49
case 49:
sIn = (char *)calloc(2402, 1);
check_calloc(sIn, "sIn", char, 2402, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 2401);
check_calloc(arr, "arr", u8, 2401, goto error, "exiting...\n");
goto doku49;
#endif //_49
#ifdef _64
case 64:
sIn = (char *)calloc(4097, 1);
check_calloc(sIn, "sIn", char, 4097, goto error, "exiting...\n");
cin >> sIn;
arr = parse(sIn, 4096);
check_calloc(arr, "arr", u8, 4096, goto error, "exiting...\n");
goto doku64;
#endif //_64
} //case 1 switch (doku)
} //switch(argc)
#ifdef _4
doku4:
sol = solver<u8, u8, 4, 2, 8, sumOfBits<u8, 4>::value,
1>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_4
#ifdef _9
doku9:
sol = solver<u16, u8, 9, 3, 81, sumOfBits<u16, 9>::value,
11>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_9
#ifdef _16
doku16:
sol = solver<u16, u8, 16, 4, 256, sumOfBits<u16, 16>::value,
32>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_16
#ifdef _25
doku25:
sol = solver<u32, u16, 25, 5, 625, sumOfBits<u32, 25>::value,
79>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_25
#ifdef _36
doku36:
sol = solver<u64, u16, 36, 6, 1296, sumOfBits<u64, 36>::value,
162>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_36
#ifdef _49
doku49:
sol = solver<u64, u16, 49, 7, 2401, sumOfBits<u64, 49>::value,
301>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_49
#ifdef _64
doku64:
sol = solver<u64, u16, 64, 8, 4096, sumOfBits<u64, 64>::value,
512>::solve(arr);
if (sol == nullptr(u8))
goto no_solution_found;
else
goto solution_found;
#endif //_64
no_solution_found:
cout << "No solution found for puzzle " << (argc == 3 ? argv[2] :
(sIn != nullptr(char)) ? sIn : argv[1]) << endl;
goto done;
solution_found:
cout << "Solution for puzzle " << (argc == 3 ? argv[2] : (sIn !=
nullptr(char)) ? sIn : argv[1])
<< " is " << arr_str(sol, (u16)strlen((sIn != nullptr(char)) ? sIn :
argv[1])) << endl;
goto done;
error:
return 1;
done:
return 0;
}
Compile with options -D_4 -D_9 -D_16 -D_25 -D_36 -D_49 -D_64
Any (elegant?) way to fix the error (if you can use diif -Naur fromat,
that would be very nice)?