code:
#include <iostream>
#include <vector>
#include <stdexcept>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
#ifdef _MSC_VER
#define inline __inline
#endif
typedef unsigned __int8 u8;
typedef signed __int8 s8;
typedef unsigned __int16 u16;
#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; \
}
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) {
cerr << "Array index out of range (n=" << n << ", length=" <<
length << "\"\n";
throw std::out_of_range("Array index out of range");
}
return data[n];
}
T& elem(unsigned int n) {
if ((size_t)n >= length) {
cerr << "Array index out of range (n=" << n << ", length=" <<
length << "\"\n";
throw std::out_of_range("Array index out of range");
}
return data[n];
}
~array() { delete[] data; }
private:
T* data;
};
class solver {
public:
solver() {
cells = (u16 *)calloc(81, 2);
zeroBit = (char *)calloc(11, 1);
}
//garbage collection
~solver() {
free(cells);
cells = (u16 *)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
u16 *cells;
//0th bit
char *zeroBit;
//is the puzzle solved
static bool solution;
//copy current solver
solver *duplicate(void) {
solver *dest = new solver();
u8 i;
for (i = 0; i < 81; i++) {
dest->cells[i] = cells[i];
dest->zeroBit[i] = zeroBit[i];
}
return dest;
}
//check zeroBit
inline bool checkBit(u8 i, char bit) {
u8 _byte = (u8)floor((i + 1) / 8.0);
return ((zeroBit[_byte] & (1 << (i % 8))) == bit) ? true : false;
}
//find most constrained position
u8 constrained(void) {
u8 max = 0x7f;
u8 maxp = 0x7f, i;
u8 j, v;
for (i = 0; i < 81; ++i) {
if (checkBit(i, 0)) {
v = 0;
for (j = 0; j < 9; ++j)
if (((1 << j) & cells[i]) != 0)
++v;
if (v >= max || max >= 0x7f) {
max = v;
maxp = i;
}
}
}
return maxp;
}
//get all available options for value val
array<u8*options(u16 val) {
vector<u8cc(0);;
array<u8*arr;
u8 i;
//find and add avialbale numbers
for (i = 0; i < 9; ++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;
^ segfault null dereference at this line when vc++
does cleanup of vector before returning ^
}
//set value val in position pos, NOT-masking the other positions in
the group
void set(u8 pos, u8 val) {
//column
u8 x = pos % 9;
//row
u8 y = (u8)floor((pos * 1.0) / 9);
//zone column, row
u8 zx = (u8)floor((x * 1.0) / 3) * 3;
u8 zy = (u8)floor((y * 1.0) / 3) * 3;
//value bit
u16 add = 1 << ((u16)val - 1);
u8 k;
//NOT-mask the other positions in the group
for (k = 0; k < 9; ++k) {
//mask column
cells[x + k * 9] |= add;
//mask row
cells[k + y * 9] |= add;
//mask zone
cells[zx + (k % 3) + 9 * (zy + (u8)floor((k * 1.0) / 3))] |= add;
}
//unmask pos
cells[pos] = 0x1ff - add;
}
//sanity check
inline bool okay(void) {
u8 i;
for (i = 0; i < 81; ++i)
if (((cells[i] & 0x1ff) == 0x1ff) && checkBit(i, 0))
return false;
return true;
}
//check if solved
inline bool solved(void) {
u8 i;
for (i = 0; i < 81; ++i) {
if (checkBit(i, 0))
return false;
}
return true;
}
//search for solutions, return pointer to solution or null pointer
solver *search(void) {
u8 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));
delete l;
}
//failed sanity check
return nullptr(solver);
}
//decode bitmask solution to numerical solution
u8 *decode(void) {
u8 *arr = (u8 *)calloc(81, sizeof(u8));
if (arr == nullptr(u8))
return arr;
u8 i;
u8 j;
for (i = 0; i < 81; ++i)
for (j = 0; j < 9; ++j)
if (((cells[i] | (u16)(1 << j)) == 0x1ff) &&
checkBit(i, 1)) {
arr[i] = j + 1;
break;
}
return arr;
}
static solver *encode(u8 *arr) {
solver *a = new solver();
u8 i;
for (i = 0; i < 81; ++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 (arr[i] >= 1 && arr[i] <= 9)
a->set(i, arr[i]);
}
return a;
}
};
bool solver::solution;
//pase sIng to array
u8 *parse (const char *str) {
u8 i;
u8 *arr = (u8 *)calloc(81, 1);
if (arr == nullptr(u8))
return nullptr(u8);
for (i = 0; i < 81; i++) {
if (str[i] 0x30 && str[i] <= 0x39) //'1'-'9'
arr[i] = str[i] - 0x30;
else
arr[i] = 1 << 7;
}
return arr;
}
//create sIng from array
char *arr_str(const u8 *arr) {
char *str = (char *)calloc(82, 1);
u16 i;
if (str == nullptr(char))
return nullptr(char);
for (i = 0; i < 81; i++)
if (arr[i] < 10)
str[i] = arr[i] + 0x30; //1-9
else
str[i] = 0x3f; //?
str[81] = '\0';
return str;
}
int main(int argc, char *argv[]) {
u8 *arr;
u8 *sol;
FILE *f;
char *sIn = nullptr(char);
switch (argc) {
case 2:
if (argv[1][0] < 0x31 || argv[1][0] 0x39)
goto from_file;
arr = parse(argv[1]);
check_calloc(arr, "arr", u8, 81, return 1, "exiting...
\n");
break;
case 1:
sIn = (char *)calloc(82, 1);
check_calloc(sIn, "sIn", char, 82, return 1, "exiting...
\n");
cin >sIn;
arr = parse(sIn);
check_calloc(arr, "arr", u8, 81, return 1, "exiting...
\n");
break;
default:
fprintf(stderr, "usage:\n\tsudoku input\n\tsudoku < input
\n");
return 1;
} //switch(argc)
goto solve;
from_file:
f = fopen(argv[1], "r");
sIn = (char *)calloc(82, 1);
check_calloc(sIn, "sIn", char, 82, return 1, "exiting...\n");
fgets(sIn, 81, f);
arr = parse(sIn);
check_calloc(arr, "arr", u8, 81, return 1, "exiting...\n");
solve:
sol = solver::solve(arr);
if (sol == nullptr(u8)) {
cout << "No solution found for puzzle "
<< (argc == 2 ? argv[1] : (sIn != nullptr(char)) ?
sIn : '\0') << endl;
return 0;
} else {
cout << "Solution for puzzle " << (argc == 2 ? argv[1] : (sIn !
= nullptr(char)) ? sIn : '\0')
<< " is " << arr_str(sol) << endl;
return 0;
}
}
