Lights Off

#include <ncurses.h>
#include <vector>
using std::vector;

#define WID 5
#define HGT 5

bool grid[HGT][WID];

void drawgrid(int x, int y) {
  for (int i = 0; i < HGT; ++i)
  for (int j = 0; j < WID; ++j)
    mvprintw(y+i,x+j,grid[i][j]?"#":" ");
}

void getgrid() {
  for (int i = 0; i < HGT; ++i)
  for (int j = 0; j < WID; ++j) {
    move(i,j);
    char c = getch();
    grid[i][j] = (c == '1' || c == 'x' || c == 'X');
    clear();
    drawgrid(0,0);
  }
}

struct coord { int x,y; coord(int xx, int yy): x(xx), y(yy) {} };
typedef vector<coord> sv;

void doXOR(bool g[HGT][WID], const coord &c) {
  g[c.y][c.x] ^= 1;
  if (c.x > 0) g[c.y][c.x - 1] ^= 1;
  if (c.x < WID-1) g[c.y][c.x + 1] ^= 1;
  if (c.y > 0) g[c.y - 1][c.x] ^= 1;
  if (c.y < HGT-1) g[c.y + 1][c.x] ^= 1;
}

bool solution(sv &s) {
  bool sgrid[5][5];
  for (int i = 0; i < HGT; ++i)
  for (int j = 0; j < WID; ++j)
    sgrid[i][j] = grid[i][j];
  for (size_t i = 0; i < s.size(); ++i)
    doXOR(sgrid,s[i]);
  for (int i = 0; i < HGT; ++i)
  for (int j = 0; j < WID; ++j)
    if (sgrid[i][j]) return false;
  return true;
}

void nextsolution(sv &s, size_t p) {
  if (s[p].x < WID-1) ++s[p].x;
  else {
    s[p].x = 0;
    if (s[p].y < HGT-1) ++s[p].y;
    else {
      s[p].y = 0;
      if (s.size() > p+1)
        nextsolution(s, p+1);
      else {
        s.push_back(coord(0,0));
        printf("Need at least %lu clicks...\n", s.size());
      }
    }
  }
}

#define METHOD 2

void printsolution() {
  sv s;

  if (METHOD == 1) {
    s.push_back(coord(0,0));
    while (!solution(s)) {
      nextsolution(s,0);
      if (s.size() > WID*HGT) {
        printf("No solution");
        return;
      }
    }
  }

  bool sol[WID][HGT];
  for (size_t x = 0; x < WID; ++x)
  for (size_t y = 0; y < HGT; ++y)
    sol[x][y] = 0;

  if (METHOD == 2) {
    for (long si = 0; si < (1L << WID*HGT); ++si) {
      s.clear();
      for (long i = 1, i2 = 0; i <= si; i <<= 1, ++i2)
        if (si & i)
          s.push_back(coord(i2 % WID, i2 / WID));
      if (solution(s)) break;
      if (!(si & 0xFFFFF))
        printf("Attempting solution %ld\n", si);
    }
  }

  for (size_t i = 0; i < s.size(); ++i)
    sol[s[i].x][s[i].y] = 1;
  for (int y = 0; y < HGT; ++y) {
    for (int x = 0; x < WID; ++x)
      putc(sol[x][y]? 'X' : ' ', stdout);
    putc('\n', stdout);
  }
}

int main() {
  initscr();
  timeout(-1);
  getgrid();
  endwin();
  printf("Solution:\n");
  printsolution();
  printf("Thanks for playing\n");
  return 0;
}