Sensor placement is a crucial task for any wireless sensor network (WSN) application. Sensor placement has a direct impact on the efficiency of any WSN application in terms of energy preservation in eliminating redundant transmissions and in terms of coverage of the sensed area. In this work, an advanced sensor placement algorithm which depends on achieving a total coverage with the minimum possible number of sensors is presented. The detection of the sensors is associated to a detection probability matrix in order to reflect different real life scenarios. The algorithm refers to Tabu Search heuristics in order to reduce time and computation complexities. The network is modeled as a grid network in the presence and absence of obstacles. Different experiments are conducted to prove the efficiency of the advanced sensor placement algorithm. Furthermore, when compared with other published work the proposed algorithm achieved a saving of 105 sensors in a network with grid size of 80×80.