====== 01 Intro and Solvability ======
We log on, discuss the rules, answer first questions, create first simple Python program.

Read about [[https://cyber.felk.cvut.cz/study/computer-labs/|computer labs]] how to set-up initial password, access home directory, links to other university services, ...

Reading about Python and programming essentials from the Programming Essentials course. [[https://cw.fel.cvut.cz/wiki/courses/be5b33kui/tutorials/start|Tutorials]] help with setting Python, discuss how to upload homework correctly, and add some class examples and some most frequent Python modules.

After solving the logging issues we will go into Objective Python. We will program the NPuzzle class that would represent the classical n-1 puzzle. Necessary basis will be explained at the first lecture. Python is well on-line documented/discussed, in case of problems, google is your friend.

===== NPuzzle class =====
Besides the constructor ''%%__init__%%'' we will need a few basic method, namely ''reset, visualise, read_tile''. You can create some auxiliary methods/function as it suits to you
<code python>
class NPuzzle:
    '''
    sliding puzzle class of a general size
    https://en.wikipedia.org/wiki/15_puzzle
    '''
    def __init__(self,size):
        '''
        create the list of symbols, typically from 1 to 8 or 15. Empty tile
        is represented by None
        :param size: the board will be size x size,
                     size=3 - 8-puzzle; 4 - 15 puzzle
        '''

    def reset(self):
        '''
        initialize the board by a random shuffle of symbols
        :return: None
        '''
        
    def visualise(self):
        '''
        just print itself to the standard output
        :return: None
        '''

    def read_tile(self, row, col):
        '''
        returns a symbol on row, col position
        :param row: index of the row
        :param column: index of the column
        :return: value of the tile - int 1 to size^2-1, None for empty tile
        The function raises IndexError exception if outside the board
        '''
</code>

===== Bonus Programming task - solvability n-1 puzzle =====

Is the given configuration/state solvable at all? 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>

Basic communication with the NPuzzle object is through the function ''env.read_tile(row, col)'', which returns the value of the tile; ''None'' for empty or an exception is generated  (''IndexError'') in case the index is out of range. An example is provided in ''npuzzle.py''


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

===== Quiz for bonus points =====
  * Solvable and unsolvable puzzle states
  * 0.5 points
  * submit your solution to [[https://cw.felk.cvut.cz/brute/|BRUTE]] **lab01quiz** by February 15, midnight
  * format: text file, photo of your solution on paper, pdf - what is convenient for you
  * solution will be discussed on the next lab
  * quiz assignment: [Students with their family name from A to L should draw 2 unsolvable configurations of 4-1 puzzles (2x2 squares). The other half, students with a family name from M to Z have to draw 2 solvable configurations of 4-1 puzzles.]

>  {{page>courses:be5b33kui:internal:quizzes#4-1-puzzle}}

===== Completeness and optimality =====
We will discuss how to best search when we don't know how far is the goal. What does it mean that a search algorithm is  //complete, optimal//. 

==== Quiz II / Solving together ====

>  {{page>courses:be5b33kui:internal:quizzes#A forgetful traveler }}


===== Mandatory Assignment: searching in a maze =====

This assignment is not meant to be started on the first week, as it will be related to the second and third lecture and labs, but if you can do the bonus N-puzzle assignment fast enough and if you are used to Python, you can start working on the first mandatory assignment.

The full description of the assignment is here [[https://cw.fel.cvut.cz/b202/courses/be5b33kui/labs/search/start| Search (1st assignment)]]. In a maze environment, you will program the algorithm to find the shortest path. Do not forget that the cost of transition between different positions does not have to be the same.