When you're solving the sliding cars puzzle as a person you're not thinking of graphs. The experience of solving OP's puzzle is entirely different from the one you mention. In theory you could stop, write down the underlying graph representation and solve it that way I suppose. Does anyone do that though?