testing issues

[icecream17]

The tests are complaining about how they take too long

[icecream17]

I've added a test to time strategies

Note; this is outdated

speed

With the new fish general function, the fish methods are definitely faster! Yay, results there (with pairsTriplesAndQuads unchanged) are listed alongside

checkForSolved:               3634ms
updateCandidates:              526ms
hiddenSingles:                3913ms
intersectionRemoval:         60706ms
pairsTriplesAndQuads:        27710ms
hiddenPairsTriplesAndQuads:  20615ms     23555ms
xWing:                       34913ms     16655ms
swordfish:                   88537ms     40345ms
jellyfish:                  163236ms    107867ms
skyscraper:                  36366ms
yWing:                         684ms
twoMinusOneLines:           161803ms
xyzWing:                       836ms
xyLoop:                    1139485ms
xyChain:                    430316ms

But I don't want to wait >1000ms. So introducing... speed!

  console.log
    checkForSolved did 70383 sudokus in 10003ms
    speed: 7.0361891432570225

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    updateCandidates did 151132 sudokus in 10001ms
    speed: 15.111688831116888

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    hiddenSingles did 165001 sudokus in 10002ms
    speed: 16.496800639872024

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    intersectionRemoval did 10786 sudokus in 10001ms
    speed: 1.0784921507849214

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    pairsTriplesAndQuads did 4543 sudokus in 10001ms
    speed: 0.45425457454254575

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    hiddenPairsTriplesAndQuads did 32311 sudokus in 10001ms
    speed: 3.2307769223077694

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xWing did 69621 sudokus in 10002ms
    speed: 6.960707858428314

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    swordfish did 19107 sudokus in 10001ms
    speed: 1.9105089491050895

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    jellyfish did 4035 sudokus in 10003ms
    speed: 0.4033789863041088

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    skyscraper did 65915 sudokus in 10001ms
    speed: 6.59084091590841

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    yWing did 214486 sudokus in 10003ms
    speed: 21.44216734979506

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    twoMinusOneLines did 4531 sudokus in 10001ms
    speed: 0.4530546945305469

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xyzWing did 226105 sudokus in 10001ms
    speed: 22.608239176082392

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xyLoop did 2670 sudokus in 25684ms
    speed: 0.10395577012926335

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xyChain did 2324 sudokus in 28779ms
    speed: 0.08075332707877271

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

Part 2:

  console.log
    checkForSolved did 71800 sudokus in 10001ms
    speed: 7.17928207179282

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    updateCandidates did 151632 sudokus in 10001ms
    speed: 15.161683831616838

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    hiddenSingles did 172988 sudokus in 10001ms
    speed: 17.2970702929707

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    intersectionRemoval did 10620 sudokus in 10001ms
    speed: 1.0618938106189382

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    pairsTriplesAndQuads did 4451 sudokus in 10003ms
    speed: 0.4449665100469859

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    hiddenPairsTriplesAndQuads did 31993 sudokus in 10003ms
    speed: 3.1983404978506447

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xWing did 69812 sudokus in 10001ms
    speed: 6.98050194980502

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    swordfish did 19791 sudokus in 10001ms
    speed: 1.9789021097890211

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    jellyfish did 4465 sudokus in 10002ms
    speed: 0.4464107178564287

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    skyscraper did 66904 sudokus in 10001ms
    speed: 6.68973102689731

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    yWing did 218234 sudokus in 10001ms
    speed: 21.821217878212178

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    twoMinusOneLines did 4383 sudokus in 10004ms
    speed: 0.43812475009996

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xyzWing did 230451 sudokus in 10001ms
    speed: 23.042795720427957

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xyLoop did 2670 sudokus in 26763ms
    speed: 0.0997646003811232

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

  console.log
    xyChain did 2324 sudokus in 28158ms
    speed: 0.08253427089992187

      at Object.<anonymous> (src/Api/Strategies/timeStrategies.test.ts:61:12)

Strategy optimization ideas

links

Maybe connected candidates together with links and using the resulting graph to detect strategies would be much faster.

It could really help in xyChain and xyLoop

xy wing

In this sudoku, the last xy-wing can be shortened

800200001
090008036
041500000
060000000
000030040
000004095
030087904
080000000
900006807

original: 57 71 13 34 42 28 87 71 12 21 14 45 54 45
shorter: 57 71 13 34 42 28 87 71 12 21 14 45

weird

106500000
000034000
000800590
000000009
021000600
040090800
080672003
003000260
004300000

unoptimal xy-wing
unoptimal xy-wing
weird xy-loop (see page + image) [two 7s are the same color]
[goes 25 12 12 12 27 47 49 19 59 79 57 57 27 and then back to 25]

[icecream17]

Although speeding up strategies isn't very important. Maybe I should remove the lazyloaded prop handling and just load everything on start

[icecream17]

As long as the strategies last shorter than 0.1 seconds (and with go, 0.001 seconds) then speed doesn't matter too much actually

[icecream17]

So I think the actual thing I need to rewrite is the Solver API itself