1
\$\begingroup\$

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 isfree(int hexadoku[][16], int radek, int sloupec, int num)
 {
 int rowStart = (radek/4) * 4;
 int colStart = (sloupec/4) * 4;

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

return 1;
}

int napln(int hexadoku[][16], int radek, int sloupec)
{
int i = 0;
if (sloupec >= 16)
{
     sloupec = 0;
     ++radek;
     if (radek >= 16)
     {
         return 1;
     }
}

 if( hexadoku[radek][sloupec] != 0)
    {
        return napln(hexadoku, radek, sloupec+1);
    }
    else
    {
        for(i=0; i<16; ++i)
        {
            if( isfree(hexadoku, radek, sloupec, i+1) )
            {
                hexadoku[radek][sloupec] = i+1;

                int good = napln(hexadoku, radek, sloupec +1);
                if (good)
                {   return 1;
                }
                hexadoku[radek][sloupec] = 0;
            }
        }
    }
    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;

printf("Zadejte hexadoku:\n");
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;
}

int hexadoku[16][16];


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

if( napln(hexadoku, 0, 0) )
{

for (i = 0; i < 16; i++)
    {
    for (j = 0; j < 16; j++)
        {
            switch (hexadoku[i][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             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'm understanding this as working but slow. \$\endgroup\$
    – user59064
    Dec 31 '14 at 16:22
  • \$\begingroup\$ 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. \$\endgroup\$
    – user59064
    Dec 31 '14 at 16:31
  • \$\begingroup\$ 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) \$\endgroup\$ Jan 3 '15 at 21:16
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.