URL https://opencores.org/ocsvn/sudoku/sudoku/trunk

Subversion Repositories sudoku

[/] [sudoku/] [trunk/] [c_implementation/] [sudoku.c] - Blame information for rev 3

Details | Compare with Previous | View Log


/* C implementation of sudoku solver.
 *
 * David Sheffield (dsheffield@alumni.brown.edu)
 * September 2013
 *
 * Exact cover using bit vectors with
 * backtracking performed using an
 * explict stack.
 *
 */
 
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
 
inline uint64_t rdtsc(void)
{
  uint32_t hi=0, lo=0;
#ifdef __amd64__
  __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
#endif
  return ( (uint64_t)lo)|( ((uint64_t)hi)<<32 );
}
 
inline uint32_t one_set(uint32_t x)
{
  /* all ones if pow2, otherwise 0 */
  uint32_t pow2 = (x & (x-1));
  uint32_t m = (pow2 == 0);
  return ((~m) + 1) & x;
}
 
inline uint32_t isPow2(uint32_t x)
{
  uint32_t pow2 = (x & (x-1));
  return (pow2 == 0);
}
 
inline uint32_t ln2(uint32_t x)
{
  uint32_t y = 1;
  while(x > 1)
    {
      y++;
      x = x>>1;
    }
  return y;
}
 
 
inline uint32_t count_ones(uint32_t x)
{
#ifdef __GNUC__
  return __builtin_popcount(x);
#else
  uint32_t y = 0;
  for(y=0;x!=0;y++)
    {
      x &= (x-1);
    }
  return y;
#endif
}
 
inline uint32_t find_first_set(uint32_t x)
{
#ifdef __GNUC__
  return __builtin_ctz(x);
#else
  /* copied from the sparc v9 reference manual */
  return count_ones(x ^ (~(-x))) - 1;
#endif
}
 
void sprintf_binary(uint32_t n, char *buf, uint32_t len)
{
  bzero(buf,len);
  uint32_t p = 0;
  while (p<9)
    {
      if (n & 1)
        buf[8-p] = '1';
      else
        buf[8-p] = '0';
      n >>= 1;
      p++;
    }
}
 
void print_board(uint32_t *board)
{
  int32_t i,j;
  char buf[80] = {0};
  for(i=0;i<9;i++)
    {
      for(j=0;j<9;j++)
        {
          /* sprintf_binary(board[i*9+j], buf, 80);
           * printf("%s ", buf); */
          printf("%d ", ln2(board[i*9+j]));
        }
      printf("\n");
    }
  printf("\n");
}
 
int32_t sudoku_norec(uint32_t *board, uint32_t *os);
 
int32_t solve(uint32_t *board, uint32_t *os)
{
  int32_t i,j,idx;
  int32_t ii,jj;
  int32_t ib,jb;
  uint32_t set_row, set_col, set_sqr;
  uint32_t row_or, col_or, sqr_or;
  uint32_t tmp;
  int32_t changed = 0;
 
  do
    {
      changed=0;
      //print_board(board);
      /* compute all positions one's set value */
      for(i = 0; i < 9; i++)
        {
          for(j = 0; j < 9; j++)
            {
              idx = i*9 + j;
              os[idx] = one_set(board[idx]);
            }
        }
 
      for(i = 0; i < 9; i++)
        {
          for(j = 0; j < 9; j++)
            {
              /* already solved */
              if(isPow2(board[i*9+j]))
                continue;
              else if(board[idx]==0)
                return 0;
 
              row_or = set_row = 0;
              for(jj = 0; jj < 9; jj++)
                {
                  idx = i*9 + jj;
                  if(jj == j)
                    continue;
                  set_row |= os[idx];
                  row_or |= board[idx];
                }
              col_or = set_col = 0;
              for(ii = 0; ii < 9; ii++)
                {
                  idx = ii*9 + j;
                  if(ii == i)
                    continue;
                  set_col |= os[idx];
                  col_or |= board[idx];
                }
              sqr_or = set_sqr = 0;
              ib = 3*(i/3);
              jb = 3*(j/3);
              for(ii=ib;ii < ib+3;ii++)
                {
                  for(jj=jb;jj<jb+3;jj++)
                    {
                      idx = ii*9 + jj;
                      if((i==ii) && (j == jj))
                        continue;
                      set_sqr |= os[idx];
                      sqr_or |= board[idx];
                    }
                }
              tmp = board[i*9 + j] & ~( set_row | set_col | set_sqr);
 
              if(tmp != board[i*9 + j])
                {
                  changed = 1;
                }
              board[i*9+j] = tmp;
 
              /* check for singletons */
              tmp = 0;
              tmp = one_set(board[i*9 + j] & (~row_or));
              tmp |= one_set(board[i*9 + j] & (~col_or));
              tmp |= one_set(board[i*9 + j] & (~sqr_or));
              if(tmp != 0 && (board[i*9+j] != tmp))
                {
                  board[i*9+j] = tmp;
                  changed = 1;
                }
            }
        }
 
    } while(changed);
 
  return 0;
}
 
