CodingAI4-student-code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code for CodingAI Lesson 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching Problems and how to solve them"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 6):\n",
    "    for j in range(1, 6):\n",
    "        print(i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 10):          # by our reasoning range(1, 3) is enough for first digit\n",
    "    for j in range(1, 10):\n",
    "        for k in range(1, 10):\n",
    "            # TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sudoku Solver part I"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "d = 4   \n",
    "\n",
    "def gen_puzzle():\n",
    "    seedp = [4, 3, 1, 2, 2, 1, 4, 3, 1, 2, 3, 4, 3, 4, 2, 1]\n",
    "    permu = list(range(1, 5))\n",
    "    random.shuffle(permu)\n",
    "    nrm = random.randint(7, 11)\n",
    "    indices = random.sample(list(range(16)), nrm)\n",
    "    newp = [0 if i in indices else permu[v-1] for i, v in enumerate(seedp) ]\n",
    "    return newp\n",
    "     \n",
    "\n",
    "def show(puzzle):\n",
    "    print('-------')\n",
    "    for i in range(8):          \n",
    "        if i % 2 == 0:\n",
    "            print('|', end='')\n",
    "        print(puzzle[i], end='')\n",
    "        if i % 4 == 3:\n",
    "            print('|', end='')   \n",
    "            print()\n",
    "    print('-------')\n",
    "    for i in range(8, 16):         \n",
    "        if i % 2 == 0:\n",
    "            print('|', end='')\n",
    "        print(puzzle[i], end='')\n",
    "        if i % 4 == 3:\n",
    "            print('|', end='')   \n",
    "            print()\n",
    "    print('-------')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Activity 1\n",
    "p = gen_puzzle()\n",
    "print(p)\n",
    "show(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Task 1. Write a function called is_repeated, that takes a list as input, called x. Use a for loop to go over all the elements of x and returns True if any element is repeated. Otherwise, return False. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_repeated(x):\n",
    "    return False\n",
    "    # create an empty list name appeared\n",
    "    # loop through the elements of x\n",
    "        # if the number is not in appeared\n",
    "            # WHAT TO DO?\n",
    "        # else:\n",
    "            # WHAT TO DO?\n",
    "    # WHAT TO DO?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Task 1: Modify your is_repeated() so that the existing IF block is triggered only when the number is > 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# modified version of is_repeated()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(is_repeated([0,1,2,1]))    # should output True\n",
    "print(is_repeated([0,0,4,3]))    # should output False\n",
    "print(is_repeated([4,1,2,4]))    # should output True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Task 2. How to use is_repeated() to check if Rule R is violated?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# How to check Rule R is violated for row 0\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Task 3. How would use the is_repeated() function to check if Rule C is violated?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# How to check Rule C is violated for column 0\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Task 4. How would use the is_repeated() function to check if Rule B is violated?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# How to check Rule B is violated for top left block\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i, v in enumerate([0, 10, 13, 20]):\n",
    "    print(i, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_blank_pos(p):\n",
    "    \"\"\" return list of positions that need to be filled \"\"\"\n",
    "    blank_pos = []\n",
    "    for i, v in enumerate(p):\n",
    "        if v == 0:\n",
    "            blank_pos.append(i)\n",
    "    return blank_pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = [0, 1, 0, 0, 0, 3, 0, 0, 0, 2, 0, 4, 0, 0, 3, 2]\n",
    "get_blank_pos(p) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sudoku Solver Part II: the backtracking algorithm  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def backtrack4(p):\n",
    "    \"\"\" Solve 4x4 Sudoku by back-tracking \"\"\"\n",
    "  \n",
    "    blanks = get_blank_pos(p)\n",
    "    nsteps = len(blanks)\n",
    "    cand_gen = [1]*nsteps\n",
    "    \n",
    "    walk = 0        # the \"ring number\" we are currently testing\n",
    "    found = False\n",
    "    counter = 0     # counting total # of trials \n",
    "    print(p)\n",
    "    print('Begin solving..')\n",
    "    \n",
    "    while not found:\n",
    "        counter += 1\n",
    "        k = blanks[walk]\n",
    "        p[k] = cand_gen[walk]\n",
    "        this_step = True    # is this step ok?\n",
    "        \n",
    "        # check row/column repeat conditions \n",
    "        row = k // d\n",
    "        col = k % d\n",
    "        if is_repeated(p[d*row:d*(1+row)]) or is_repeated(p[col::d]):\n",
    "            this_step = False\n",
    "        else:\n",
    "            # check block repeat conditions\n",
    "            if k in [0,1,4,5]:\n",
    "                psub = [p[v] for v in [0,1,4,5]]\n",
    "            elif k in [2,3,6,7]:\n",
    "                psub = [p[v] for v in [2,3,6,7]]\n",
    "            elif k in [8,9,12,13]:\n",
    "                psub = [p[v] for v in [8,9,12,13]]\n",
    "            else: #if k in [10,11,14,15]:\n",
    "                psub = [p[v] for v in [10,11,14,15]]\n",
    "                \n",
    "            if is_repeated(psub):\n",
    "                this_step = False\n",
    "\n",
    "        print(p)\n",
    "        print(this_step)\n",
    "        if this_step:\n",
    "            if walk == nsteps -1:\n",
    "                found = True\n",
    "                print('Solution found in iterations =', counter)\n",
    "                show(p)    \n",
    "            else:\n",
    "                walk += 1\n",
    "        else:\n",
    "            while cand_gen[walk] == d:       \n",
    "                p[blanks[walk]] = 0             \n",
    "                cand_gen[walk] = 1\n",
    "                walk -= 1\n",
    "            cand_gen[walk] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Activity 3         \n",
    "p = gen_puzzle()\n",
    "backtrack4(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# puzzle from Activity 2\n",
    "p = [0, 1, 0, 0, 0, 3, 0, 0, 0, 2, 0, 4, 0, 0, 3, 2]\n",
    "backtrack4(p)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}