I have serious problem with my Hexadoku (16 x 16 , a - p) solver. I'd like to run the program in under 2 seconds but my solution solves it in 10 seconds.

Native Code:

#include <stdio.h>
#include <stdio.h>

{
int rowStart = (radek/4) * 4;
int colStart = (sloupec/4) * 4;

int i;
for(i=0; i<16; ++i)
{
if (hexadoku[i][sloupec] == num)                         return 0;
if (hexadoku[rowStart + (i%4)][colStart + (i/4)] == num) return 0;
}

return 1;
}

{
int i = 0;
if (sloupec >= 16)
{
sloupec = 0;
{
return 1;
}
}

{
}
else
{
for(i=0; i<16; ++i)
{
{

if (good)
{   return 1;
}
}
}
}
return 0;
}

int main()
{

char pole[17][17];
char tmp[66];
int i = 0, j = 0, k = 0, l = 0, m = 0, x = 0, y = 0;

while ( scanf( " %[^\n]", &tmp ) == 1 )
{

for ( j = 2; j <= 62; j += 4 )
{
if ( tmp[0] != '+' )
{
pole[i][k] = tmp[j];
k++;
}
}

pole[i][k] = '\0';
k = 0;
if ( tmp[0] != '+' )
i++;
}

for ( i = 0; i < 16; i++ )
{
for ( l = 0; l < 16; l++ )
{
if( !(( pole[i][l] >='a' && pole[i][l] <= 'p' ) || ( pole[i][l] == ' ' )) ) { printf("Nespravny vstup.\n"); return 1; }
}
}

i = 0;
l = 0;

for (m = 0; m < 16; m++)
{
for (i = 0; i < 16; i++)
{
for (l = 0; l < 16; l++)
{
if ((pole[m][l] == pole[m][i]) && (i != l) && (pole[m][l] != ' ') && (pole[m][i] != ' ') ) { printf("Nespravny vstup.\n"); return 1; }
if ((pole[l][m] == pole[i][m]) && (i != l) && (pole[l][m] != ' ') && (pole[i][m] != ' ') ) { printf("Nespravny vstup.\n"); return 1; }
}
}
}

i = 0;
l = 0;
j = 0;

for (l = 0; l < 16; l+=3)
{
for (i = 0; i < 4 ; i++)
{
for (j = 0; j < 4; j++)
{
for (x = 0; x < 4; x++)
{
for (y = 0; y < 4; y++)
{
if(i==x && j==y) continue;
if ( (pole[i][j] == pole[x][y]) && (pole[i][j] != ' ') && (pole[x][y] != ' ') ) { printf("Nespravny vstup.\n"); return 1; }
}
}
}
}
i+=3;
j+=3;
x+=3;
y+=3;
}

for (i = 0; i < 16; i++)
{
for (j = 0; j < 16; j++)
{
switch (pole[i][j])
{
default : break;
}
}
}

{

for (i = 0; i < 16; i++)
{
for (j = 0; j < 16; j++)
{
{
case 0: pole[i][j]= ' '; break;
case 1: pole[i][j]= 'a'; break;
case 2: pole[i][j]= 'b'; break;
case 3: pole[i][j]= 'c'; break;
case 4: pole[i][j]= 'd'; break;
case 5: pole[i][j]= 'e'; break;
case 6: pole[i][j]= 'f'; break;
case 7: pole[i][j]= 'g'; break;
case 8: pole[i][j]= 'h'; break;
case 9: pole[i][j]= 'i'; break;
case 10: pole[i][j]= 'j'; break;
case 11: pole[i][j]= 'k'; break;
case 12: pole[i][j]= 'l'; break;
case 13: pole[i][j]= 'm'; break;
case 14: pole[i][j]= 'n'; break;
case 15: pole[i][j]= 'o'; break;
case 16: pole[i][j]= 'p'; break;
default : break;
}
}
}

printf(
"+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +\n"
"| %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c | %c   %c   %c   %c |\n"
"+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n"

, pole[0][0], pole[0][1], pole[0][2], pole[0][3], pole[0][4], pole[0][5], pole[0][6],    pole[0][7], pole[0][8], pole[0][9], pole[0][10], pole[0][11], pole[0][12], pole[0][13], pole[0][14], pole[0][15]
, pole[1][0], pole[1][1], pole[1][2], pole[1][3], pole[1][4], pole[1][5], pole[1][6],    pole[1][7], pole[1][8], pole[1][9], pole[1][10], pole[1][11], pole[1][12], pole[1][13],                    pole[1][14], pole[1][15]
, pole[2][0], pole[2][1], pole[2][2], pole[2][3], pole[2][4], pole[2][5], pole[2][6], pole[2][7], pole[2][8], pole[2][9], pole[2][10], pole[2][11], pole[2][12], pole[2][13], pole[2][14], pole[2][15]
, pole[3][0], pole[3][1], pole[3][2], pole[3][3], pole[3][4], pole[3][5], pole[3][6], pole[3][7], pole[3][8], pole[3][9], pole[3][10], pole[3][11], pole[3][12], pole[3][13], pole[3][14], pole[3][15]
, pole[4][0], pole[4][1], pole[4][2], pole[4][3], pole[4][4], pole[4][5], pole[4][6], pole[4][7], pole[4][8], pole[4][9], pole[4][10], pole[4][11], pole[4][12], pole[4][13], pole[4][14], pole[4][15]
, pole[5][0], pole[5][1], pole[5][2], pole[5][3], pole[5][4], pole[5][5], pole[5][6], pole[5][7], pole[5][8], pole[5][9], pole[5][10], pole[5][11], pole[5][12], pole[5][13], pole[5][14], pole[5][15]
, pole[6][0], pole[6][1], pole[6][2], pole[6][3], pole[6][4], pole[6][5], pole[6][6], pole[6][7], pole[6][8], pole[6][9], pole[6][10], pole[6][11], pole[6][12], pole[6][13], pole[6][14], pole[6][15]
, pole[7][0], pole[7][1], pole[7][2], pole[7][3], pole[7][4], pole[7][5], pole[7][6], pole[7][7], pole[7][8], pole[7][9], pole[7][10], pole[7][11], pole[7][12], pole[7][13], pole[7][14], pole[7][15]
, pole[8][0], pole[8][1], pole[8][2], pole[8][3], pole[8][4], pole[8][5], pole[8][6], pole[8][7], pole[8][8], pole[8][9], pole[8][10], pole[8][11], pole[8][12], pole[8][13], pole[8][14], pole[8][15]
, pole[9][0], pole[9][1], pole[9][2], pole[9][3], pole[9][4], pole[9][5], pole[9][6], pole[9][7], pole[9][8], pole[9][9], pole[9][10], pole[9][11], pole[9][12], pole[9][13], pole[9][14], pole[9][15]
, pole[10][0], pole[10][1], pole[10][2], pole[10][3], pole[10][4], pole[10][5], pole[10][6], pole[10][7], pole[10][8], pole[10][9], pole[10][10], pole[10][11], pole[10][12], pole[10][13], pole[10][14], pole[10][15]
, pole[11][0], pole[11][1], pole[11][2], pole[11][3], pole[11][4], pole[11][5], pole[11][6], pole[11][7], pole[11][8], pole[11][9], pole[11][10], pole[11][11], pole[11][12], pole[11][13], pole[11][14], pole[11][15]
, pole[12][0], pole[12][1], pole[12][2], pole[12][3], pole[12][4], pole[12][5], pole[12][6], pole[12][7], pole[12][8], pole[12][9], pole[12][10], pole[12][11], pole[12][12], pole[12][13], pole[12][14], pole[12][15]
, pole[13][0], pole[13][1], pole[13][2], pole[13][3], pole[13][4], pole[13][5], pole[13][6], pole[13][7], pole[13][8], pole[13][9], pole[13][10], pole[13][11], pole[13][12], pole[13][13], pole[13][14], pole[13][15]
, pole[14][0], pole[14][1], pole[14][2], pole[14][3], pole[14][4], pole[14][5], pole[14][6], pole[14][7], pole[14][8], pole[14][9], pole[14][10], pole[14][11], pole[14][12], pole[14][13], pole[14][14], pole[14][15]
, pole[15][0], pole[15][1], pole[15][2], pole[15][3], pole[15][4], pole[15][5], pole[15][6], pole[15][7], pole[15][8], pole[15][9], pole[15][10], pole[15][11], pole[15][12], pole[15][13], pole[15][14], pole[15][15]);

}
else
{
printf("Reseni neexistuje.\n");
}

return 0;
}