int32_t check_correct(uint32_t *board, uint32_t *unsolved_pieces)
{
  int32_t i,j;
  int32_t ii,jj;
  int32_t si,sj;
  int32_t tmp;
 
  *unsolved_pieces = 0;
  int32_t violated = 0;
 
  uint32_t counts[81];
  for(i=0;i < 81; i++)
    {
      counts[i] = count_ones(board[i]);
      if(counts[i]!=1)
        {
          *unsolved_pieces = 1;
          return 0;
        }
    }
 
 
  /* for each row */
  for(i=0;i<9;i++)
    {
      uint32_t sums[9] = {0};
      for(j=0;j<9;j++)
        {
          if(counts[i*9 +j] == 1)
            {
              tmp =ln2(board[i*9+j])-1;
              sums[tmp]++;
              if(sums[tmp] > 1)
                {
                  //char buf[80];
                  //sprintf_binary(board[i*9+j],buf,80);
                  //printf("violated row %d, sums[%d]=%d, board = %s\n", i, tmp, sums[tmp], buf);
                  //print_board(board);
                  violated = 1;
                  goto done;
                }
            }
        }
    }
  /* for each column */
 
   for(j=0;j<9;j++)
   {
     uint32_t sums[9] = {0};
     for(i=0;i<9;i++)
     {
       if(counts[i*9 +j] == 1)
         {
           tmp =ln2(board[i*9+j])-1;
           sums[tmp]++;
           if(sums[tmp] > 1)
             {
               violated = 1;
               goto done;
               //printf("violated column %d, sums[%d]=%d\n", i, tmp, sums[tmp]);
               //return 0;
             }
         }
     }
   }
 
   for(i=0;i<9;i++)
     {
       si = 3*(i/3);
       for(j=0;j<9;j++)
         {
           sj = 3*(j/3);
           uint32_t sums[9] = {0};
           for(ii=si;ii<(si+3);ii++)
             {
               for(jj=sj;jj<(sj+3);jj++)
                 {
                   if(counts[ii*9 +jj] == 1)
                     {
                       tmp =ln2(board[ii*9+jj])-1;
                       sums[tmp]++;
                       if(sums[tmp] > 1)
                         {
                           violated = 1;
                           goto done;
                         }
                     }
                 }
             }
         }
     }
 
done:
   return (violated == 0);
}
 
uint32_t count_poss(uint32_t *board)
{
  uint32_t i,t;
  uint32_t c=0;
  for(i=0;i<81;i++)
    {
      t = count_ones(board[i]);
      c += (t == 1) ? 0 : t;
    }
  return c;
}
 
