The New Sudoku Players' Forum

[sigh]

I made a web-based solver for various sudoku variants including: killer, little killer, thermo, sandwich and others.

See it at https://sigh.github.io/Interactive-Sudoku-Solver/

It doesn't attempt to show human solving techniques, but I've found it a fun way to explore how different constraints affect the possible solutions of a grid.

[999_Springs]

i really like this for killer sudoku! this is the only brute-force killer sudoku solver i have seen that does not require a download, and it's easy to use - and it may be the fastest one i know of

i had a play around with it trying to test the sudokus in this thread, which are the hardest killer sudokus that i know of based on time to brute-force, and these are the results i got to confirm a unique solution:

Wecoc #1: 19.8 seconds
Wecoc #1 with 3-cell 6-cage in block 5: 74.5 seconds
Wecoc #2: 282 seconds
tarek's unsolvable #41: 219 seconds
mith's White Room: 0.013 seconds (for comparison)
HATMAN's 14-cage: 0.209 seconds
Wecoc #1 with 3-cell 18-cage in block 5 (invalid): 344 seconds for first 2 solutions

these times are faster than the ones posted in that thread from other solvers, so this may be the fastest killer sudoku solver i know of! i haven't used those other solvers so can't make a direct comparison but this is very impressive - well done

i might check out some of the other variants if i find some nice hard puzzles to test them with

can i suggest that a puzzle should not automatically solve even when partially entered? when i was testing these i had to click "abort" after entering each cage as it would try to solve it every time which was a distraction

you spelt "possibilities" wrong in the drop down menu next to the grid

[1to9only]

On the subject of 'Web-based solver for sudoku variants', I've come across this: https://sudokuspoiler.azurewebsites.net/ - it does not have a solver for killers and sigh's other variants, but has solvers for vanilla sudoku and a number of other sudoku variants, AND it does support some sudoku sizes besides the standard 9x9.

Disclaimer: I've not used any of the web solvers mentioned in this thread.

[sigh]

i really like this for killer sudoku! this is the only brute-force killer sudoku solver i have seen that does not require a download, and it's easy to use - and it may be the fastest one i know of

Thank you for testing it, and the kind words! And for believing in it enough to wait for it to solve hard puzzles...

I hadn't seen those threads, thanks for pointing them out. Improving the killer performance was certainly the most fun, and frustrating part of this. These are a good tests if I come up with more ideas for making it faster.

can i suggest that a puzzle should not automatically solve even when partially entered? when i was testing these i had to click "abort" after entering each cage as it would try to solve it every time which was a distraction

you spelt "possibilities" wrong in the drop down menu next to the grid

I appreciate the feedback, I've fixed both of these. There is now a toggle for auto-solving.