Input:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|             h | p   m   o     |     i   k     | n       f   l |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| c   l   g   m | n           e | h   p         | o       d     |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| o             |             d | b             |               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|     p   i   e |     h       g |             m |         b     |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|     c         | h             | n   k       f |     i   g     |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|         h     |     l   p     | i   b   j     |         c     |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| f   a         |     j   g     |             p |               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|         e     |     i       o |         l     | h   p   n     |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| i       d     |         n     | o   a   g   b | l             |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|     f   j   g |         m     |     d   i     |             c |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| l   k         |               | f             |             o |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|               |               |         m     | k           n |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|         n     | b       k     | g       o   d | c   h   i     |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|             o |             l |         n     | m             |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| h   g       f |             j | p             |         e   d |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|               | m   p       f |     c       j | b             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

• I'm understanding this as working but slow.
– user59064
Dec 31, 2014 at 16:22
• The code at paste.ofcode.org is only around 250 lines. Please embed that in your post. It gets put in a scroll box and is reasonably manageable for other users.
– user59064
Dec 31, 2014 at 16:31
• One way to speed up hexadoku is to use bit operations on an array(s) of shorts (a short will hold a flag bit for each possible value) This allows quick elimination of possible matches as well as additional speedups if you operate on 4 shorts at a time for blocks and rows. To prevent redoing ops, you can use 4 64-bit masks to indicate whether it was already done. Probably not needed to get you under 2s, but if you want to learn bitops, its an interesting excercise and can get solve time down to ~0.2s. (hint: to get <0.2s you may need to use some compiler builtins) Jan 3, 2015 at 21:16

