Minimizing number of field lamps

This program attempts to solve the following challenge:


There is a 2D grid of cells containing N lamps. Each lamp illuminates its own cell as well as its eight neighbours. How many lamps can you possibly remove such that each cell that was originally illuminated remains illuminated?

My code:

```
import java.util.*;

class test
{
public static void main(String[] ar)
{
int use = 0;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the dimensions: ");
int a = sc.nextInt();
int b = sc.nextInt();
int[][] f = new int[a][b];
System.out.print("Enter the no. of lamps: ");
int n = sc.nextInt();
int[][] l = new int[n][2];
//System.out.print("Enter the coordinates : ");
for(int i = 0; i < n; i++)
{
int t1,t2;
do
{
t1 = l[i][0] = (int)(Math.random()*a);
t2 = l[i][1] = (int)(Math.random()*b);
f[t1][t2] = 1;
}while(f[t1][t2] == 0);
}
print(f);
light(f);
for(int i = 0; i < l.length; i++)
{
int[][] f1 = new int[a][b];
for(int j = 0; j < l.length; j++)
{
if(i == j)
continue;
int x = l[j][0];
int y = l[j][1];
if(x < 0)
continue;
f1[x][y] = 1;
}
light(f1);
if(!same(f,f1))
use++;
else
{
l[i][0] = -1;
l[i][1] = -1;
}
}
System.out.println("Usefull : " + use);

}

public static boolean same(int[][] a, int[][] b)
{
for(int i = 0; i < a.length; i++)
{
for(int j = 0; j < a[i].length ; j++)
{
if(a[i][j] != b[i][j])
return false;
}
}
return true;
}

Your algorithm is faulty, because it only tries to eliminate redundant lamps in the order in which they were installed.

Consider a 1 × 9 array with 7 initial lamps L0 … L6 at positions 2 … 8.

Your algorithm would first eliminate L0 at position 5, then L1 at position 4. It would consider L2 and L3 essential. Then it would eliminate L4 at position 7. L5 and L6 would be essential. Total lamps eliminated: three.

An optimal solution would eliminate four lamps at positions 3, 4, 6, 7.

StackExchange Code Review Q#38332, answer score: 7