mersenneforum.org What might really happen if P=NP?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2021-07-21, 14:18   #13
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×373 Posts

Quote:
 Originally Posted by LaurV Anyhow, as a way to go forward for your team, you could try to transform your algorithm to solve hamiltonian cycle or 3-sat, and I believe there are algorithms on the web to transform generalized sudoku into one of these or viceversa. Telling people about sudoku, they are reticent. Tell them about graphs and boolean circuits, you got them by the ears.
I tried that. It didn't pan out so far. There is almost a trivial relation to the Latin squares, but the rest is not as easy to do.

Quote:
 Originally Posted by LaurV If you don't believe me, try this grid, without guessing. Courtesy of Mark and Simon, from Cracking the Cryptic youtube channel (google them, it is fun!). This grid is trivial to solve by guessing, but almost impossible to solve by logic, as they proved in two videos. Then think about a 169x169 grid (with 13x13 biscuits) and tell my how would you solve THAT one in O(n^6) You can have few hundreds of chains, every one of them with a hundred links, and you will have to make few hundred guesses, fill each chain, and if the guess was wrong and you got a contradiction, you will need to backtrack and refill with the correct chain. I don't see other way. But again, I may be too stupid to be a Mozart, haha
I know them, great channel indeed!

I'll send you more details on inner working of the algorithm in PM (as well as the results of the experiment), but this I will say "publicly":

I should be able to get a solution in O(n^12) - unless I found a counterexample to the algorithm. In O(n^6), I should be able to tell you whether it's uniquely solvable, non-uniquely solvable, or non-solvable. The part about being able to distinguish between unique solutions and non-unique ones is not well-studied yet. It's only simple observation. But the same observation tells me, that if it is uniquely solvable, I should be able to get a solution in O(n^6).

EDIT:
After running the experiment, I found that at least for the present version of the algorithm, the striken is not true.

Last fiddled with by Viliam Furik on 2021-07-21 at 14:32

2021-07-21, 20:38   #14
Till

"Tilman Neumann"
Jan 2016
Germany

13·37 Posts

Quote:
 Originally Posted by LaurV Attachment 25315

Thanks, my 77-year old, sudoku-addicted mother will love it

2021-07-21, 21:12   #15
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×373 Posts

Quote:
 Originally Posted by Till Thanks, my 77-year old, sudoku-addicted mother will love it
You can google some n=4 grids for her, that's an even bigger challenge. I attached one such grid.
Attached Thumbnails

2021-07-21, 22:16   #16
jwaltos

Apr 2012
Gracie on lookout.

1A516 Posts

Quote:
 Originally Posted by Viliam Furik That's possible, but I doubt the script runs in polynomial time. Yes, they did. But none of them produced a general polynomial-time algorithm, as Wikipedia still states the problem is NP-complete.
Definitely no poly time script on a classical (binary) system that I'm aware of but there are some good solvers out there.

2021-07-21, 22:59   #17
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×373 Posts

Quote:
 Originally Posted by jwaltos Definitely no poly time script on a classical (binary) system that I'm aware of but there are some good solvers out there.
That's true.

 Similar Threads Thread Thread Starter Forum Replies Last Post EugenioBruno Information & Answers 21 2020-03-28 21:12 RichardB Information & Answers 16 2010-09-03 21:25 Uncwilly Lounge 11 2005-02-18 14:41

All times are UTC. The time now is 09:56.

Sun Jan 23 09:56:42 UTC 2022 up 184 days, 4:25, 0 users, load averages: 0.58, 0.94, 1.02

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