inline void find_min(uint32_t *board, int32_t *min_idx, int *min_pos)
{
  int32_t tmp,idx,i,j;
  int32_t tmin_idx,tmin_pos;
 
  tmin_idx = 0;
  tmin_pos = INT_MAX;
  for(idx=0;idx<81;idx++)
    {
      tmp = count_ones(board[idx]);
      tmp = (tmp == 1) ? INT_MAX : tmp;
      if(tmp < tmin_pos)
        {
          tmin_pos = tmp;
          tmin_idx = idx;
        }
    }
  *min_idx = tmin_idx;
  *min_pos = tmin_pos;
}
 
 
int32_t sudoku(uint32_t *board, uint32_t *os, int d)
{
  int32_t rc;
 
  int32_t tmp,min_pos;
  int32_t min_idx;
  int32_t i,j,idx;
 
  uint32_t cell;
  uint32_t old[81];
 
  uint32_t unsolved_pieces = 0;
 
  //printf("%d poss\n", count_poss(board));
 
  solve(board,os);
  rc = check_correct(board, &unsolved_pieces);
 
  if(rc == 1 && unsolved_pieces == 0)
    {
      return 1;
    }
  else if(rc == 0 && unsolved_pieces == 0)
    {
      return -1;
    }
 
  /* find variable to branch on */
  find_min(board, &min_idx, &min_pos);
 
  bzero(os,sizeof(uint32_t)*81);
 
  cell = board[min_idx];
 
  memcpy(old, board, sizeof(uint32_t)*81);
 
  while(cell != 0)
    {
      tmp = find_first_set(cell);
      cell &= ~(1 << tmp);
      board[min_idx] = 1 << tmp;
 
      rc = sudoku(board, os, d+1);
 
      if(rc == 1)
        {
          return 1;
        }
 
      /* restart from previous state */
      memcpy(board,old,sizeof(uint32_t)*81);
    }
 
  /* we went down the wrong branch of the
   * search tree */
  memcpy(board,old,sizeof(uint32_t)*81);
  return -1;
}
 
uint32_t board[81] = {0};
uint32_t os[81] = {0};
 
int main(int argc, char **argv)
{
 
 
  int32_t i=0,d=0j;
  FILE *fp  = 0;
  uint64_t c0 = 0;
  uint32_t rc;
 
  if(argc < 2)
    return -1;
 
  fp = fopen(argv[1], "r");
  assert(fp);
 
  while (i < 81)
    {
      rc = fscanf(fp, "%x", board+i);
      if (rc != 1)
        break;
 
      i++;
    }
  fclose(fp);
 
  //printf("board[0] = %x, board[80] = %x\n", board[0], board[80]);
 
 
 
  c0 = rdtsc();
  sudoku_norec(board, os);
  c0 = rdtsc() - c0;
 
  print_board(board);
  printf("%lu cycles\n", c0);
 
  return 0;
}
 
 
int32_t sudoku_norec(uint32_t *board, uint32_t *os)
{
  int32_t rc;
 
  int32_t tmp,min_pos;
  int32_t min_idx;
  int32_t i,j,idx;
 
  uint32_t cell;
  uint32_t old[81];
 
  uint32_t unsolved_pieces = 0;
  uint32_t *bptr, *nbptr;
 
  int32_t stack_pos = 0;
  int32_t stack_size = (1<<6);
  uint32_t **stack = 0;
 
  stack = (uint32_t**)malloc(sizeof(uint32_t*)*stack_size);
  for(i=0;i<stack_size;i++)
    {
      stack[i] = (uint32_t*)malloc(sizeof(uint32_t)*81);
    }
 
  memcpy(stack[stack_pos++], board, sizeof(uint32_t)*81);
 
  //printf("%d poss\n", count_poss(board));
  while(stack_pos > 0)
    {
      unsolved_pieces = 0;
      bptr = stack[--stack_pos];
 
      bzero(os,sizeof(uint32_t)*81);
      solve(bptr,os);
      rc = check_correct(bptr, &unsolved_pieces);
      /* solved puzzle */
      if(rc == 1 && unsolved_pieces == 0)
        {
          memcpy(board, bptr, sizeof(uint32_t)*81);
          goto solved_puzzle;
        }
      /* traversed to bottom of search tree and
       * didn't find a valid solution */
      if(rc == 0 && unsolved_pieces == 0)
        {
          continue;
        }
 
      find_min(bptr, &min_idx, &min_pos);
      cell = bptr[min_idx];
      while(cell != 0)
        {
          tmp = find_first_set(cell);
          cell &= ~(1 << tmp);
          nbptr = stack[stack_pos];
          stack_pos++;
          memcpy(nbptr, bptr, sizeof(uint32_t)*81);
          nbptr[min_idx] = 1<<tmp;
 
          assert(stack_pos < stack_size);
        }
    }
 solved_puzzle:
 
  for(i=0;i<stack_size;i++)
    {
      free(stack[i]);
    }
  free(stack);
 
  return 1;
}

