Stage 1 solver

#include <stdio.h>

/* http://puzzling.stackexchange.com/q/12624/40 */

#define BEG 0
#define ADD 1
#define SUB 2
#define MUL 3
#define END 4

int ops[16] = { BEG, MUL, SUB, SUB,
                SUB, ADD, MUL, MUL,
                SUB, ADD, ADD, SUB,
                ADD, MUL, ADD, END };
int val[16] = {  5,   3,   4,   3,
                 8,   4,   7,   6,
                 3,   9,   8,   1,
                 5,   2,   1,   0  };
int nhb[16][8] = { { 1, 4, 5,-1,-1,-1,-1,-1 },   /* A */
                   { 0, 2, 4, 5, 6,-1,-1,-1 },   /* B */
                   { 1, 3, 5, 6, 7,-1,-1,-1 },   /* C */
                   { 2, 6, 7,-1,-1,-1,-1,-1 },   /* D */
                   { 0, 1, 5, 8, 9,-1,-1,-1 },   /* E */
                   { 0, 1, 2, 4, 6, 8, 9,10 },   /* F */
                   { 1, 2, 3, 5, 7, 9,10,11 },   /* G */
                   { 2, 3, 6,10,11,-1,-1,-1 },   /* H */
                   { 4, 5, 9,12,13,-1,-1,-1 },   /* I */
                   { 4, 5, 6, 8,10,12,13,14 },   /* J */
                   { 5, 6, 7, 9,11,13,14,15 },   /* K */
                   { 6, 7,10,14,15,-1,-1,-1 },   /* L */
                   { 8, 9,13,-1,-1,-1,-1,-1 },   /* M */
                   { 8, 9,10,12,14,-1,-1,-1 },   /* N */
                   { 9,10,11,13,15,-1,-1,-1 },   /* O */
                   {10,11,14,-1,-1,-1,-1,-1 } }; /* P */
int viz[16] = { 0 };

int findpath(int cur_cell, int step_num, int score, int target_score) {
  int i, c;
  viz[cur_cell] = step_num++;
  for (i=0; i<8 && (c=nhb[cur_cell][i])>=0; i++) {
    if (!viz[c]) {
      switch(ops[c]) {
        case END:
          if (score==target_score) {
            viz[c] = step_num;
            return 1;
          }
          else return 0;
        case MUL:
          viz[c] = step_num;
          if (findpath(c,step_num,score * val[c],target_score)) return 1;
          break;
        case SUB:
          viz[c] = step_num;
          if (findpath(c,step_num,score - val[c],target_score)) return 1;
          break;
        case ADD:
          viz[c] = step_num;
          if (findpath(c,step_num,score + val[c],target_score)) return 1;
          break;
        default:
          puts("WTFIGOH?");
      }
      viz[c] = 0;
    }
  }
  return 0;
}



int main() {
  int targets[8] = { 1600, 1800, 1900, 2300, 2400, 3600, 4500, 5000 };
  int t, i;
  for (t=0; t<8; t++) {
    for (i=0; i<16; i++) viz[i] = 0;
    if (findpath(0, 1, 5, targets[t])) {
      printf("%d: L=%d\n",targets[t],viz[15]);
      for (i=0; i<16; i++) {
        printf("%2d ",viz[i]);
        if ((i&3)==3) putchar('\n');
      }
      putchar('\n');
    }
    else printf("%d: No solution",targets[t]);
  }
  return 0;
}