0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@iharakenji

Flutterで箱入り娘を作成する2

0
Last updated at Posted at 2026-10-30

概要

Flutterで箱入り娘を作成し、iOS と Android のアプリとして販売する
このシリーズでは、作り始めから販売までを順番に書いていく

第2回では、次のことをする
1手の数え方を調べる
最短手数を探すプログラムを作り、定番の配置が81手になるか確かめる
駒をなぞる間に、角を曲がれるようにする

実行環境

Flutter

$ flutter --version
Flutter 3.47.8 • channel stable • https://github.com/flutter/flutter.git
Framework • revision 737ba8f885 (8 days ago) • 2026-10-22 21:37:31 -0700
Engine • hash dfd2e6cb7d319db05e3bf1503f3e2ac60f6288a2 (revision cf636b1dfb) (7 days ago) • 2026-10-23 02:13:38.000Z
Tools • Dart 3.13.7 • DevTools 2.60.0

手順

ファイルの構成

lib/
  model/              … ルール（前回から）
  solver/
    solver.dart       … 最短手数を探す
  screen/
  widget/
tool/
  solve_classic.dart  … 定番の配置を解いて、手数を表示する
test/
  solver/solver_test.dart

ソルバーは前回の model（Board と Piece）をそのまま使う。
model は Flutter を import していないので、ソルバーも画面なしで動かせる。

以下のコードは主要な部分の抜粋（... は省略）。

1手の数え方

箱入り娘の手数は、数え方が何通りかある。

数え方 1手
1マスずつ 1マス動かすごとに1手
まっすぐ 1つの駒をまっすぐ何マス動かしても1手
曲がってもいい 1つの駒を、ほかの駒を動かさずに行ける所なら、曲がっても1手

よく知られている「定番の配置は81手」は、3つめの数え方。
指で駒に触って、動かして、離すまでが1手になる。

3通りとも数えられるように、数え方を enum にする。

lib/solver/solver.dart
/// 何を1手と数えるか。
enum MoveRule {
  /// 1マス動かすごとに1手。
  step,

  /// 1つの駒をまっすぐ何マス動かしても1手。
  straight,

  /// 1つの駒を、ほかの駒を動かさずに行ける所なら、曲がっても1手。
  piece,
}

最短手数を探す

幅優先探索

最初の盤面から、1手で行ける盤面、2手で行ける盤面…と順に調べる。
近いものから順に調べるので、クリアした盤面が最初に見つかったときの手数が最短になる。

  • 調べる順番は Queue（先に入れたものから取り出す）
  • 見つけた盤面は Map に入れる。値は1手前の盤面
    • 同じ盤面を2回調べない
    • クリアしたら、1手前を順にたどれば手順になる
lib/solver/solver.dart
/// 幅優先探索で、[start] から娘を出口に出すまでの最短の手順を探す。
///
/// [path] は最初の盤面からクリアした盤面までの並び（手数は `path.length - 1`）。
/// 解けなければ null。[visited] は調べた盤面の数。
({List<Board>? path, int visited}) solve(
  Board start, {
  MoveRule rule = MoveRule.piece,
}) {
  // 見つけた盤面と、その1手前の盤面。見つけたかどうかの記録も兼ねる
  final previous = <Board, Board?>{start: null};
  final queue = Queue<Board>()..add(start);
  while (queue.isNotEmpty) {
    final board = queue.removeFirst();
    if (board.isSolved) {
      return (path: _path(previous, board), visited: previous.length);
    }
    for (final next in nextBoards(board, rule)) {
      if (previous.containsKey(next)) continue;
      previous[next] = board;
      queue.add(next);
    }
  }
  return (path: null, visited: previous.length);
}

戻り値はレコード ({List<Board>? path, int visited})。
手順と、調べた盤面の数を、クラスを作らずに名前付きで返せる。

lib/solver/solver.dart
/// [goal] から1手前をたどって、最初の盤面からの並びにする。
List<Board> _path(Map<Board, Board?> previous, Board goal) {
  final path = <Board>[];
  Board? board = goal;
  while (board != null) {
    path.add(board);
    board = previous[board];
  }
  return path.reversed.toList();
}

前回「調べた盤面を Set に入れて覚える」と書いたが、1手前も覚えるために Map にした。

1手で行ける盤面

数え方ごとに、駒の行き先を switch 式で切りかえる。
sync* と yield で、見つけた盤面を1つずつ返す（リストを作らずに済む）。

