A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit squares edge to edge. These two notions were first introduced and investigated by Solomon W. Golomb in the 1950s and popularized by Martin Gardner in the 1960s. Since then, dozens of studies have been made in communities of recreational mathematics and puzzles. We first focus on the specific rep-tiles that have been investigated in these communities. Since the notion of rep-tiles is so simple that can be formulated mathematically in a natural way, we can apply a representative puzzle solver, a MIP solver, and SAT-based solvers for solving the rep-tile problem in common. In comparing their performance, we can conclude that the SAT-based solvers are the strongest in the context of simple puzzle solving. We then turn to analyses of the specific rep-tiles. Using some properties of the rep-tile patterns found by solvers, we can complete analyses of specific rep-tiles up to certain sizes, and find new series of solutions for the rep-tiles which have never been found.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Rep-Tile by Computers: Performance of Solvers and Analyses of Solutions

  • Mutsunori Banbara,
  • Kenji Hashimoto,
  • Takashi Horiyama,
  • Kosuke Oguri,
  • Shin-ichi Minato,
  • Masaaki Nishino,
  • Masahiko Sakai,
  • Ryuhei Uehara,
  • Yushi Uno,
  • Norihito Yasuda

摘要

A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit squares edge to edge. These two notions were first introduced and investigated by Solomon W. Golomb in the 1950s and popularized by Martin Gardner in the 1960s. Since then, dozens of studies have been made in communities of recreational mathematics and puzzles. We first focus on the specific rep-tiles that have been investigated in these communities. Since the notion of rep-tiles is so simple that can be formulated mathematically in a natural way, we can apply a representative puzzle solver, a MIP solver, and SAT-based solvers for solving the rep-tile problem in common. In comparing their performance, we can conclude that the SAT-based solvers are the strongest in the context of simple puzzle solving. We then turn to analyses of the specific rep-tiles. Using some properties of the rep-tile patterns found by solvers, we can complete analyses of specific rep-tiles up to certain sizes, and find new series of solutions for the rep-tiles which have never been found.