Skip to main content
16 votes

Complexity of n-queens-completion?

It's taken years but this post inspired us to write a paper which has come out today. The answer is that n Queens Completion is NP-Complete. However for full disclosure should mention we solve a ...
Ian Gent's user avatar
  • 428
8 votes

Among an infinite variety of n x n board games, why are some interesting?

I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game ...
Marzio De Biasi's user avatar
5 votes

Does this game terminate?

Digression Maybe since the time of asking you found the answer yourself... However yes, "Cavacamicia" has cycles so sometimes it is non terminating. Some friends and I found this back in May ...
Diego Mazzaro's user avatar
3 votes

Matrix Coloring under Vertical and Horizontal Constraints

A1) The problem remains NP-complete even for fixed $|\Sigma|=3$ A reduction from planar 1-3-SAT is the following; suppose $\Sigma = \{0,1,2\}$ use a sequence of $M_{ij} = \{0,1\}$ pairs of ...
Marzio De Biasi's user avatar
2 votes

Implementation of surreal numbers for games

Here is an implementation of Surreal Numbers in a relatively new language, Julia. Described at
Matt's user avatar
  • 21

Only top scored, non community-wiki answers of a minimum length are eligible