lib/solver/solver.dart
/// [board] から1手で行ける盤面。
Iterable<Board> nextBoards(Board board, MoveRule rule) sync* {
  for (var i = 0; i < board.pieces.length; i++) {
    final destinations = switch (rule) {
      MoveRule.step => _steps(board, i),
      MoveRule.straight => _straights(board, i),
      MoveRule.piece => _reachables(board, i),
    };
    for (final piece in destinations) {
      yield board.place(i, piece);
    }
  }
}

「曲がってもいい」は、1つの駒だけを1マスずつ動かして行ける所を、同じく幅優先で集める。

lib/solver/solver.dart
/// [index] 番目の駒だけを何マスか動かして行ける位置（曲がってもいい）。今の位置は含まない。
Iterable<Piece> _reachables(Board board, int index) {
  final start = board.pieces[index];
  final found = <Piece>{start};
  final queue = Queue<Piece>()..add(start);
  while (queue.isNotEmpty) {
    final piece = queue.removeFirst();
    for (final d in Direction.values) {
      final moved = piece.moved(d);
      if (board.canPlace(index, moved) && found.add(moved)) queue.add(moved);
    }
  }
  return found.skip(1);
}

Set.add は、新しく入ったときだけ true を返す。調べたかどうかの確認と追加が1回で済む。

canPlace と place は Board に足した。

lib/model/board.dart
  /// [index] 番目の駒を [piece] の位置に置けるか（ほかの駒はそのまま）。
  bool canPlace(int index, Piece piece) {
    if (!_isInside(piece)) return false;
    for (var i = 0; i < pieces.length; i++) {
      if (i != index && pieces[i].overlaps(piece)) return false;
    }
    return true;
  }

  /// [index] 番目の駒を [piece] に置き換えた盤面。
  Board place(int index, Piece piece) {
    final next = [...pieces];
    next[index] = piece;
    return Board(next);
  }

盤面を Map のキーにする

Map のキーにするので、Board にも == と hashCode を書く。

ここで「同じ盤面」をどう決めるかで、調べる量が大きく変わる。
定番の配置には、縦長の駒が4つ、小さい駒が4つある。
同じ種類の駒どうしを入れ替えても、遊ぶ人から見れば同じ盤面になる。

V D D V      V D D V
V D D V      V D D V
V H H V  と  V H H V   は同じ盤面
V S S V      V S S V
S . . S      S . . S
（左の V が駒A、右の V が駒B）（左右の V を入れ替えた）

そこで、駒の並び順も、同じ種類の駒の入れ替えも区別しないことにする。

lib/model/board.dart
  /// 同じ種類の駒が同じマスにあれば、同じ盤面とみなす。
  /// 駒の並び順や、同じ種類の駒どうしが入れ替わっているかは区別しない。
  @override
  bool operator ==(Object other) =>
      other is Board &&
      other.pieces.length == pieces.length &&
      _pieceSet.containsAll(other.pieces);

  @override
  late final int hashCode = Object.hashAllUnordered(pieces);

  late final Set<Piece> _pieceSet = pieces.toSet();
  • Piece の == は「種類と位置」で比べる（前回）。なので、同じ種類で同じ位置の駒は、どの駒でも同じになる
  • Object.hashAllUnordered は、並び順を変えても同じ値を返す
  • Board は変更できないので、hashCode と Set は late final で1回だけ作る（Map の中で何度も使われる）

区別する場合としない場合で、定番の配置を解いて比べた（時間は手元の PC で測ったもの）。

同じ種類の駒の入れ替え 手数 調べた盤面 時間
区別する 81手 10,534,300 約123秒
区別しない 81手 23,960 約0.3秒

手数は同じで、調べる盤面は約440分の1になる。

== を変えたときに気を付けること

== で「並び順の違う盤面」も同じになったので、「盤面が替わったか」を == で調べると、並び順だけ違う盤面を見落とす。

画面の BoardView は、なぞっている途中で盤面が替わったら（はじめからボタンなど）、掴んでいた駒を離す。
ここは「別のオブジェクトになったか」を知りたいので、identical で比べる。

lib/widget/board_view.dart
  @override
  void didUpdateWidget(BoardView oldWidget) {
    super.didUpdateWidget(oldWidget);
    // なぞっている途中で盤面が替わったら（はじめからなど）、掴んでいた駒は離す
    // Board の == は駒の並び順を見ないので、別の盤面かどうかは identical で比べる
    if (!identical(oldWidget.board, widget.board) || !widget.enabled) {
      _release();
    }
  }

定番の配置を解く

3通りの数え方で解いて表示する。

tool/solve_classic.dart
void main() {
  for (final rule in MoveRule.values) {
    final watch = Stopwatch()..start();
    final result = solve(classicLayout, rule: rule);
    watch.stop();
    final moves = result.path == null ? '解けない' : '${result.path!.length - 1} 手';
    print(
      '${rule.name}: $moves'
      '（調べた盤面 ${result.visited}、${watch.elapsedMilliseconds} ms）',
    );
  }
}

$ dart run tool/solve_classic.dart
step: 116 手（調べた盤面 24098、287 ms）
straight: 90 手（調べた盤面 23946、228 ms）
piece: 81 手（調べた盤面 23960、276 ms）

「曲がってもいい」数え方で81手になった。
アプリでも、見つけた手順どおりに動かすと、81手でクリアになった。

駒をなぞる間に、角を曲がれるようにする

前回の画面は、まっすぐ動かしたときだけ1手だった。
81手と同じ数え方にするため、1回なぞる間に角を曲がれるようにする。

  1. 指がとなりのマスの半分を越えたら、駒をそのマスへ進める（L字になぞれば角を曲がる）
  2. 指を離すまでが1手（曲がっても、何マス動かしても1手）
  3. 元のマスにいるときだけ、マスの4割なぞれば動く（前回と同じく、少しなぞるだけで動くように）
lib/widget/board_view.dart
  /// なぞっている間の、掴んだ駒のマス。指について角を曲がると変わる。
  Piece? _at;
  ...
  /// 指が [_at] からマスの [threshold] 倍より多くずれていて、その向きの隣が空いていれば、その向き。
  Direction? _nextStep(double cell, double threshold) {
    for (final (direction, amount) in _split(_rest(cell))) {
      if (amount > cell * threshold &&
          widget.board.canPlace(_grabbed!, _at!.moved(direction))) {
        return direction;
      }
    }
    return null;
  }

  /// 指が隣のマスの半分を越えたら、駒をそのマスへ進める。L 字になぞれば角を曲がる。
  void _followFinger(double cell) {
    for (var d = _nextStep(cell, 0.5); d != null; d = _nextStep(cell, 0.5)) {
      _at = _at!.moved(d);
    }
  }

_split は、指のずれを「横の向きと量」「縦の向きと量」に分けて、量の大きい順に並べる。
大きいほうの向きがふさがっていれば、もう一方の向きを試す。

離したときの行き先は _target で決める。

lib/widget/board_view.dart
  /// 今指を離したら、駒が収まるマス。元のマスに戻るなら null（動かさない）。
  /// まだ元のマスにいるときだけ、マスの 4 割より多くなぞれば隣へ動かす（少しなぞるだけで動くように）。
  /// 進んだあとは [_at] のまま（4 割で戻すと、来た向きへ引き返してしまうため）。
  Piece? _target(double cell) {
    if (_grabbed == null) return null;
    final start = widget.board.pieces[_grabbed!];
    if (_at != start) return _at;
    final d = _nextStep(cell, 0.4);
    return d == null ? null : start.moved(d);
  }

進む判定を「半分」にしているのは、行ったり来たりしないため。
4割で進むようにすると、1つ進んだ直後に「戻る向きに6割ずれている」ことになり、すぐ戻ってしまう。

画面に知らせる内容は「何番目の駒を、どの位置へ」にした。
GameScreen は place で置いて、1手増やすだけになる。

lib/screen/game_screen.dart
  /// 指を離したときに呼ばれる。触ってから離すまでを、曲がっても 1 手と数える。
  void _move(int index, Piece to) {
    if (_board.isSolved) return;
    setState(() {
      _board = _board.place(index, to);
      _moves++;
    });
  }

テスト

test/solver/solver_test.dart
    test('定番の配置は、同じ駒なら曲がっても1手と数えて 81 手', () {
      expect(moves(classicLayout, MoveRule.piece), 81);
    });

    test('まっすぐなら1手と数えると 90 手、1マスずつなら 116 手', () {
      expect(moves(classicLayout, MoveRule.straight), 90);
      ...
test/widget/board_view_test.dart
  testWidgets('L 字になぞると、駒は角を曲がって 1 回で動く', (tester) async {
    ...
    final gesture = await tester.startGesture(center(tester, 1, 4));
    await gesture.moveBy(const Offset(cell, 0)); // 右へ
    await tester.pump();
    await gesture.moveBy(const Offset(0, -cell)); // 上へ
    await tester.pump();
    ...
    await gesture.up();
    expect(moves, [(5, const Piece(PieceType.small, 2, 3))]);
  });

flutter test

アプリの実行

アプリを起動

flutter run

実行結果

klotski2.gif

次回

いろいろな配置（ステージ）を作って、難しさの順に並べる。

0
0
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
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?