Sokoban is a puzzle video game genre in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.
A puzzle is a game, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together in a logical way, in order to arrive at the correct or fun solution of the puzzle. There are different genres of puzzles, such as crossword puzzles, word-search puzzles, number puzzles, relational puzzles, and logic puzzles. The academic study of puzzles is called enigmatology.
A mechanical puzzle is a puzzle presented as a set of mechanically interlinked pieces in which the solution is to manipulate the whole object or parts of it. One of the most well-known mechanical puzzles is the Rubik's Cube, invented by the Hungarian architect Ernő Rubik in 1974. The puzzles are mostly designed for a single player where the goal is for the player to see through the principle of the object, not so much that they accidentally come up with the right solution through trial and error. With this in mind, they are often used as an intelligence test or in problem solving training.
A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or determine moves or plays in the game.
Combinatorial game theory (CGT) is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.
Connect Four is a two-player connection board game, in which the players choose a color and then take turns dropping colored tokens into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own tokens. Connect Four is a solved game. The first player can always win by playing the right moves.
Ataxx (アタックス) is a strategy video game that was published in arcades by The Leland Corporation in 1990. It also appeared the same year as Spot: The Video Game and later as the Microscope Puzzle from the 1993 CD-ROM game The 7th Guest. The game was invented by Dave Crummack and Craig Galley in 1988 and was originally called Infection. It was first programmed on Amiga, Commodore 64, and Atari ST.
The 15 puzzle is a sliding puzzle having 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order.
The Square-1, also known as Back to Square One and Cube 21, is a puzzle similar to the Rubik's Cube. Its distinguishing feature among the numerous Rubik's Cube variants is that it can change shape as it is twisted, due to the way it is cut, thus adding an extra level of challenge and difficulty. The Super Square One and Square Two puzzles have also been introduced. The Super Square One has two additional layers that can be scrambled and solved independently of the rest of the puzzle, and the Square Two has extra cuts made to the top and bottom layer, making the edge and corner wedges the same size.
Klotski is a sliding block puzzle thought to have originated in the early 20th century. The name may refer to a specific layout of ten blocks, or in a more global sense to refer to a whole group of similar sliding-block puzzles where the aim is to move a specific block to some predefined location.
A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a combination puzzle that challenges a player to slide pieces along certain routes to establish a certain end-configuration. The pieces to be moved may consist of simple shapes, or they may be imprinted with colours, patterns, sections of a larger picture, numbers, or letters.
Kye is a real-time puzzle game with a variety of interacting objects. It takes ideas from puzzle games like Sokoban and Boulder Dash, but the inclusion of active objects gives it a real-time component, and it can also produce arcade-game levels like those found in Pac-Man. Anyone can create new levels for the game.
Ricochet Robots is a puzzle board game for 2 or more people, designed by Alex Randolph, in which the playing pieces (robots) must be moved to selected locations in as few moves as possible, working within strict limitations on robots' movements. The game was first published in Germany in 1999 as Rasende Roboter. An English version was published by Rio Grande Games.
Fish Fillets NG, originally just Fish Fillets, is a puzzle video game developed and released by Altar Games in 1998. The game's goal is in each level to find a safe way out for both of the two fish. Fish Fillets is comparable to other sliding puzzle games such as sokoban and klotski, while it has a few additional elements and rules.
Zillions of Games is a commercial general game playing system developed by Jeff Mallett and Mark Lefler in 1998. The game rules are specified with S-expressions, Zillions rule language. It was designed to handle mostly abstract strategy board games or puzzles. After parsing the rules of the game, the system's artificial intelligence can automatically play one or more players. It treats puzzles as solitaire games and its AI can be used to solve them.
Puzzlejuice is a 2012 indie puzzle video game for iOS produced and developed by video game company Sirvo. The game is a combination of Tetris, tile-matching, and Boggle: players rearrange falling tetromino blocks into rows of similar colors, which turn into letters that are cleared from the board by forming words. The fast-paced game also includes challenges and power-ups. The development team consisted of three people; programmer Asher Vollmer initially developed the game alone, before reaching out to artist Greg Wohlwend for advice on the aesthetics. Composer Jimmy Hinson produced the game's music.
Dynamo chess is a chess variant invented by chess problemists Hans Klüver and Peter Kahl in 1968. The invention was inspired by the closely related variant push chess, invented by Fred Galvin in 1967. The pieces, board, and starting position of Dynamo chess are the same as in orthodox chess, but captures are eliminated and enemy pieces are instead "pushed" or "pulled" off the board. On any given move, a player can make a standard move as in orthodox chess, or execute a "push move" or a "pull move". A move that is either a push move or a pull move is called a "dynamo move".
In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.
