枝豆(@ek_bm)/2022年09月09日

ペンシルパズルを解くのはNP完全
（解が存在するNP困難問題に対して、多項式時間で検証できる解を一つ出力する）
だけど、
ペンシルパズルを機械が解く時に実用的に求められているのは
「別解がないこと」の確認なのでNP完全には属さないよなっていう話思い出した。

タグ：

posted at 01:27:35

非公開

タグ：

posted at xx:xx:xx

めるるん @melvy_mag

Wordle 447 4/6

⬜🟨⬜⬜⬜
⬜🟨⬜⬜🟩
⬜⬜⬜🟨🟩
🟩🟩🟩🟩🟩

タグ：

posted at 02:58:59

fff @puzzlerfff

一筆書き最小ヒント研究がされてなさそう、確かに
ループじゃない分シンプルループから結果がかなり変わりそうな気がします
(パズル界でこのタイプの一筆書きがあまりメジャーではないので研究されてない？)

タグ：

posted at 09:34:39

@puzlab @ark184 平面グリッドグラフの部分グラフ上での3彩色問題と考えると示されてそうに見えます

www.sciencedirect.com/science/articl...

タグ：

posted at 10:11:59

壁がない4x5全マス通過一筆書き盤面を教えてもらった pic.twitter.com/MBlFu8gL4o

タグ：

posted at 10:37:10

メタプレースの小パズルがNP-Completeで
メタプレース自体はΣ_2P-Completeかな

タグ：

posted at 14:21:09

稲葉直貴（パズル作家） @puzlab

パズルの作者名が意識されないのは未だパズルというものが世間的に創作物として十分に認められていないことの証左と捉えていたので、この視点は興味深いです。 twitter.com/propara/status...

タグ：

posted at 16:17:51

fff @puzzlerfff

クィアウルフ（ダイナモでなぐるマン） @xevs99

2×2×1 13個 in 4×4×4のアンチスライディングパズルが唯一解なのは奇跡だと思ってる

タグ：

posted at 17:37:45

@puzzlerfff 12個の解ができたけどそこから13個が構成できなそう…？

タグ：

posted at 17:43:59

ﾜ……! pic.twitter.com/RQ5C6MEuYp

タグ：

posted at 21:17:39

掲載誌ありがとうございます。

タグ：

posted at 21:20:56

ワを作るパズルたのしいです。

タグ：

posted at 22:29:12