consider the following list 4 1 2 0 5 3 it represents onestate of the 5 puzzle a sim 4947109

Consider the following list (4 1 2 0 5 3). It represents onestate of the 5-puzzle (a simplification of the 8-puzzle — seetextbook, page 63 for a description of 8 puzzle), namely —————– | 4 | 1 | 2 | —————– | 0 | 5 | 3 | —————–The puzzle consists of 5 tiles, numbered from 1 to 5, and an “empty”tile (numbered 0 for convinience). By sliding tiles one at a time into the empty tile, the tiles can be redistributed. The goal is toreach the following configuration: —————– | 1 | 2 | 3 | —————– | 4 | 5 | 0 | —————–Moving a tile up, down, left or right can be viewed as moving the empty tile down, up, right or left, respectively. Thus, instead ofmoving 5 individual tiles, we can only consider the movements of theempty tile. The problem is to find the sequence of moves that takes the puzzle from its initial state to the goal state. To solve this problem, we have to write a function GET-NEW-STATES which returns all possible movements of the empty tile for each state. Example: * (get-new-states ‘(4 1 2 5 0 3)) ((4 1 2 5 3 0) (4 1 2 0 5 3) (4 0 2 5 1 3)) | | | move 0 move 0 move 0 up to the right to the leftWrite GET-NEW-STATES to implement all possible movements of theempty tile for a given state. I’ll start it for you:(defun get-new-states (state) (setf new-states ‘()) (cond ((= 0 (first state)) (setf new-states ……….)) ((= 0 (second state)) (setf new-states ………)) ….. ((= 0 (sixth state)) (setf new-states ……….)))) . . .