A better solver proceeds as follows:

1. Set up 16x16 array of variable length arrays each empty.
2. Fill in the 'givens' by adding the given to the arrays in the relevant locations.
3. Pack the spaces with arrays of all possible values (1 to 16).
4. Raster scan the puzzle looking for singletons and performing annihilations on the 'candidate' arrays in the same column, row or box.
5. Keep doing that until there are no more annihilations.

An easy way of doing that is to just 'remember' if you reduced a 'past' cell to a singleton and re-scan if so.

1. Keep a count of 'singletons' so that when you have 256=16*16 you're done.

If you can't find any more 'easy' annihilations proceed to 'back-tracking':

1. IMPORTANT BIT: Find a cell with the fewest remaining candidates.
2. Clone the whole puzzle, set that cell to one of the possible values
3. Call the solver recursively

Your method is pivoting on an arbitrary cell. You need to find a cell with a small number of candidate values. It's common in problems set for human solvers to find at most one or two recursive steps and then only find they have 1 or 2 candidates.

When you find a solution you can either add it to an array or return it as 'first found'. That's up to you.

Note: incorporation of my comments will speed up the execution (of this code) by a factor of (at least) 6.

My comments marked with with '<--'.

for (l = 0; l < 16; l+=3) <-- this 'for' loop has no effect and can be removed
{
for (i = 0; i < 4 ; i++)
{
for (j = 0; j < 4; j++)
{
for (x = 0; x < 4; x++)
{
for (y = 0; y < 4; y++)
{
if(i==x && j==y) continue;
if ( (pole[i][j] == pole[x][y]) && (pole[i][j] != ' ') && (pole[x][y] != ' ') ) { printf("Nespravny vstup.\n"); return 1; }
}
}
}
}
i+=3; // <-- this has no effect and can be removed
j+=3; // <-- this has no effect and can be removed
x+=3; // <-- this has no effect and can be removed
y+=3; // <-- this has no effect and can be removed
}