By the way, the "Load from text" option supports the "3x3::k:..." format (whatever it's called), which is provided for a bunch of puzzles in that thread.

[sigh]

I improved the killer sudoku solving, and it's much faster now.

The solver seems to run faster on my computer than 999_Springs's so I've included my timings for the old version as well for comparison against the puzzles that 999_Springs used:

Code: Select all

Puzzle                Old (999_Springs)  Old    New
---------------------------------------------------
Wecoc #1               19.8s              14s    8s
Wecoc #1 mod A         74.5s              48s   24s
Wecoc #1 mod B *      344s               170s   68s
Wecoc #2              282s               143s   45s
tarek unsolvable #41  219s               118s   50s


* Wecoc mod B has 6 solution, the time given is time taken to disprove uniqueness. My new version takes 129s to find all 6 solutions.

Links to the puzzles in my solver: Wecoc #1 Wecoc #1 mod A Wecoc #1 mod B Wecoc #2 tarek unsolvable #41

I still have some ideas, so I hope to make it faster if I get the time.

[sigh]

So it turns out that the solver is much slow on Firefox, so I focused some optimization on the bottlenecks there:

Code: Select all

Case                 Chrome  Firefox
------------------------------------
Wecoc #1                 4s       8s
Wecoc #1 mod A          12s      21s
Wecoc #1 mod B *        31s      52s
Wecoc #2                10s      16s
tarek unsolvable #41    12s      21s


I also extended it to solve Jigsaw layouts, but not sure how efficient it is right now.

[Mathimagics]

Jigsaw mode seems to work OK. I tested this 8-clue Jigsaw Sudoku:

Code: Select all

......7....3.............8..............5.........6...1...........4......2.......
111111123144552223145522663445226633455266337456668397458888397488999997889977777


Solve time (Edge browser) was 0.3s, so that seems pretty efficient to me!

Since the post above, your Killer solve times have reduced (as you reported here). Now 3x faster on most of these, but tarek's #41 puzzle is now 100x faster!

What would you put that down to?

Cheers
MM

[sigh]

Thanks for testing the jigsaw solver. Working on the layout validation helped the solving as well, so your data is one of the reasons it's as fast as it is now.

Since the post above, your Killer solve times have reduced (as you reported here). Now 3x faster on most of these, but tarek's #41 puzzle is now 100x faster!

What would you put that down to?

Oh, that can mostly be attributed to a single change:

- When looking at jigsaw sudoku, I added extra constraints by taking advantage of the law-of-leftovers. I realised the same approach could find innies and outies for killer sudokus.
- This could infer constraints where [cell1 + ... + celln = sum] - however this wasn't where the big win was. In fact, there weren't any of these constraints to be found in the hard killers such as tarek#41.
- I could also infer constraints of the form [cell1 + ... + celln - cellm = sum]. i.e. finding the difference between innies and outies. I already had code to solve constraints of this form from solving Arrow sudokus, which have the same constraint with the sum = 0. This is also why I currently only handle a single negative cell in the sum.
- They are particularly useful because the cells can be quite distant and hence can help quickly propagate values to large portions of the grid.

I think tarek#41 simply yielded more constraints of this form (12), as opposed to something like Wecoc#1 which only had 4.

[Mathimagics]

.
With "Load from text", if there are problems with a PS string (the one-line killer definition), the solver goes into a hard loop and the page hangs:

Code: Select all

S<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O>>^^^>^W^<<^>^^O^<<^T^J^^^>>>^>^>^ML<S<<^^>^<^<<^<
S<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O><^^^>^W^<<^>^^O^<<^T^J^^^>>>^>^>^ML<S<<^^>^<^<<^<
                                !


[sigh]

Thanks for finding that! Fixed now.

[Mathimagics]

.
ISS rejects a PS string that includes a "v". I suspect that the problem is here in sudoku_builder.js:

Code: Select all

81:    if (!text.match(/[<V>^``]/)) return null;
82:    if (!text.match(/^[0-9A-Za-j^<V>``]*$/)) return null;


The V should be lower-case in both lines.

[sigh]

Yup, that's exactly it. I'd only used that format for tarek's unsolvable puzzles, which apparently don't have any 'v's. Fixed now.

[Mathimagics]

I referred previously to these 81-byte Killer strings as "PS" (Perfect Sudoku) strings. This is incorrect, PS actually refers to the "3x3::k" format.

tarek can probably tell us where the 81-byte format comes from. I think it comes from the "JSudoku" app?

Another common format is "SumoCueV1", which you don't support, but is probably not necessary at this stage ...

[1to9only]

See tarek's thread. There is a post towards the end when JSudoku added support for the 81-chars killer format.
The SumoCue format for killers is described by Ruud in this thread.

[Mathimagics]

.
ISS ignores cages with sum = 0.

Code: Select all

Z<<<<W<<<^S<<>^X<T>^j>>>^>^c^^<<>>^T^<<<^>>>^^S<<^<<V^>^L<<<^^<^>^U<>>^Q>>>^>>>>^
Z<<<<W<<<^0<<>^X<T>^j>>>^>^c^^<<>>^T^<<<^>>>^^S<<^<<0^>^L<<<^^<^>^U<>>^Q>>>^>>>>^


The first case has a unique solution. In the second case, two sums are replaced by 0, but the corresponding cages appear blank in the displayed grid, and are not listed in the cage display. The first solution found has repeated values in these cages.

Zero-sum cages should be considered valid, and interpreted simply as having the "all different" constraint.

Cheers
MM