Description

I started on an implementation of the Nondeterministic Constraint Logic puzzle / game.
From the Wikipedia page for Nondeterministic constraint logic:
In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. The constraint logic problem and its variants have been proven to be PSPACE-complete to determine whether there exists a sequence of moves that reverses a specified edge and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete.
​
This is a form of reversible logic in that each sequence of edge orientation changes can be undone. The hardness of this problem has been used to prove that many games and puzzles have high game complexity.
Anyway, this system can actually be implemented as a kind of single player puzzle game in which one has a graph with colored arrows, and one tries to flip the arrows in such a way that a target arrow (which I’ve colored yellow in my implementation) can be flipped. The rules are basically that each node must have a weight of at least two moving into it. The thinner red arrows add weight one, the thicker blue arrows add weight two. I’ve tried to generate puzzles that are at least somewhat challenging for the size that they are, but with smaller sizes, but I think they’re still not *too* hard to solve once you get the hang of how the game works.
​
In the future, I think I could make the puzzle generation more efficient, but for now it works alright.

Code


The Game

In[]:=
Manipulate[If[resetQ,​​winQ=False;edges=initEdges;resetQ=False];If[generateQ,winQ=False;edges=initEdges=puzzlizeGraph[vertexNumber,redWeight];initGraph=Graph[edges,GraphLayoutgraphLayout];vertexCo=Last[First[AbsoluteOptions[initGraph,VertexCoordinates]]];generateQ=False];Column[{progress,​​With[{flippedEdges=​​Module[{i=0},​​Function[edge,​​(i++;EventHandler[edge,{"MouseClicked"​​(edges=If[flippableQ[edge,edges],​​If[jwinIndex,winQ=True];​​MapAt[edgeFlip,edges,j],edges];)​​/.ji}])​​]​​/@edges​​]​​},​​Graph[flippedEdges,​​VertexCoordinatesmoveBy[vertexCo,VertexList[initGraph],VertexList[edges]],​​EdgeShapeFunctionGraphElementData["ShortUnfilledArrow","ArrowSize".15],​​VertexSizeScaled[redEdgeSize*vertexExpansion],​​ImageSize{350,350}]],​​If[winQ,"You Win!"]}],​​{{vertexNumber,8,"Vertex Number"},4,28,2,Appearance"Open"},​​{{generateQ,True,""},Button["Generate Puzzle",generateQ=True]&},​​{{resetQ,False,""},Button["Reset Puzzle",resetQ=True]&},​​SaveDefinitionsTrue]

CITE THIS NOTEBOOK

Implementation of Nondeterministic Constraint Logic Game​
by Eric Parfitt​
Wolfram Community, STAFF PICKS, December 24, 2023
​https://community.wolfram.com/groups/-/m/t/1993426