Browse

Tools

Subversion Repositories sudoku

[/] [sudoku/] [trunk/] [c_implementation/] [sudoku.c] - Blame information for rev 3

Line No.	Rev	Author	Line
1	3	dsheffie	`/* C implementation of sudoku solver.`
2			`*`
3			`* David Sheffield (dsheffield@alumni.brown.edu)`
4			`* September 2013`
5			`*`
6			`* Exact cover using bit vectors with`
7			`* backtracking performed using an`
8			`* explict stack.`
9			`*`
10			`*/`
11
12			`#include <stdint.h>`
13			`#include <stdio.h>`
14			`#include <stdlib.h>`
15			`#include <string.h>`
16			`#include <assert.h>`
17			`#include <limits.h>`
18
19			`inline uint64_t rdtsc(void)`
20			`{`
21			`uint32_t hi=0, lo=0;`
22			`#ifdef __amd64__`
23			`__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));`
24			`#endif`
25			`return ( (uint64_t)lo)\|( ((uint64_t)hi)<<32 );`
26			`}`
27
28			`inline uint32_t one_set(uint32_t x)`
29			`{`
30			`/* all ones if pow2, otherwise 0 */`
31			`uint32_t pow2 = (x & (x-1));`
32			`uint32_t m = (pow2 == 0);`
33			`return ((~m) + 1) & x;`
34			`}`
35
36			`inline uint32_t isPow2(uint32_t x)`
37			`{`
38			`uint32_t pow2 = (x & (x-1));`
39			`return (pow2 == 0);`
40			`}`
41
42			`inline uint32_t ln2(uint32_t x)`
43			`{`
44			`uint32_t y = 1;`
45			`while(x > 1)`
46			`{`
47			`y++;`
48			`x = x>>1;`
49			`}`
50			`return y;`
51			`}`
52
53
54			`inline uint32_t count_ones(uint32_t x)`
55			`{`
56			`#ifdef __GNUC__`
57			`return __builtin_popcount(x);`
58			`#else`
59			`uint32_t y = 0;`
60			`for(y=0;x!=0;y++)`
61			`{`
62			`x &= (x-1);`
63			`}`
64			`return y;`
65			`#endif`
66			`}`
67
68			`inline uint32_t find_first_set(uint32_t x)`
69			`{`
70			`#ifdef __GNUC__`
71			`return __builtin_ctz(x);`
72			`#else`
73			`/* copied from the sparc v9 reference manual */`
74			`return count_ones(x ^ (~(-x))) - 1;`
75			`#endif`
76			`}`
77
78			`void sprintf_binary(uint32_t n, char *buf, uint32_t len)`
79			`{`
80			`bzero(buf,len);`
81			`uint32_t p = 0;`
82			`while (p<9)`
83			`{`
84			`if (n & 1)`
85			`buf[8-p] = '1';`
86			`else`
87			`buf[8-p] = '0';`
88			`n >>= 1;`
89			`p++;`
90			`}`
91			`}`
92
93			`void print_board(uint32_t *board)`
94			`{`
95			`int32_t i,j;`
96			`char buf[80] = {0};`
97			`for(i=0;i<9;i++)`
98			`{`
99			`for(j=0;j<9;j++)`
100			`{`
101			`/* sprintf_binary(board[i*9+j], buf, 80);`
102			`* printf("%s ", buf); */`
103			`printf("%d ", ln2(board[i*9+j]));`
104			`}`
105			`printf("\n");`
106			`}`
107			`printf("\n");`
108			`}`
109
110			`int32_t sudoku_norec(uint32_t board, uint32_t os);`
111
112			`int32_t solve(uint32_t board, uint32_t os)`
113			`{`
114			`int32_t i,j,idx;`
115			`int32_t ii,jj;`
116			`int32_t ib,jb;`
117			`uint32_t set_row, set_col, set_sqr;`
118			`uint32_t row_or, col_or, sqr_or;`
119			`uint32_t tmp;`
120			`int32_t changed = 0;`
121
122			`do`
123			`{`
124			`changed=0;`
125			`//print_board(board);`
126			`/* compute all positions one's set value */`
127			`for(i = 0; i < 9; i++)`
128			`{`
129			`for(j = 0; j < 9; j++)`
130			`{`
131			`idx = i*9 + j;`
132			`os[idx] = one_set(board[idx]);`
133			`}`
134			`}`
135
136			`for(i = 0; i < 9; i++)`
137			`{`
138			`for(j = 0; j < 9; j++)`
139			`{`
140			`/* already solved */`
141			`if(isPow2(board[i*9+j]))`
142			`continue;`
143			`else if(board[idx]==0)`
144			`return 0;`
145
146			`row_or = set_row = 0;`
147			`for(jj = 0; jj < 9; jj++)`
148			`{`
149			`idx = i*9 + jj;`
150			`if(jj == j)`
151			`continue;`
152			`set_row \|= os[idx];`
153			`row_or \|= board[idx];`
154			`}`
155			`col_or = set_col = 0;`
156			`for(ii = 0; ii < 9; ii++)`
157			`{`
158			`idx = ii*9 + j;`
159			`if(ii == i)`
160			`continue;`
161			`set_col \|= os[idx];`
162			`col_or \|= board[idx];`
163			`}`
164			`sqr_or = set_sqr = 0;`
165			`ib = 3*(i/3);`
166			`jb = 3*(j/3);`
167			`for(ii=ib;ii < ib+3;ii++)`
168			`{`
169			`for(jj=jb;jj<jb+3;jj++)`
170			`{`
171			`idx = ii*9 + jj;`
172			`if((i==ii) && (j == jj))`
173			`continue;`
174			`set_sqr \|= os[idx];`
175			`sqr_or \|= board[idx];`
176			`}`
177			`}`
178			`tmp = board[i*9 + j] & ~( set_row \| set_col \| set_sqr);`
179
180			`if(tmp != board[i*9 + j])`
181			`{`
182			`changed = 1;`
183			`}`
184			`board[i*9+j] = tmp;`
185
186			`/* check for singletons */`
187			`tmp = 0;`
188			`tmp = one_set(board[i*9 + j] & (~row_or));`
189			`tmp \|= one_set(board[i*9 + j] & (~col_or));`
190			`tmp \|= one_set(board[i*9 + j] & (~sqr_or));`
191			`if(tmp != 0 && (board[i*9+j] != tmp))`
192			`{`
193			`board[i*9+j] = tmp;`
194			`changed = 1;`
195			`}`
196			`}`
197			`}`
198
199			`} while(changed);`
200
201			`return 0;`
202			`}`
203
204			`int32_t check_correct(uint32_t board, uint32_t unsolved_pieces)`
205			`{`
206			`int32_t i,j;`
207			`int32_t ii,jj;`
208			`int32_t si,sj;`
209			`int32_t tmp;`
210
211			`*unsolved_pieces = 0;`
212			`int32_t violated = 0;`
213
214			`uint32_t counts[81];`
215			`for(i=0;i < 81; i++)`
216			`{`
217			`counts[i] = count_ones(board[i]);`
218			`if(counts[i]!=1)`
219			`{`
220			`*unsolved_pieces = 1;`
221			`return 0;`
222			`}`
223			`}`
224
225
226			`/* for each row */`
227			`for(i=0;i<9;i++)`
228			`{`
229			`uint32_t sums[9] = {0};`
230			`for(j=0;j<9;j++)`
231			`{`
232			`if(counts[i*9 +j] == 1)`
233			`{`
234			`tmp =ln2(board[i*9+j])-1;`
235			`sums[tmp]++;`
236			`if(sums[tmp] > 1)`
237			`{`
238			`//char buf[80];`
239			`//sprintf_binary(board[i*9+j],buf,80);`
240			`//printf("violated row %d, sums[%d]=%d, board = %s\n", i, tmp, sums[tmp], buf);`
241			`//print_board(board);`
242			`violated = 1;`
243			`goto done;`
244			`}`
245			`}`
246			`}`
247			`}`
248			`/* for each column */`
249
250			`for(j=0;j<9;j++)`
251			`{`
252			`uint32_t sums[9] = {0};`
253			`for(i=0;i<9;i++)`
254			`{`
255			`if(counts[i*9 +j] == 1)`
256			`{`
257			`tmp =ln2(board[i*9+j])-1;`
258			`sums[tmp]++;`
259			`if(sums[tmp] > 1)`
260			`{`
261			`violated = 1;`
262			`goto done;`
263			`//printf("violated column %d, sums[%d]=%d\n", i, tmp, sums[tmp]);`
264			`//return 0;`
265			`}`
266			`}`
267			`}`
268			`}`
269
270			`for(i=0;i<9;i++)`
271			`{`
272			`si = 3*(i/3);`
273			`for(j=0;j<9;j++)`
274			`{`
275			`sj = 3*(j/3);`
276			`uint32_t sums[9] = {0};`
277			`for(ii=si;ii<(si+3);ii++)`
278			`{`
279			`for(jj=sj;jj<(sj+3);jj++)`
280			`{`
281			`if(counts[ii*9 +jj] == 1)`
282			`{`
283			`tmp =ln2(board[ii*9+jj])-1;`
284			`sums[tmp]++;`
285			`if(sums[tmp] > 1)`
286			`{`
287			`violated = 1;`
288			`goto done;`
289			`}`
290			`}`
291			`}`
292			`}`
293			`}`
294			`}`
295
296			`done:`
297			`return (violated == 0);`
298			`}`
299
300			`uint32_t count_poss(uint32_t *board)`
301			`{`
302			`uint32_t i,t;`
303			`uint32_t c=0;`
304			`for(i=0;i<81;i++)`
305			`{`
306			`t = count_ones(board[i]);`
307			`c += (t == 1) ? 0 : t;`
308			`}`
309			`return c;`
310			`}`
311
312			`inline void find_min(uint32_t board, int32_t min_idx, int *min_pos)`
313			`{`
314			`int32_t tmp,idx,i,j;`
315			`int32_t tmin_idx,tmin_pos;`
316
317			`tmin_idx = 0;`
318			`tmin_pos = INT_MAX;`
319			`for(idx=0;idx<81;idx++)`
320			`{`
321			`tmp = count_ones(board[idx]);`
322			`tmp = (tmp == 1) ? INT_MAX : tmp;`
323			`if(tmp < tmin_pos)`
324			`{`
325			`tmin_pos = tmp;`
326			`tmin_idx = idx;`
327			`}`
328			`}`
329			`*min_idx = tmin_idx;`
330			`*min_pos = tmin_pos;`
331			`}`
332
333
334			`int32_t sudoku(uint32_t board, uint32_t os, int d)`
335			`{`
336			`int32_t rc;`
337
338			`int32_t tmp,min_pos;`
339			`int32_t min_idx;`
340			`int32_t i,j,idx;`
341
342			`uint32_t cell;`
343			`uint32_t old[81];`
344
345			`uint32_t unsolved_pieces = 0;`
346
347			`//printf("%d poss\n", count_poss(board));`
348
349			`solve(board,os);`
350			`rc = check_correct(board, &unsolved_pieces);`
351
352			`if(rc == 1 && unsolved_pieces == 0)`
353			`{`
354			`return 1;`
355			`}`
356			`else if(rc == 0 && unsolved_pieces == 0)`
357			`{`
358			`return -1;`
359			`}`
360
361			`/* find variable to branch on */`
362			`find_min(board, &min_idx, &min_pos);`
363
364			`bzero(os,sizeof(uint32_t)*81);`
365
366			`cell = board[min_idx];`
367
368			`memcpy(old, board, sizeof(uint32_t)*81);`
369
370			`while(cell != 0)`
371			`{`
372			`tmp = find_first_set(cell);`
373			`cell &= ~(1 << tmp);`
374			`board[min_idx] = 1 << tmp;`
375
376			`rc = sudoku(board, os, d+1);`
377
378			`if(rc == 1)`
379			`{`
380			`return 1;`
381			`}`
382
383			`/* restart from previous state */`
384			`memcpy(board,old,sizeof(uint32_t)*81);`
385			`}`
386
387			`/* we went down the wrong branch of the`
388			`* search tree */`
389			`memcpy(board,old,sizeof(uint32_t)*81);`
390			`return -1;`
391			`}`
392
393			`uint32_t board[81] = {0};`
394			`uint32_t os[81] = {0};`
395
396			`int main(int argc, char **argv)`
397			`{`
398
399
400			`int32_t i=0,d=0j;`
401			`FILE *fp = 0;`
402			`uint64_t c0 = 0;`
403			`uint32_t rc;`
404
405			`if(argc < 2)`
406			`return -1;`
407
408			`fp = fopen(argv[1], "r");`
409			`assert(fp);`
410
411			`while (i < 81)`
412			`{`
413			`rc = fscanf(fp, "%x", board+i);`
414			`if (rc != 1)`
415			`break;`
416
417			`i++;`
418			`}`
419			`fclose(fp);`
420
421			`//printf("board[0] = %x, board[80] = %x\n", board[0], board[80]);`
422
423
424
425			`c0 = rdtsc();`
426			`sudoku_norec(board, os);`
427			`c0 = rdtsc() - c0;`
428
429			`print_board(board);`
430			`printf("%lu cycles\n", c0);`
431
432			`return 0;`
433			`}`
434
435
436			`int32_t sudoku_norec(uint32_t board, uint32_t os)`
437			`{`
438			`int32_t rc;`
439
440			`int32_t tmp,min_pos;`
441			`int32_t min_idx;`
442			`int32_t i,j,idx;`
443
444			`uint32_t cell;`
445			`uint32_t old[81];`
446
447			`uint32_t unsolved_pieces = 0;`
448			`uint32_t bptr, nbptr;`
449
450			`int32_t stack_pos = 0;`
451			`int32_t stack_size = (1<<6);`
452			`uint32_t **stack = 0;`
453
454			`stack = (uint32_t*)malloc(sizeof(uint32_t)*stack_size);`
455			`for(i=0;i<stack_size;i++)`
456			`{`
457			`stack[i] = (uint32_t)malloc(sizeof(uint32_t)81);`
458			`}`
459
460			`memcpy(stack[stack_pos++], board, sizeof(uint32_t)*81);`
461
462			`//printf("%d poss\n", count_poss(board));`
463			`while(stack_pos > 0)`
464			`{`
465			`unsolved_pieces = 0;`
466			`bptr = stack[--stack_pos];`
467
468			`bzero(os,sizeof(uint32_t)*81);`
469			`solve(bptr,os);`
470			`rc = check_correct(bptr, &unsolved_pieces);`
471			`/* solved puzzle */`
472			`if(rc == 1 && unsolved_pieces == 0)`
473			`{`
474			`memcpy(board, bptr, sizeof(uint32_t)*81);`
475			`goto solved_puzzle;`
476			`}`
477			`/* traversed to bottom of search tree and`
478			`* didn't find a valid solution */`
479			`if(rc == 0 && unsolved_pieces == 0)`
480			`{`
481			`continue;`
482			`}`
483
484			`find_min(bptr, &min_idx, &min_pos);`
485			`cell = bptr[min_idx];`
486			`while(cell != 0)`
487			`{`
488			`tmp = find_first_set(cell);`
489			`cell &= ~(1 << tmp);`
490			`nbptr = stack[stack_pos];`
491			`stack_pos++;`
492			`memcpy(nbptr, bptr, sizeof(uint32_t)*81);`
493			`nbptr[min_idx] = 1<<tmp;`
494
495			`assert(stack_pos < stack_size);`
496			`}`
497			`}`
498			`solved_puzzle:`
499
500			`for(i=0;i<stack_size;i++)`
501			`{`
502			`free(stack[i]);`
503			`}`
504			`free(stack);`
505
506			`return 1;`
507			`}`