A non-volatile semiconductor memory device may include a memory cell array and a controller coupled to the memory cell array. The memory cell array may include first and second memory cells coupled to respective first and second word lines. Each of the first and second memory cells may be configured to be programmed to one of a first, a second, or a third threshold voltage so that the first and second memory cells provide nine different threshold voltage combinations. The controller may be configured to provide a mapping of data of a set of three binary bits providing eight different data combinations to eight of the nine different threshold voltage combinations provided by the first and second memory cells. The controller may be further configured to write data of first, second, and third binary bits to the first and second memory cells by programming each of the first and second memory cells to a respective one of the first, second, or third threshold voltages using the mapping of data. Related methods are also discussed.