====== 02 Solvability ======

===== programming task - solvability n-1 puzzle =====
Is the given configuration/state solvable at all? The actual algorithm will be explained at the second lecture. The essential pieces of implementation will be shown live during the computer lab. You can use also the code from {{ :courses:b3b33kui:cviceni:program_po_tydnech:npuzzle.py |}} and compare it to your solution of ''npuzzle.py''.

The task is to implement a method ''is_solvable(env)'', which decides whether a given ''env'' (NPuzzle instance) is solvable or not. Implement the function in a module named ''solvability_check.py'' and upload it to [[https://cw.felk.cvut.cz/brute/|BRUTE]]. A correct solution is worth 2 points.

Example structure of (''solvability_check.py''):
<code python>
import npuzzle

def is_solvable(env):
    '''
    True or False?
    '''
    # your code comes here

if __name__=="__main__": # testing suite
    env = npuzzle.NPuzzle(3) # instance of NPuzzle class
    env.reset()              # random shuffle
    env.visualise()          # just to show the board
    # just check
    print(is_solvable(env))  # should output True or False
</code>



When done, upload to the [[https://cw.felk.cvut.cz/brute|BRUTE]]

===== Extra =====
A link to the [[http://tristanpenman.com/demos/n-puzzle/|N-Puzzle solver]].