Related Research Articles
Peg solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known simply as Solitaire in the United Kingdom where the card games are called Patience. It is also referred to as Brainvita.
Sokoban is a type of puzzle video game in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.
The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
Mastermind or Master Mind is a code-breaking game for two players. The modern game with pegs was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. It resembles an earlier pencil and paper game called Bulls and Cows that may date back a century or more.
TwixT is a two-player strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games in the series. It is a connection game where players alternate turns placing pegs and links on a pegboard in an attempt to link their opposite sides. The rules are simple but the strategy complex, so young children can play it, but it also appeals to adults. The game has been discontinued except in Germany.
Nonograms, also known as Picross or Griddlers, are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive sets.
In computer science, a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems.
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.
Nurikabe is a binary determination puzzle named for Nurikabe, an invisible wall in Japanese folklore that blocks roads and delays foot travel. Nurikabe was apparently invented and named by Nikoli; other names for the puzzle include Cell Structure and Islands in the Stream.
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop edges from the graph to break the cycles. A feedback arc set (FAS) or feedback edge set is a set of edges which, when removed from the graph, leave a DAG. Put another way, it's a set containing at least one edge of every cycle in the graph.
Heyawake is a binary-determination logic puzzle published by Nikoli. As of 2013, five books consisting entirely of Heyawake puzzles have been published by Nikoli. It first appeared in Puzzle Communication Nikoli #39.
Hasami shogi is a variant of shogi. The game has two main variants, and all Hasami variants, unlike other shogi variants, use only one type of piece, and the winning objective is not checkmate. One main variant involves capturing all but one of the opponent's men; the other involves building an unbroken vertical or horizontal chain of five-in-a-row.
Gess is an abstract strategy board game for two players, involving a grid board and mutating pieces. The name was chosen as a conflation of "chess" and "Go". It is pronounced with a hard "g" as in "Go", and is thus homophonous with "guess".
Minesweeper is a single-player puzzle computer game. The objective of the game is to clear a rectangular board containing hidden "mines" or bombs without detonating any of them, with help from clues about the number of neighboring mines in each field. The game originates from the 1960s, and has been written for many computing platforms in use today. It has many variations and offshoots.
In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly, such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it, and a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If any NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.
Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.
In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens.
In computational complexity theory, the constraint logic problem is a problem in constraint graph, a special graph with weighted edges that satisfy special constraints. This problem and its variants have been proven to be PSPACE-Complete and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete.
References
- 1 2 Andersson, Daniel (2007), "HIROIMONO Is NP-Complete", in Crescenzi, Pierluigi; Prencipe, Giuseppe; Pucci, Geppino (eds.), Fun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007, Proceedings, Lecture Notes in Computer Science, 4475, Springer, pp. 30–39, doi:10.1007/978-3-540-72914-3_5, ISBN 978-3-540-72913-6
- ↑ Costello, Matthew J. (1988), The Greatest Puzzles of All Time, Dover books on mathematical & logical puzzles, cryptography and word recreations, Courier Corporation, pp. 9–10, ISBN 9780486292250
- ↑ Tagaya, K. (1727), Wakoku Chie Kurabe. As cited by Fukui, Suetsugu & Suzuki (2017).
- ↑ Fukui, Masanori; Suetsugu, Koki; Suzuki, Akira (2017), "Complexity of "Goishi Hiroi"", Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³ 2017) (PDF), pp. 142–143, archived from the original (PDF) on 2017-09-12, retrieved 2017-09-11