News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

BT, BTS, BTR

Started by raymond, August 14, 2023, 04:00:29 AM

Previous topic - Next topic

raymond

Just found some use for those simple instructions to save a lot of computing time after all those years!

Almost 20 years ago, one of the provided problems on Project Euler involved designing a solver for the well known Sudoku puzzles. At the time, my brute force approach required a little less than 2 seconds to solve 50 puzzles and was fast enough for me to give up on improving that timing. A recent rewrite using the subject instructions brought the timing down to 0.1 second!!

The reason to look into this was due to a recent gift by an old lady which made me aware of a Sudoku variant, i.e. Tridoku. This revived my desire to design a solver for such puzzles. For those not familiar with that variant, a picture of a typical puzzle is included and the rules are as follows:

a) Each of the 9 main triangles must contain the digits 1-9.
b) Each of the 3 sides of the outer large triangle (shaded yellow) must contain the digits 1-9.
c) Each of the 3 sides of the inner triangle (shaded cyan) must contain the digits 1-9.
d) Finally, none of the distinct half- or full- hexagons must contain identical digits.

Note: The three tips of the inner triangle are shaded cyan but must also be considered as parts of a side of the outer triangle as "shaded" yellow.

Because of that last constraint, each individual cell can be part of a combination of up to 3 distinct hexagons, in addition to up to 2 sides of the outer triangle, up to 2 sides of the inner triangle and at least 1 of the 9 main triangles. And, since there are 52 distinct hexagons within the puzzle area, a better approach to designing a solver was required. Hence the use of the subject instructions.  :icon_idea:

So here's where I have been "wasting" some of my time lately. :eusa_boohoo:

The eventual solver required less than 0.2 seconds for 50 puzzles on my 10-year-old laptop.

This prompted me to write another program for myself, family and friends to "manually" solve such puzzles.
The attached .zip file contains the program executable, one data file with 40 'easy'  :winking:  puzzles, and a readme file. Other data files may be added later with more difficult puzzles. Eventually, I may provide the source file.

As usual, comments or inquiries are always welcome. Enjoy.

Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com

zedd151

#1
Very interesting, Ray. What does it look like when completely solved? All little triangles have a digit? I will play with this a bit later...  :biggrin:




Some time later...
I found some more info online about tridoku here:
http://www.tridoku.com/AboutTridoku.html

HSE

These are the "easy" ones?  :biggrin:  :biggrin:
Equations in Assembly: SmplMath

raymond

QuoteAll little triangles have a digit?
Right. All 81 of them.

QuoteThese are the "easy" ones?  :biggrin:
I've solved a few of them inside 10 minutes. But expect the average to be in the range of 15 minutes.
When you get some of the harder ones, many have taken me around 1 hour! :dazzled: But it is a good feeling when you fill in that last number.
Whenever you assume something, you risk being wrong half the time.
http://www.ray.masmcode.com

daydreamer

Great raymond
I hope you post 20 year old version + newer version 0.1 seconds in laboratory so we can test them
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding