Morpion Solitaire 5D : a new upper bound 121 of the maximum score (コンピュテーション) Morpion Solitaire 5D : a new upper bound 121 of the maximum score

Search this Article

Author(s)

Abstract

Morpion Solitaireという名前の紙と鉛筆で遊ぶパズル(一人遊びゲーム)がある.フランスを中心に人気があり,世界中に知られている.このパズルは盤面にクロスを1つ描きラインを1本引くことを1手とし,与えられた初期盤面から始めてその手数を最大化することを目的とする.引かれるラインの長さとそれに応じた初期盤面,また引くことができるラインの制約などによっていくつかの種類がある.本論文の目的は,Morpion Solitaire 5Dという種類に対して,その最大手数の上界値を理論的に改善することである.具体的には上界値改善のためにラインベースの議論を導入し,現在知られている最善の上界値138を121に改善する.

Morpion Solitaire is a pencil-and-paper game for a single player, popular in several countries including France. A move in this game consists of putting a cross at a lattice point and then drawing a line segment that passes through exactly five consecutive crosses. The objective is to make as many moves as possible, starting from a standard initial configuration of crosses. For one of the variants of this game, called 5D, we prove the upper bound 121 on the number of moves. This is done by introducing line-based analysis, and improves on the known upper bound 138 obtained by potential-based analysis.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 113(108), 1-6, 2013-06-24

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    110009779042
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • ISSN
    0913-5685
  • NDL Article ID
    024679348
  • NDL Call No.
    Z16-940
  • Data Source
    NDL  NII-ELS 
Page Top