Fast web-based solver for sudoku variants

Programs which generate, solve, and analyze Sudoku puzzles

Fast web-based solver for sudoku variants

Postby sigh » Thu Sep 02, 2021 10:56 am

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: 16
Joined: 01 September 2021

Re: Web-based solver for sudoku variants

Postby 999_Springs » Fri Sep 10, 2021 8:30 am

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: 576
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Web-based solver for sudoku variants

Postby 1to9only » Wed Sep 15, 2021 11:39 am

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: 3415
Joined: 04 April 2018

Re: Web-based solver for sudoku variants

Postby sigh » Mon Sep 20, 2021 8:30 am

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: 16
Joined: 01 September 2021

Re: Web-based solver for sudoku variants

Postby sigh » Sat Sep 25, 2021 4:22 am

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
 
Posts: 16
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby sigh » Sat Oct 02, 2021 3:17 am

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.
sigh
 
Posts: 16
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Wed Nov 03, 2021 6:58 am

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! :shock:

What would you put that down to?

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby sigh » Wed Nov 03, 2021 11:14 am

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! :shock:

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: 16
Joined: 01 September 2021

Bug report

Postby Mathimagics » Sat Nov 06, 2021 9:33 am

.
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<<^^>^<^<<^<
                                !
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby sigh » Sun Nov 07, 2021 7:56 am

Thanks for finding that! Fixed now.
sigh
 
Posts: 16
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Mon Nov 08, 2021 6:20 am

.
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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby sigh » Mon Nov 08, 2021 8:31 am

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: 16
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Mon Nov 08, 2021 9:20 am

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby 1to9only » Mon Nov 08, 2021 10:26 am

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: 3415
Joined: 04 April 2018

Support for "zero-sum" cages

Postby Mathimagics » Thu Nov 11, 2021 10:37 am

.
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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1829
Joined: 27 May 2015
Location: Canberra

Next

Return to Software