I call a variant sudoku "on interval [0,1]" ,in which the values may be assigned any real numbers in the closed interval [0,1].
In such a "variant", some methods are still applicable, and some are not.
Still OK:
- Full House / Hidden Single / Naked Single
- Subsets
- Standard Fish(X-Wing, Swordfish, etc.)
- Loops (X-Cycle, Y-Cycle, Bidirectional Cycle)
- MSLS and more loop/net-like methods(SDC, SK-Loop, specific types of Exocet)
Not OK:
- Open Chains(XY-Wing, XYZ-Wing, SE-6.6 X-Chains, and more)
- Uniqueness (We may disallow it even in normal classics)
In such rules, basic puzzles are still solvable, but there will be other non-01 solution if specific methods are used.
Current algorithm(introduction):
- 729=9*9*9 variables, representing the value of each digit in each cell, with initial values 1/9=0.111...
- Set givens: if Rx Cy =z, assign value[x][y][z]=1, and related cells value=0
- Target function:
--For each region and cell, loss +=(sum(values)-1)^2;
--or each candidate, if value>1 loss+=(value-1)^4; or value^4 if value<0;
- Gradient Descent with slight modification
==Above is a simple convex optimization.
-To faster the stabilization, if a value reaches 0.9, assume it is correct. Set candidates above 0.9 as 1 and related cells to 0 every 100 steps. I know this makes it no longer a guaranteed method, but I'm keeping it.
Sample: The puzzle
- Code: Select all
1.......5.5..3......2.4..............34...7.....2.6..12....5....7.....3.....61...
(edited from the 16-clue 2-solution puzzle below:
1.......5....3......2.4..............34...7.....2.6..12....5....7.....3......1...)
has no solution as Classic sudoku (due to 89 chains, but has a solution as this (assign 0.5*8+0.5*9)
Samples used as testing:
- Code: Select all
Solved:
.6..1..7.2.....36.....65.9.....3.7.93.48.......9...6.8.3.9.1...715.........3.7... 1.5/1.2/1.2 A simple puzzle generated by JSudoku
.9.2..3....7..3.1.....9.8.6.2.3..5.............6..7.3.3.4.6.....8.5..6....1..2.4. 6.5/6.5/2.6 X-Cycle 1to9only, Patterns Game Page 3449
..83.7..926....3.........4.3...521.87.4..8..5.5........8...6..7.....52....1...... 7.0/1.2/1.2 Yogi, How to spot a Sue De Coq
...5...8...7..8..5.8..2.4..9..1...2.1.......8.4...3..6..2.7..6.7..3..9...9...6... 3.2/3.2/2.6 Luo Siyuan 罗思远, Sudoku Grand Prix 2022 Round 3 Puzzle 4 gp.worldpuzzle.org
Could not solve:
61.5.829.78..245162..6.183.542763189961482375837159642178246953..6.1..28.2.8...61 5.6/5.6/2.6 BUG+1 from a Patterns-Game puzzle by JPF. This converges to (20/21)(precise)*BUG+(1/21)*Solution.
.....1..2.3....4....5.6..7......2..3..4.8.6..1..9......6..3.8....9....1.2..7..... 5.6/3.4/3.4 BUG+1 from a Patterns-Game puzzle by m_b_metcalf. Page 3460. This converges to 0.958(approx.)*BUG+0.042*Solution
.....1.....23..14..3.5..2.6.75...............2..1..5.7..76..3.26......8.3....9... A puzzle found by searching "JE4" in this forum. Managed to eliminate some 489s in Columns 568. But the Quad is no longer usable.
8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. A widely known "Hardest" sudoku with an MSLS in it, managed to find MSLS and get three digits.
Other uses:
Correcting mistakes(limited to techniques above): Set an incorrect answer as initial values
Managed to correct it, which costs at most 0.5*(time to complete it from default value) if not too far from solution.
Motivation:
In current Sudoku speedsolving contests, pointing/claiming intersections and subsets play an important role. Wings are rare, and SE6.6 chains are even rarer.
I was curious how can we spot subsets faster, and how to make more efficient t&e's. Sometimes I feel like the algorithm has already spotted subsets in fewer than 20 steps, and then keeps confirming them.
Other things:
Sometimes we can spot the solution from the converged non-01 result. How would this work.
How to make a better guess when chains are needed.
Supportive External Sources:
- Code: Select all
https://rileykenyon.github.io/img/2019/sudoku.pdf
This introduces a similar optimization method (using [0,1]), with 4 testing puzzles, with SE 1.5/2.0/3.2 and the "hardest" above. The 2.0 is not naked single, the 3.2 has alternative using only subsets. The program solves the first three, unsurprisingly.
I am glad to see other thoughts about it.
