元ネタを遊んでみて、ああこんなやりかたをするんだと勉強になったので、良さそうだけどあまりいじってない 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を使うパターンでやってみました。 なるほどこうするのか...
以上です。つっこみ歓迎です。よろしくお願いします。