There are many steganalysis methods, which can estimate length of a message embedded in least significant bits. It may be embedded either in spatial domain or in frequency domain. The well known approaches are Chi – Square test, RS steganalysis and Sample Pair steganalysis. Many commercial steganographic programs are based on LSB method. It is important to ensure undetectablity of a hidden message in a carrier. We present an analysis of steganographic security on data hiding approach using eight queen solutions. In this approach, relationship between message bytes and 8-queen solutions is embedded in the cover. Further, we propose a new approach to adjust the statistical properties of the cover image in such a way that the steganalyst may not be able to detect the presence of hidden message. The proposed approach is tested using steganalysis tool STEGEXPOSE and the experimental results found are within acceptable range.