## Fast web-based solver for sudoku variants

Programs which generate, solve, and analyze Sudoku puzzles

### Fast web-based solver for sudoku variants

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.
Last edited by sigh on Sat Sep 25, 2021 4:22 am, edited 1 time in total.
sigh

Posts: 20
Joined: 01 September 2021

### Re: Web-based solver for sudoku variants

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
999_Springs

Posts: 585
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

### Re: Web-based solver for sudoku variants

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.
1to9only

Posts: 4070
Joined: 04 April 2018

### Re: Web-based solver for sudoku variants

999_Springs wrote: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.

999_Springs wrote: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

Posts: 20
Joined: 01 September 2021

### Re: Web-based solver for sudoku variants

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    8sWecoc #1 mod A         74.5s              48s   24sWecoc #1 mod B *      344s               170s   68sWecoc #2              282s               143s   45starek 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

Posts: 20
Joined: 01 September 2021

### Re: Fast web-based solver for sudoku variants

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       8sWecoc #1 mod A          12s      21sWecoc #1 mod B *        31s      52sWecoc #2                10s      16starek unsolvable #41    12s      21s`

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

Posts: 20
Joined: 01 September 2021

### Re: Fast web-based solver for sudoku variants

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

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Fast web-based solver for sudoku variants

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.

Mathimagics wrote: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.
Last edited by sigh on Sun Nov 14, 2021 1:15 pm, edited 1 time in total.
sigh

Posts: 20
Joined: 01 September 2021

### Bug report

.
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<<^^>^<^<<^<                                !`

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Fast web-based solver for sudoku variants

Thanks for finding that! Fixed now.
sigh

Posts: 20
Joined: 01 September 2021

### Re: Fast web-based solver for sudoku variants

.
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.

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Fast web-based solver for sudoku variants

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.
sigh

Posts: 20
Joined: 01 September 2021

### Re: Fast web-based solver for sudoku variants

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 ...

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

### Re: Fast web-based solver for sudoku variants

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.
1to9only

Posts: 4070
Joined: 04 April 2018

### Support for "zero-sum" cages

.
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

Mathimagics
2017 Supporter

Posts: 1886
Joined: 27 May 2015
Location: Canberra

Next