turn on all the squares

Consider an n by n board. Each square has a pair of co-ordinates ( x,y ) where 1<= x, y <= n. Each square has two states : either "ON" or "OFF". Initially, all the squares are OFF. For a square (i.j), its neighbors are the squares: { (i' , j' ) | 1<= i' , j' <=n; |i-i'| , |j-j'| <=1} . The neighbors of (4,2) in case of n=4 are {(4,1),(4,2),(3,2),(4,3)} . Note that (i, j) is a neighbor of itself. Define the operation toggle (i,j) that toggles the state of square (i ,j)'s neighbors. i.e. if the state is "ON" then it is turned "OFF" and vice versa. Write a program that, given a n by n board off all OFF squares, computes the shortest sequence of toggle operations that turns all the squares ON. If no sequences can turn all the squares "ON", output "No Solution". On addition to that, the solution should contain step by step change of state (shown graphically).
Example Input
2 3
Example Output
(1,1) (1,2) (2,2) (2,1)
(2,2) (1,3) (3,3) (3,1) ( 1,1)
if you have to toggle ( 2,1) then we toggle its neighbors ( 2,2) (2,1) (1,1) (1,3) . The diagonal elements are not considered.

tell me yhe logic for doing this or full solution