グリッド状の盤面の上で与えられた条件を満たす単純パスを求めることを目的としたパズルゲームは多く存在する。本研究の目的は条件を満たすグリッド上の単純パスの存在判定問題の計算複雑さを明らかにすることである。
　本稿ではまずパスによって分割された領域の数を指定された値にする、という条件に付いて考えた。以降この領域を空白と呼ぶ。この条件について、空白の数の最大値の解析を行った。次に空白の数を指定された値にしかつ指定された頂点を通らない、頂点のパス内での位置が指定される、という2つの条件について条件を満たす単純パスの存在判定問題が、どちらもNP完全であることを示した。