Untitled9.ipynb

Untitled9.ipynb

{
  "cells": [
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "Nc = 3; Nr = 3\n\nboard = (reshape([i for i in 1:Nc * Nr], Nr, Nc))\ncompletion = collect(board)",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 9,
          "data": {
            "text/plain": "3×3 Array{Int64,2}:\n 1  4  7\n 2  5  8\n 3  6  9"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "function shuffle1(board = board)\n    i = rand(1:Nc * Nr - 2)\n    j = rand(i + 1:Nc * Nr - 1)\n    board[i], board[j] = board[j], board[i]\nend\nfunction shufflen(n = 2Nc * 2Nr, board = board)\n    for _ = 1:n; shuffle1(board) end\nend",
      "execution_count": 2,
      "outputs": [
        {
          "data": {
            "text/plain": "shufflen (generic function with 3 methods)"
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "shufflen()\nboard",
      "execution_count": 17,
      "outputs": [
        {
          "data": {
            "text/plain": "3×3 Array{Int64,2}:\n 6  3  8\n 2  4  1\n 7  5  9"
          },
          "execution_count": 17,
          "metadata": {},
          "output_type": "execute_result"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "board = [\n    6 3 8\n    2 4 1\n    7 5 9\n]",
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 10,
          "data": {
            "text/plain": "3×3 Array{Int64,2}:\n 6  3  8\n 2  4  1\n 7  5  9"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "function findblank(board)\n    for posx in 1:lastindex(board[:,1]), posy in 1:lastindex(board[1,:])\n        board[posx, posy] == lastindex(board) && return posx, posy\n    end\nend\n\nfunction slidefromxplus1!(board, posx, posy)\n    board[posx, posy], board[posx + 1, posy] = board[posx + 1, posy], board[posx, posy]\nend\n\nfunction slidefromxminus1!(board, posx, posy)\n    board[posx, posy], board[posx - 1, posy] = board[posx - 1, posy], board[posx, posy]\nend\n\nfunction slidefromyplus1!(board, posx, posy)\n    board[posx, posy], board[posx, posy + 1] = board[posx, posy + 1], board[posx, posy]\nend\n\nfunction slidefromyminus1!(board, posx, posy)\n    board[posx, posy], board[posx, posy - 1] = board[posx, posy - 1], board[posx, posy]\nend",
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 2,
          "data": {
            "text/plain": "slidefromyminus1! (generic function with 1 method)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "function solvebyiddfs1(subboard, blankposx, blankposy, depth, atthebottom, prev, completion = completion, board = board)\n    depth == 0 && return atthebottom(subboard, blankposx, blankposy, completion)\n\n    if prev ≠ :xplus && blankposx > 1\n        slidefromxminus1!(subboard, blankposx, blankposy)\n        mayberet = solvebyiddfs1(subboard, blankposx - 1, blankposy, depth - 1, atthebottom, :xminus, completion)\n        slidefromxplus1!(subboard, blankposx - 1, blankposy)\n        mayberet == [] || return [[collect(board)]; mayberet]\n    end\n    if prev ≠ :xminus && blankposx < lastindex(subboard[:,1])\n        slidefromxplus1!(subboard, blankposx, blankposy)\n        mayberet = solvebyiddfs1(subboard, blankposx + 1, blankposy, depth - 1, atthebottom, :xplus, completion)\n        slidefromxminus1!(subboard, blankposx + 1, blankposy)\n        mayberet == [] || return [[collect(board)]; mayberet]\n    end\n    if prev ≠ :yplus && blankposy > 1\n        slidefromyminus1!(subboard, blankposx, blankposy)\n        mayberet = solvebyiddfs1(subboard, blankposx, blankposy - 1, depth - 1, atthebottom, :yminus, completion)\n        slidefromyplus1!(subboard, blankposx, blankposy - 1)\n        mayberet == [] || return [[collect(board)]; mayberet]\n    end\n    if prev ≠ :yminus && blankposy < lastindex(subboard[1,:])\n        slidefromyplus1!(subboard, blankposx, blankposy)\n        mayberet = solvebyiddfs1(subboard, blankposx, blankposy + 1, depth - 1, atthebottom, :yplus, completion)\n        slidefromyminus1!(subboard, blankposx, blankposy + 1)\n        mayberet == [] || return [[collect(board)]; mayberet]\n    end\n\n    return []\nend\n",
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 3,
          "data": {
            "text/plain": "solvebyiddfs1 (generic function with 3 methods)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "function atthebottom(subboard, blankposx, blankposy, completion)\n    if subboard == completion\n        [collect(board)]\n    else\n        []\n    end\nend",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 4,
          "data": {
            "text/plain": "atthebottom (generic function with 1 method)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "function atthebottomreducing(subboard, blankposx, blankposy, completion)\n    if length(subboard[:,1]) ≤ 2 && length(subboard[1,:]) ≤ 2\n        solvebyiddfs(atthebottom, subboard, blankposx, blankposy, completion)\n    else\n        reduce = false\n        if length(subboard[:,1]) > 2 && subboard[1,:] == completion[1,:]\n            subboard, completion = @views subboard[2:end,:], completion[2:end,:]\n            blankposx -= 1\n            reduce = true\n        end\n        if length(subboard[1,:]) > 2 && subboard[:,1] == completion[:,1]\n            subboard, completion = @views subboard[:,2:end], completion[:,2:end]\n            blankposy -= 1\n            reduce = true\n        end\n        \n        if reduce\n            solvebyiddfs(atthebottomreducing, subboard, blankposx, blankposy, completion)\n        else\n            []\n        end\n    end\nend\n",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 5,
          "data": {
            "text/plain": "atthebottomreducing (generic function with 1 method)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "function solvebyiddfs(atthebottom, board = board, blankposx = lastindex(@view(board[:,1])), blankposy = lastindex(@view(board[1,:])), completion = completion)\n    i = 0\n    while true\n        ret = solvebyiddfs1(board, blankposx, blankposy, i, atthebottom, :nomove, completion)\n        ret ≠ [] && return ret\n        i += 1\n    end\nend",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 6,
          "data": {
            "text/plain": "solvebyiddfs (generic function with 5 methods)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "@time solvebyiddfs(atthebottom)",
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": " 27.142626 seconds (90.60 M allocations: 7.564 GiB, 10.23% gc time)\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "execution_count": 13,
          "data": {
            "text/plain": "29-element Array{Array{Int64,2},1}:\n [6 3 8; 2 4 1; 7 5 9]\n [6 3 8; 2 4 1; 7 9 5]\n [6 3 8; 2 9 1; 7 4 5]\n [6 9 8; 2 3 1; 7 4 5]\n [9 6 8; 2 3 1; 7 4 5]\n [2 6 8; 9 3 1; 7 4 5]\n [2 6 8; 7 3 1; 9 4 5]\n [2 6 8; 7 3 1; 4 9 5]\n [2 6 8; 7 9 1; 4 3 5]\n [2 9 8; 7 6 1; 4 3 5]\n [2 8 9; 7 6 1; 4 3 5]\n [2 8 1; 7 6 9; 4 3 5]\n [2 8 1; 7 9 6; 4 3 5]\n ⋮\n [2 8 1; 4 7 9; 3 5 6]\n [2 8 1; 4 9 7; 3 5 6]\n [2 9 1; 4 8 7; 3 5 6]\n [2 1 9; 4 8 7; 3 5 6]\n [2 1 7; 4 8 9; 3 5 6]\n [2 1 7; 4 9 8; 3 5 6]\n [2 1 7; 9 4 8; 3 5 6]\n [9 1 7; 2 4 8; 3 5 6]\n [1 9 7; 2 4 8; 3 5 6]\n [1 4 7; 2 9 8; 3 5 6]\n [1 4 7; 2 5 8; 3 9 6]\n [1 4 7; 2 5 8; 3 6 9]"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "@time solvebyiddfs(atthebottomreducing)",
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "text": "  0.036326 seconds (153.37 k allocations: 14.672 MiB)\n",
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "execution_count": 14,
          "data": {
            "text/plain": "31-element Array{Array{Int64,2},1}:\n [6 3 8; 2 4 1; 7 5 9]\n [6 3 8; 2 4 1; 7 9 5]\n [6 3 8; 2 9 1; 7 4 5]\n [6 9 8; 2 3 1; 7 4 5]\n [9 6 8; 2 3 1; 7 4 5]\n [2 6 8; 9 3 1; 7 4 5]\n [2 6 8; 3 9 1; 7 4 5]\n [2 6 8; 3 1 9; 7 4 5]\n [2 6 9; 3 1 8; 7 4 5]\n [2 9 6; 3 1 8; 7 4 5]\n [2 1 6; 3 9 8; 7 4 5]\n [2 1 6; 3 4 8; 7 9 5]\n [2 1 6; 3 4 8; 9 7 5]\n ⋮\n [1 9 4; 2 8 6; 3 7 5]\n [1 8 4; 2 9 6; 3 7 5]\n [1 8 4; 2 7 6; 3 9 5]\n [1 8 4; 2 7 6; 3 5 9]\n [1 8 4; 2 7 9; 3 5 6]\n [1 8 4; 2 9 7; 3 5 6]\n [1 9 4; 2 8 7; 3 5 6]\n [1 4 9; 2 8 7; 3 5 6]\n [1 4 7; 2 8 9; 3 5 6]\n [1 4 7; 2 9 8; 3 5 6]\n [1 4 7; 2 5 8; 3 9 6]\n [1 4 7; 2 5 8; 3 6 9]"
          },
          "metadata": {}
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "julia-1.5",
      "display_name": "Julia 1.5.3",
      "language": "julia"
    },
    "language_info": {
      "file_extension": ".jl",
      "name": "julia",
      "mimetype": "application/julia",
      "version": "1.5.3"
    },
    "gist": {
      "id": "",
      "data": {
        "description": "Untitled9.ipynb",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}