Reduce minesweeper to integer programming

[837951602]

Did you compare current strategy with directly using an IP solver?

[837951602]

Tried http://web.mit.edu/lpsolve/doc/index.htm, modifying its demo.c and run a random 100x100 field. Take 1190417us for solvable case and 2375908us for unsolvable case.

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

#include "lp_lib.h"

#define W 100
#define H 100 

int MineField[H][W];
#define MF_MINE -1
#define MF_SAFE -2
#define MF_DISP -3


int main(void) {
  lprec *lp;
  int colno[8];
  static const REAL ArrOfOnes[8] = {1,1,1,1,1,1,1,1};
  int i, j, k, l, m, n;
  REAL r;
  
  // Init
  srand(1);
  for (i=0; i<H; ++i) for(j=0; j<W; ++j) {
    r = rand() * (1. / RAND_MAX);
    MineField[i][j] = r<(1./3)?MF_MINE:r<(2./3)?MF_SAFE:MF_DISP;
  }
  
  if ((lp = make_lp(0, W*H)) == NULL)
    return -1;
  set_add_rowmode(lp, TRUE);
  for (i=0; i<H; ++i) for(j=0; j<W; ++j) {
	n = i * W + j;
	if(MineField[i][j]!=MF_DISP) {
		set_binary(lp, n, 1);
	} else {
		set_bounds(lp, n, 0, 0);
		m = r = 0;
		for (k=-1; k<2; ++k) if(i+k>=0 && i+k<H) {
		  for (l=-1; l<2; ++l) if(j+l>=0 && j+l<W) if(k || l){
		    colno[m++] = n + k*W + l;
		    r += MineField[i+k][j+l] == MF_MINE;
		  }
		}
		add_constraintex(lp, m, ArrOfOnes, colno, 3, r);
	}
  }
		set_bounds(lp, 5, 0, 0);
  set_add_rowmode(lp, FALSE);
  m = solve(lp);
  printf ("%d %ld\n", m, clock());
  delete_lp(lp);
  
  /*
  for (i=0; i<H; ++i,puts("")) for(j=0; j<W; ++j) {
    printf("%d", -MineField[i][j]);
  }*/
  return 0;
}

[837951602]

Missed mine count. If revealed (2i+1, 2j+1) then 80x80 take 6443627us

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "lp_lib.h"

#define W 80
#define H 80 

int MineField[H][W];
#define MF_MINE ~1
#define MF_SAFE ~0
#define MF_DISP ~8


int main(void) {
  lprec *lp;
  int colno[8];
  static REAL ArrOfOnes[W*H];
  int i, j, k, l, m, n = 0;
  REAL r;
  REAL* rp;
  
  // Init
  srand(1);
  for (i=0; i<H; ++i) for(j=0; j<W; ++j) {
    r = rand() * (1. / RAND_MAX);
    // MineField[i][j] = r<(1./3)?MF_MINE:r<(2./3)?MF_SAFE:MF_DISP;
    MineField[i][j] = i&j&1?MF_DISP:r<0.5?MF_MINE:MF_SAFE;
    ArrOfOnes[i*W+j] = 1;
    n += MineField[i][j] == MF_MINE;
  }
  
  if ((lp = make_lp(0, W*H)) == NULL)
    return -1;
  set_add_rowmode(lp, TRUE);
  add_constraint(lp, ArrOfOnes, 3, n);
  for (i=0; i<H; ++i) for(j=0; j<W; ++j) {
	n = i * W + j;
	if(MineField[i][j]!=MF_DISP) {
		set_binary(lp, n, 1);
	} else {
		set_bounds(lp, n, 0, 0);
		m = r = 0;
		for (k=-1; k<2; ++k) if(i+k>=0 && i+k<H) {
		  for (l=-1; l<2; ++l) if(j+l>=0 && j+l<W) if(k || l){
		    colno[m++] = n + k*W + l;
		    r += MineField[i+k][j+l] == MF_MINE;
		  }
		}
		add_constraintex(lp, m, ArrOfOnes, colno, 3, r);
	}
  }
		//set_bounds(lp, 5, 0, 0);
  set_add_rowmode(lp, FALSE);
  m = solve(lp);
  printf ("%d %ld %d\n", m, clock(), get_ptr_primal_solution(lp, &rp));
  m = solve(lp);
  printf ("%d %ld %d\n", m, clock(), get_ptr_primal_solution(lp, &rp));
  // delete_lp(lp);
  
  for (i=0; i<H; ++i,puts("")) for(j=0; j<W; ++j) {
    printf("%d", ~MineField[i][j]);
  }puts("");
  
  n = get_Nrows(lp);
  for (i=0; i<H; ++i,puts("")) for(j=0; j<W; ++j) {
    printf("%d", (int)rp[i*W+j+n]);
  }puts("");
  
  
  return 0;
}