Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@ttatsf(tatsuo fukuchi)

Elm0.19.1 : 絶対解ける8パズルを Elm で作ってみた

Last updated at Posted at 2020-05-11

元ネタを遊んでみて、ああこんなやりかたをするんだと勉強になったので、良さそうだけどあまりいじってない Elm で似たようなのを作ってみました。
こんなやつです。puzzle8
大体の仕組みは元記事からいただいて、解けるお題だけを出題する部分だけオリジナルです。
jsでやってみた版はこちら。

ソースコード

index.html
<!DOCTYPE html>
<html lang="ja">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>puzzle</title>
    <link rel="stylesheet" href="style.css">
    <script src="elm.js"></script>
</head>
<body>
    <main></main>
    <script type="text/javascript">
        Elm.Main.init({ node: document.querySelector('main') });
    </script>  
</body>
</html>
style.css
body {
    height: 100vh;
    display: grid;
    justify-content: center;
    align-items: center;
}
.panel {
    width: 300px;
    display: grid;
    grid-template-columns: repeat(3, 1fr);
    grid-template-rows: repeat(3, 1fr);
    grid-column-gap: 2px;
    grid-row-gap: 2px;
}

.tile {
    line-height: 100px;
    text-align: center;
    border: 1px solid #333;
    border-radius: 5px;
    font-size: 26px;
    cursor: pointer;
    transition-duration:0.2s;
}
.tile:hover{
  border:none;
}

.tile_no_0 {
    background: rgb(247, 200, 200);
}
.tile_no_1 {
    background: rgb(254, 255, 201);
}
.tile_no_2 {
    background: rgb(207, 255, 195);
}
.tile_no_3 {
    background: rgb(200, 238, 247);
}
.tile_no_4 {
    background: rgb(238, 200, 247);
}
.tile_no_5 {
    background: rgb(200, 205, 247);
}
.tile_no_6 {
    background: rgb(255, 197, 164);
}
.tile_no_7 {
    background: rgb(135, 253, 106);
}
.tile_no_8 {
    background: rgb(250, 140, 226);
}
.tile_no_space {
    background: rgb(228, 228, 228);
}

.reset {
    width: 300px;
    text-align: center;
    cursor: pointer;
    background: rgb(255, 146, 146);
    padding: 10px 0;
    border-bottom: 3px solid rgb(185, 104, 104);
    margin-top: 30px;
    font-size: 16px;
}
.reset:active {
    transform: translateY(3px);
    border: none;
}
.reset:focus {
    outline: none;
}
Main.elm
module Main exposing (main)

-- import Array exposing (Array)

import Arithmetic exposing (isEven)
import Browser
import Html exposing (..)
import Html.Attributes exposing (..)
import Html.Events exposing (..)
import List
import List.Extra
import Maybe
import Random
import Random.List



-- MAIN


main : Program () Model Msg
main =
    Browser.element
        { init = init
        , view = view
        , update = update
        , subscriptions = subscriptions
        }



-- MODEL


type alias Model =
    { tiles : List Int
    }


init : () -> ( Model, Cmd Msg )
init _ =
    ( Model solved
    , Random.generate NewOrder <| Random.List.shuffle solved
    )


solved =
    [ 1, 2, 3, 4, 5, 6, 7, 8, spaceValue ]


spaceValue =
    9


defaultSpaceIndex =
    8


matrixSize =
    3



-- UPDATE


type Msg
    = Reset
    | NewOrder (List Int)
    | Click Int


update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        Reset ->
            ( model
            , Random.generate NewOrder <| Random.List.shuffle solved
            )

        NewOrder newOrder ->
            ( Model  <| solvabled <| newOrder
            , Cmd.none
            )

        Click value ->
            ( { model | tiles = model.tiles |> moveBy value }
            , Cmd.none
            )


solvabled : List Int -> List Int
solvabled list =
    if isSolvable list then
        list

    else if List.member (indexOf spaceValue list) [ 0, 1 ] then
        swap 2 3 list

    else
        swap 0 1 list


swap : Int -> Int -> List Int -> List Int
swap a b list =
    List.Extra.swapAt a b list


isSolvable : List Int -> Bool
isSolvable list =
    exchangingParity list == spaceMovementParity list


indexOf : Int -> List Int -> Int
indexOf value list =
    Maybe.withDefault -1 <| List.Extra.elemIndex value list


type Parity
    = Odd
    | Even


inverted : Parity -> Parity
inverted parity =
    if parity == Odd then
        Even

    else
        Odd


type alias Temporary =
    { list : List Int
    , parity : Parity
    }


exchangingParity : List Int -> Parity
exchangingParity list =
    list 
        |> List.indexedMap Tuple.pair 
        |> List.foldl updateEP (Temporary list Even)
        |> .parity

updateEP : ( Int, Int ) -> Temporary -> Temporary
updateEP ( i, _ ) temp =
    if valueOf i temp.list == valueOf i solved then
        temp

    else
        { temp
            | list = swap i (indexOf (valueOf i solved) temp.list) temp.list
            , parity = inverted temp.parity
        }


valueOf : Int -> List Int -> Int
valueOf i list =
    Maybe.withDefault -1 <| List.Extra.getAt i list


spaceMovementParity : List Int -> Parity
spaceMovementParity list =
    if Arithmetic.isEven <| distance (indexOf spaceValue list) defaultSpaceIndex then
        Even

    else
        Odd


moveBy : Int -> List Int -> List Int
moveBy value list =
    let
        valueIndex =
            indexOf value list

        spaceIndex =
            indexOf spaceValue list
    in
    if distance valueIndex spaceIndex == 1 then
        list |> swap valueIndex spaceIndex

    else
        list


