Fast web-based solver for sudoku variants

Programs which generate, solve, and analyze Sudoku puzzles

Re: Fast web-based solver for sudoku variants

Postby sigh » Thu Nov 11, 2021 12:17 pm

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


Thanks for those pointers. I've updated my parsing to understand all the diagonal chars in the 81-char format.

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


I didn't know that was the convention. Luckily it was a very simple change, fixed now.

You're second example is significantly harder than the first for my solver! 940ms vs 50ms. I also found a couple of more improvements, so my updated timings in the latest version are:

Code: Select all
Case                    Chrome
------------------------------------
Wecoc #1                 .6s
Wecoc #1 mod A          1.1s
Wecoc #1 mod B *        2.6s
Wecoc #2                 .1s
tarek unsolvable #41     .06s
sigh
 
Posts: 22
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Thu Nov 11, 2021 2:02 pm

.
Confirmed zero-sums are now handled gracefully, thanks!

sigh wrote:Your second example is significantly harder than the first for my solver! 940ms vs 50ms.

Yes, with two or more zero-sum-cages the constraints are generally much weaker ...

sigh wrote:I also found a couple of more improvements ...

Yes, I had noticed!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby sigh » Tue Nov 16, 2021 2:07 pm

I hit a nice milestone: All the puzzles I've tested solve in under 1s :)

Code: Select all
Case                    Chrome
------------------------------------
Wecoc #1                 .22s
Wecoc #1 mod A           .55s
Wecoc #1 mod B *         .33s
Wecoc #2                 .15s
tarek unsolvable #41     .04s

* "Wecoc #1 mod B" has 6 solutions which it takes my solver 2s to find.

tarek's 42 unsolvable puzzles take a total of 0.9s to complete.
Mathimagics' 0-cage puzzle is now the hardest taking 0.64s.

Although there are surely many possible improvements, it's getting harder to find optimizations which don't hurt a subset of the cases more than they help.
sigh
 
Posts: 22
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Wed Nov 17, 2021 4:35 pm

sigh wrote:it's getting harder to find optimizations which don't hurt a subset of the cases more than they help.

The latest version seems to demonstrate this. In most cases it's faster, sometimes many times faster - but there are the occasional exceptions.

Here are some exceptions, tagged with #of guesses before & after:

Code: Select all
M<<<R<<<N^N<<<^Q>^N<<^O<^S^^L>>^>^^^^^<T6^>^NR^>^R<<^^^^^>^U>>^^<^N>^<<N^>>^<>>>^ #   533523     770285
R<<<P<<<S^L<<<^V>^Q<<^K<^M^^Q>>^>^^^^^<R7^>^LL^>^L<<^^^^^>^Q>>^^<^U>^<<Q^>>^<>>>^ #   426566     478255
M<<<T<<<O^O<<<^R>^N<<^N<^N^^N>>^>^^^^^<U7^>^OO^>^M<<^^^^^>^U>>^^<^R>^<<N^>>^<>>>^ #   698321    1556843


It's hard to provide more examples, since these are the few puzzles for which I have recorded the previous version's guess count.

I do have the previous version downloaded, but am unable to run it locally ... is there any way to make a standalone page that can be run locally (i.e. without jekyll) ?

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

Re: Fast web-based solver for sudoku variants

Postby sigh » Thu Nov 18, 2021 11:32 am

Mathimagics wrote:I do have the previous version downloaded, but am unable to run it locally ... is there any way to make a standalone page that can be run locally (i.e. without jekyll) ?


I'll have a look at making this easier to run locally, but that won't help load earlier versions...

jekyll is only used to append a version hash to the script loads in index.html so that caching works correctly. These script loads in index.html need to be changed (manually or programmatically).
Also, the solving runs in a Web Worker (this is why the page is still interactive while solving), and some browsers don't allow those to be loaded from file. If this is the case for you, you'll need to serve the files via a http server.

To solve the first issue try loading index.html from disk and pasting the following into the javascript console in your browser (or stick it in a script tag in index.html):

Code: Select all
function f(tag, attr, newS) {
  for (const s of [...document.getElementsByTagName(tag)]) {
    if (s[attr].includes('%7B')) {
      newS = document.createElement(tag);
      newS[attr] = s[attr].match(/(\/|css)[a-z_\/]+\.(js|css)/)[0];
      newS.rel = 'stylesheet';
      newS.async = false;
      document.head.append(newS);
    }
  }
  return newS;
};
f('link', 'href');f('script', 'src').onload=()=>initPage();


Alternatively, you can solve it by directly editing index.html. On my system the following commands will do the two steps above:

Code: Select all
  # Replace the jekyll directives in index.html with direct references to the files.
$ sed -i '' "s/{{ '\\(.*\\)' .*}}/\\1/" index.html
  # Serve the files at http://localhost:8000/ - you may not need this
$ python3 -m http.server


Btw, if you are are just running the solver without needing to use the UI, then you can control a lot from the javascript console:

Code: Select all
await loadDebug();  // Load the debugging code.
loadInput(puzzle);  // Load a puzzle onto the page (same as the "Load from text" box).
await runAllWithChecks([puzzle1, puzzle2, ...]); // Runs all the listed puzzles, prints solving stats, and returns solutions.
runAll([puzzle1, puzzle2, ...]);  // Same as above, but doesn't return the solutions.


Mathimagics wrote:It's hard to provide more examples, since these are the few puzzles for which I have recorded the previous version's guess count.


Thanks the examples! Note that the "cost" of a guess is not necessarily consistent across versions, but it is usually a good proxy for the amount of effort required to solve the puzzle.
sigh
 
Posts: 22
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Thu Nov 18, 2021 1:50 pm

.
Ok, I should point out that I am under a double-disadvantage here - I use Win64 (with Edge browser), and I know next-to nothing about web software.

I did manage to test your first example, placing the script code (wrapped in <script> </script> tags) into the header of the index.html file.

Opening this with the browser looked good initially - the layout now closely resembles ISS, but significantly, there is still no grid display, and "Load from text" doesn't appear to do anything.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby sigh » Fri Nov 19, 2021 10:16 am

Ah, that sounds like the scripts loaded fine but it couldn't run the solver because the browser refused run a web-worker from a file on disk, so it needs to be loaded via a http server. Unfortunately the web-worker is critical for both speed and functionality of the page.

Here is a bare-bones interface to the solver which finds a solution and proves uniqueness: https://gist.github.com/sigh/2febe2a3c5 ... 284a6c8ec5
Place it in the same directory as index.html, then open it in your browser. It is slower, and can't be aborted, but all the stats will be the same.
sigh
 
Posts: 22
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Fri Nov 19, 2021 11:10 am

Thank you! That works fine ... and I can use it with previous version(s) 8-)

The solver appears to be just as fast as running the web-page, by the way.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby 100beep » Wed Jun 15, 2022 3:45 am

Any chance you could add support for other grid sizes?
100beep
 
Posts: 6
Joined: 15 June 2022

Re: Fast web-based solver for sudoku variants

Postby sigh » Wed Jun 15, 2022 10:38 am

100beep wrote:Any chance you could add support for other grid sizes?


Probably not anytime soon.

What sizes were you interested in? And with which variants?
Quite a few of the current optimizations won't scale well to larger sizes, so it would take a fair bit of work.
sigh
 
Posts: 22
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby 100beep » Sat Jun 18, 2022 11:45 pm

sigh wrote:
100beep wrote:Any chance you could add support for other grid sizes?


Probably not anytime soon.

What sizes were you interested in? And with which variants?
Quite a few of the current optimizations won't scale well to larger sizes, so it would take a fair bit of work.


16x16, and between lines would be at the top of my wishlist.
I really don't know anything about how this works, so I'll just have to take your word for it. I was unaware that it wouldn't be so easy as increasing it scaling up. I'd be happy with it even if it wasn't quite so fast, honestly.
Thanks!
100beep
 
Posts: 6
Joined: 15 June 2022

Re: Fast web-based solver for sudoku variants

Postby sigh » Sun Jun 19, 2022 3:42 am

Adding Between lines on the existing size is fairly easy. I updated it and between lines constraints should work now: example

I might look at 16x16 when I have some time. There is a bunch of tedious but easy work to update the UI, a bunch of possibly harder work to ensure the solver handles it correctly and a bit of due diligence to understand the standards around 16x16 puzzles.
sigh
 
Posts: 22
Joined: 01 September 2021

Re: Fast web-based solver for sudoku variants

Postby Mathimagics » Sun Jun 19, 2022 6:57 am

.
Scaling up to 16 x 16 grids is always going to be problematic.

With any DFS (depth-first search) solver, there are "worst-case" puzzles that can push the solver to its limits. For 9x9 grids, the worst-case puzzles might only take a few seconds (I think that I gave some examples of Killer Sudoku's), but for 16x16 puzzles the time scale could easily stretch to minutes, if not hours.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Fast web-based solver for sudoku variants

Postby 100beep » Sun Jun 19, 2022 7:41 pm

Well, wasn't expecting an update this fast. Thanks!
Would it be possible to do the 16x16 unoptimized and publish optimizations as you go? At this point, anything would be better than what I'm using now, which takes anywhere between 1.5 and 6 hours each time I try and can't be aborted.
100beep
 
Posts: 6
Joined: 15 June 2022

Re: Fast web-based solver for sudoku variants

Postby sigh » Mon Jun 20, 2022 5:22 am

100beep wrote:At this point, anything would be better than what I'm using now, which takes anywhere between 1.5 and 6 hours each time I try and can't be aborted.


Oh, have you got some examples of puzzles which are taking hours to solve? That'll let me get a good idea if I'll be able to get the solver to handle them sensibly.
sigh
 
Posts: 22
Joined: 01 September 2021

PreviousNext

Return to Software