t0nyx1ang/noqx

Extended logic puzzle solver of noq.

Noqx

Extended logic puzzle solver of Noq.

Current development status

• Remove redundant codes and formatting codes.

• New solver API with new visualizations (See issue #2)

• Multiple UI optimizations.

• Change the backend from Django to FastAPI (See issue #31).

How to run locally

Use PDM with a virtual environment (Recommended)

• Install PDM first.

• Install dependencies with PDM:

    pdm install

• Run with PDM:

    pdm run noqx.py

Use PIP

• Install requirements (automatically generated by PDM):

    pip install -r requirements.txt

• Run locally (based on your system):

    py -3 noqx.py
    python3 noqx.py

How to contribute

• Install PDM first.

• Clone this project and switch to dev branch.

    git clone https://github.com/T0nyX1ang/noqx.git

• Install dependencies with PDM:

    pdm install

• Install pre-commit and add commit hooks:

    pre-commit install

• Free to PR now ^_^

Noq (Original Project)

Noq is currently accessible on the web at noq.solutions.

noqx's Issues

[Refactor] refactor on the javascript loading process

maybe a separation in the game types is better?

[Feature] Conform to pzprv3 format

Since many puzzles can be played on <puzz.link>, it is natural to use the globally recognized pzprv3 format. In this way, noqx will become a solving backend eventually, and the frontend will be implemented simply by adding a html object tag:

A sample frontend is as follows (with problem loading):

<script>
    function changeData() {
        var object = document.getElementById('object');
        object.data = "https://puzz.link/p?type=player&embed=yes&pzprv3/nonogram/6/6/.%20.%20.%20.%201%20.%201%20.%20.%20/.%20.%20.%202%201%20.%201%202%20.%20/.%20.%20.%201%201%201%201%201%20.%20/.%202%201%20%23%20%23%20%2B%20%23%20%2B%20%2B%20/.%201%201%20%23%20%2B%20%2B%20%2B%20%23%20%2B%20/.%201%202%20%2B%20%23%20%2B%20%23%20%23%20%2B%20/.%20.%20.%20%2B%20%2B%20%2B%20%2B%20%2B%20%2B%20/.%201%201%20%23%20%2B%20%2B%20%2B%20%23%20%2B%20/.%20.%203%20%2B%20%23%20%23%20%23%20%2B%20%2B%20//";
    }
</script>

<div class="object-container" style="text-align: center;">
    <object
        data="https://puzz.link/p?type=player&embed=yes&pzprv3/nonogram/6/6/.%20.%20.%20.%201%20.%201%20.%20.%20/.%20.%20.%202%201%20.%201%202%20.%20/.%20.%20.%201%201%201%201%201%20.%20/.%202%201%20.%20.%20.%20.%20.%20.%20/.%201%201%20.%20.%20.%20.%20.%20.%20/.%201%202%20.%20.%20.%20.%20.%20.%20/.%20.%20.%20.%20.%20.%20.%20.%20.%20/.%201%201%20.%20.%20.%20.%20.%20.%20/.%20.%203%20.%20.%20.%20.%20.%20.%20//"
        style="width: 80%; height: 95%;" id="object">
    </object>
</div>

<div class="button-container" style="text-align: center;">
    <button onclick="changeData()" style="align-content: center;">Solve!</button>
</div>

I plan to implement this after 90% or more solvers in noqx are solved in Clingo.

The Nonogram UI and Yajikazu UI should be fixed

Nonogram UI: parameter loading is not by a standard approach.
Yajikazu UI: example loading is wrong.

[Feature] make adjacent rule more flexible

Current adjacent rule are not very flexible, since only one adjacent types can be included in the program.
Consider the case that different colors have different adjacent rules. The adjacent rule is invalid here.

[Feature] Add initial condition for hitori and kuromasu

for hitori, add a "safe" cell condition
for kuromasu, add both "safe" and "unsafe" cell condition

[Feature/Bug] Slitherlink missing wolves and sheep separation

An example has been added to dev branch.

[Refactor] parameter change for count-relevant functions

• before: target: int, op: str => two parameters
• after: target: Union[int, Tuple[str, int]] => one tuple, representing clearer relationship; or one parameter, represent equality

[Refactor/Feature] Support solver inheritance

This feature aims to make solvers behave like plugins.

The following code might be used:

def solve(E: encoding) -> str:
    # do anything or use the default behavior

[Feature/Bug] Support near number hashi puzzles

reference puzzle: https://jh2024.jianghujiemi.fun/puzzle/beam

[Deps] Change to FastAPI/starlette backend

As far as we think, Django would be too large for a simple application like noqx which only interacts with APIs.

Hence, we will replace django with FastAPI + uvicorn + jinja2 for simplicity.

[Bug] Nonogram initial value conflicts with unsetting the last value

A clue is set:

After pressing a "Delete" key

We can see that all the clues are gone.

This issue can be avoided in 73e1591, just before the initial value is set. So the issue is along with the initial value setting.

Analysis of this bug:

• DirectSum function merges the NonogramElf with BgColorElf, and both elves handle "Delete Key"
• BgColorElf will call Elf first, which will clear the innerTextHTML

Methods to fix:

• Call BgColorElf first

[refactor] 重构black white至统一颜色接口

该接口能够更好表达行列元素相同

[Feature] Add initial conditions in puzzles

在solver中增加初始条件

我们以Hitori为例，讲一下如何给一个puzzle增加初始条件。

首先是前端部分：这些puzzle前端部分的代码主要在static/noq/elves.js中。以Hitori为例，首先在代码最后的

let elf_types = {
    ...
}

中找到

hitori: HitoriElf,

可以发现，Hitori前端完全依靠HitoriElf。随后我们在文件中查找HitoriElf的定义部分并进行修改：

class HitoriElf extends

增加初始条件其实只需要把extends的class变为

DirectSum(
	class, BgColorElf({'x': ['black', 'darkgray']}, false)
)

即可，也就是在原先的基础上加了一个BgColorElf，初始条件设定使用BgColorElf即可。注意到设置颜色（初始值）一般是用x键，但Hitori的LetterElf把x键给占了(被我们魔改掉了)，因此这里我们把设置初始值的按键改为x。

到此前端部分修改完毕。下面修改后端部分：

在solvers文件夹下找到hitori.py，找到里面的solve函数，打印一下E.clues可以发现，加了颜色之后发现clues中对应的value会从（比如）4变为['4', 'black']。因此我们可以把含有gray的格子加上必须染色的约束，并把相应的value从['4', 'gray']改回4：

K = list(E.clues.keys())
for i, (r, c) in enumerate(K):
    if isinstance(E.clues[(r, c)], list):
        num, color = E.clues[(r, c)]
        assert color == 'black'
        require(s.grid[r][c])
        E.clues[(r, c)] = int(num) if '0' <= num <= '9' else num

这样初始条件就加好啦！

[Bug] Onsen solver does not consider the empty circle case

As the rule of onsen mentioned, there is an empty circle case.

[Bug] Shikaku optimization doesn't consider all rectangles has only one number

Reference:

[Refactor] separate puzzle-specific rules/constraints to their own workspaces

Some rules and constraints are general, while others are not. Putting specific rules and constraints in the utils will make more efforts to maintain.

So, if a rule/constraint is assumed to be specific to only one puzzle, it will be moved to the puzzle's workspace. Once this rule/constraint can be extended to different puzzles, we will consider to put it back to the utils.rules directory.

Currently, the following rules/constraints will be modifed:

• nori_adjacent (in Norinori)
• avoid_unknown_misaki (in Nurimisaki)
• valid_stostone (in Stostone)

The following rules/constraints may be modifed:

• unique_linecolor (in Binairo)
• identical_adjacent_map (in Tents)

Performance is not good enough on large fillomino problems

For large grids, the performance of current solver is degraded.

[Refactor] Create a uniform constructor for all connectivity structures

All the connectivity structures contain three parts:

• initialization (required): define the initial points,
• propagation (required): propagate the full connectivity map with the initial points and a propagation rule (such as an adjacent rule),
• constraint (optional): reachable on a certain area, region, etc.

Hence, it is possible to create a uniform constructor.

The following things are regarded as a connectivity structure:

• reachable, without a known origin (named as reachable/2 in the codes)
• reachable, with some known origins (named as region/2 in the codes)
• reachable to edges (named as reachable_edge/2 in the codes)
• lit, propagate adjacency as a bulb (named as lit/2 in the codes)
• reachable in an area (named as reachable/3 in the codes)
• reachable components (named as reachable/4 in the codes)

[Dev/Bug] Fivecells/Fourcells diverge

The user can't jump to the rule pages since fivecells and fourcells are different puzzle types in puzz.link.

[Refactor] Apply color specification in adjacent relationship

Current adjacent relationship are not tied to color, but it is possible to add a color specification on it.
This process may reduce propagation time, as many branches are ignored during the adjacent calculation.

[Feature] replace solver kernel from claspy to clingo

Currently transformed solver(s):

Shading

• Aqre
• Aquarium
• Binairo
• Cave
• Canal View (new!)
• Chocona
• Heyawake
• Hitori
• Kuromasu
• Kurotto
• LITS
• Nonogram
• Norinori
• Nuribou
• Nurikabe
• Nurimisaki
• Shakashaka
• Shimaguni
• Stostone
• Tapa
• Tasquare (new!)
• Yajisan-Kazusan
• Yin-Yang

Region Division

• Heteromino
• N Cells
• Shikaku
• Spiral Galaxies
• Tatamibari

Loop / Path

• Balance Loop
• Castle Wall
• Country Road
• Haisu
• Hashi
• Hotaru Beam
• Masyu
• Moon-or-Sun
• Nagare
• Numberlink
• Onsen
• Slitherlink
• Tapa-Like Loop
• Yajilin

Number Placement

• Fillomino
• Kakuro
• Nanro
• Ripple Effect

Object Placement

• Akari
• Battleship
• Gokigen
• Magnets
• Minesweeper
• Star Battle
• Statue Park
• Tents

Latin Square

• Doppelblock
• Easy As
• Skyscrapers
• Sudoku

[Enhancement?] Reduce the searching size of shading-relevant puzzles

In a common shading puzzle, the shading rule should be:

    { black(R, C) } :- grid(R, C).
    black(r1, c1).
    not black(r2, c2).

But the shading space could be reduced by:

    { black(R, C) } :- grid(R, C), not clue(R, C).
    clue(R, C).

We are unsure whether the second approach is better.