distance : Int -> Int -> Int
distance a b =
    abs (modBy matrixSize a - modBy matrixSize b) + abs (a // matrixSize - b // matrixSize)



-- SUBSCRIPTIONS


subscriptions : Model -> Sub Msg
subscriptions model =
    Sub.none



-- VIEW


view : Model -> Html Msg
view model =
    div [ class "main" ]
        [ div [ class "panel" ]
            (List.map putTile model.tiles)
        , div [ class "reset", onClick Reset ] [ text "Reset" ]
        ]


putTile : Int -> Html Msg
putTile value =
    if value == spaceValue then
        div
            [ class "tile tile_no_space"
            , onClick (Click value)
            ]
            [ text "_" ]

    else
        div
            [ class ("tile tile_no_" ++ String.fromInt value)
            , onClick (Click value)
            ]
            [ text (String.fromInt value) ]

長っ...

#「絶対解ける」って?
ランダムにタイルを配置することにして実装してみると、 1/2の確率で解けないお題を出題することになります。理屈は コチラ とかがわかりやすいかな?

不可能な配置の判定法と例
定理：s に対応する状態からはじめたとき， 8パズルが完成できる ⟺ s を t にする置換のパリティ（偶奇）と「空き」の最短距離の偶奇が等しい。
(中略)
実際の判定法
実際に与えられた配置が可能かどうかは上記の定理を使って簡単に判定することができます。
・空きの最短距離はすぐに分かります。数えて下さい。
・初期状態 s と完成状態 t の置換のパリティを求めるためには，実際に s を t にする置換を互換たちで表してその偶奇を見ればOKです。これは置換をサイクル分解してもできますし，以下のように1から順番にそろえていってもOKです。(以下略)

全部解けるお題にするために、ランダムシャッフルで作ったリストを調べて解けないようならちょこっと修正する、ってことにしました。

solvabled : List Int -> List Int
solvabled list =
    if isSolvable list then
        list

    else if List.member (indexOf spaceValue list) [ 0, 1 ] then
        swap 2 3 list

    else
        swap 0 1 list



swap : Int -> Int -> List Int -> List Int
swap a b list =
    List.Extra.swapAt a b list


isSolvable : List Int -> Bool
isSolvable list =
    exchangingParity list == spaceMovementParity list


indexOf : Int -> List Int -> Int
indexOf value list =
    Maybe.withDefault -1 <| List.Extra.elemIndex value list
  • 解けるリストならそのまま。
  • そうでなければ、任意のふたつのタイル(空のタイルじゃないやつ)を交換すればよい。
    • ここでは空のタイルの場所によって、2番目と3番目の交換か、または0番目と1番目か、にしてます。

これ以降、上の引用をそのまま実装したようなことになってます。
解けるかどうか?を返す関数 isSolvable はこんな感じです。

isSolvable : List Int -> Bool
isSolvable list =
    exchangingParity list == spaceMovementParity list

まんまです。互換の偶奇と 空白の移動の偶奇が等しいかどうか、です。

互換の偶奇 exchangingParity はちょっと面倒です。
ふたつのタイルを交換することで先頭からタイルを正しい位置にそろえていって、偶奇の変化の結果を見ることにしました。
まず偶奇 Parity, listとparityを持った中間状態 Temporary を定義します。

type Parity
    = Odd
    | Even


inverted : Parity -> Parity
inverted parity =
    if parity == Odd then
        Even

    else
        Odd


type alias Temporary =
    { list : List Int
    , parity : Parity
    }

indexedMapを使って、foldl で 添字アクセスできるようにしてみました。

  • temp.listの i 番目の値が答と同じ正しい位置ならばそのまま。
  • でなければ、正しい値のものと場所を交換し、偶奇を反転する。

exchangingParity : List Int -> Parity
exchangingParity list =
    list 
        |> List.indexedMap Tuple.pair 
        |> List.foldl updateEP (Temporary list Even)
        |> .parity

updateEP : ( Int, Int ) -> Temporary -> Temporary
updateEP ( i, _ ) temp =
    if valueOf i temp.list == valueOf i solved then
        temp

    else
        { temp
            | list = swap i (indexOf (valueOf i solved) temp.list) temp.list
            , parity = inverted temp.parity
        }


valueOf : Int -> List Int -> Int
valueOf i list =
    Maybe.withDefault -1 <| List.Extra.getAt i list

空白の移動の偶奇 spaceMovementParity はこんな感じです。
移動距離 distance が偶数なら Even 奇数なら Odd (当たり前か)。

spaceMovementParity : List Int -> Parity
spaceMovementParity list =
    if Arithmetic.isEven <| distance (indexOf spaceValue list) defaultSpaceIndex then
        Even

    else
        Odd


distance : Int -> Int -> Int
distance a b =
    abs (modBy matrixSize a - modBy matrixSize b) + abs (a // matrixSize - b // matrixSize)

distance は、 横の移動距離 プラス 縦の移動距離 ということです。

#まとめ
感想。

  • なるほど、シンプルだってみんないうのが良くわかりました。いいかも。
  • だけど、やけに 白みが多い...こんなに必要?
  • Elmのことが良く分かってないので、jsからの翻訳みたいな感じです。もっとうまいやりかたがあるんだろうな...
  • Random(ていうかCmd)を使おうとすると、大分勝手が違うっていうか、理解するのが難しかったです。関数が電卓で手元でパッと答が出るイメージだとして、Cmdはアマゾンに注文してヤマトさんに持って来てもらうくらいのイメージですかね?
  • 今回は.elmを.jsに書き出してhtmlから呼びだし、普通のcssを使うパターンでやってみました。 なるほどこうするのか...

以上です。つっこみ歓迎です。よろしくお願いします。

3
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?