New Member Hello

[Colin Fiat]

Hello all,

Occasionally I get the urge to be creative numerically. Occasionally this leads me to
experiment with something requiring speed.

In the past I've investigated several aspects of set theory including Covering Designs
and similar.

My current flight of fancy is Sudoku.

History:
1980's - hand assembling Z80 code (using TRS80 system debugger JKL)
1990's - 68000 assembly (amiga)
2000's - X86

I'm glad to be a member.

[Vortex]

Hi Colin,

Welcome to the forum.

[dedndave]

welcome to the forum, Colin   :U

one of our members, Paul, has a sudoku game available
http://pbrennick.freehosting.net/

another member, Ray, works with Project Euler, which you might enjoy...
http://projecteuler.net/

Ray has also written libraries and a great tutorial for the FPU
http://www.ray.masmcode.com/

[daydreamer]

welcome colin

[Colin Fiat]

Thanks Vortex, daydeamer, and dedndave,

I found Project Euler yesterday, or was it the day before? The result came from
searching for anything interesting related to Sudoku. Their list of 50 hard puzzles was
pleasingly trivial for the basic logic solve function I'm working on. Prior to that was a
page devoted to 17 clue puzzles (as 16 clue puzzles have been found not to exist
thanks to Project Sudoku. Just as pleasing, 88% of the 50 thousand 17 clue puzzles
were solved by the function. Did better than I expected.

I shall be getting myself a coffee in a moment before digging into Paul's Sudoku page,
thanks very much for that.

As for FPU processing, even that will not help with the staggering quantity of
permutations Sudoku presents. (6670903752021072936960 actually)

However, perhaps Paul has been attempting to find shortcuts, as I have, rather than
brute force everything. I'm quite proud to have discovered a simple modification to
one complicated rule to help average humans remove a hidden possibility; even if it
occurs only once in several thousand games... Oh well, one can but try.

I've been browsing the site and have enjoyed many of your posts, dedndave.

I love the Stats page and can only apologize for increasing the 99.7:1 gender ratio...

[dedndave]

for handling numbers larger than 20 (19.5) digits, you can use a bignum library like the one Drizz has been working on
http://drizz.has.it/ (look under Downloads on the left)

some time ago, i wrote a set of routines that will convert very large integers to ASCII...
http://www.masm32.com/board/index.php?topic=12363.msg94779#msg94779

and another for playing with large integer exponentiation...
http://www.masm32.com/board/index.php?topic=12363.msg100575#msg100575

[Colin Fiat]

Thanks dedndave, but there's no need for large number calculations. 90% of my
current project uses 3 or 9, there's one counter to 81 and several instances of 511 as
a mask. But that's all. I spent days thinking about data representation. And the
method I used is so simple that my first solver was written in JavaScript.

Lexicographical indexing has been mentioned in a few technical specs about
enumerating complete puzzles but if I were to contemplate scanning all permutations it
would either be odometer style for 81 digits or a recursive swap algorithm.

I've dabbled with both lexicographical indexing and large number arithmetic. The latter
required only the 4 basic operations so ADD and SUB over an open ended binary string
would have permitted calculation limited by the size of available ram. Even with Lexi
indexing, taking the time to generate a chart would allow for simple addition when
computing a sudoku puzzles index.

Actually, in retrospect, lexicographical indexing may not be feasible as I do not have a
spare billions years. Hmmm, hang on... ideas are afoot...

edit: cancel that, generating a bitmap of valid/invalid puzzles requires 758291207 TeraBytes

[dedndave]

i hear ya   :P
when i played with that stuff, i found that logic was more important than math
but, it's nice to be able to calculate the combintations and permutations

[FORTRANS]

Hi,

   I obtained some Sudoku solvers in ASM off the usenet groups,
and a Hugi compo.  Anyway this paper caught my eye at one
point.  I'm afraid I never got anything useful from it.  But it's a
nice read.


Nonrepetitive paths and cycles in graphs with application to Sudoku.
D. Eppstein.

Cheers,

Steve N.

[Colin Fiat]

Thanks Steve,

That's a great page you pointed out, not only for the Sudoku link but for all the other
inconsequential proofs and theorems related to pointless mathematical abstractions. I love
that kind of junk food for the mind.

[raymond]

Welcome Colin.

1980's - hand assembling Z80 code (using TRS80 system

This brings back memories. That's how I also got started with "assembly". One of my first programs was a "disassembler" to learn how the OS was functioning. I also wrote a crude "word processor" for use with my TTX printer (upper case letters only). I eventually got tired of "patching" and hand coded my own assembler (there were only some 800 instructions at that time). What a difference from hand coding after that! :dance:

As for Project Euler, that site started about 10 years ago. What made you discover it only recently? I'm sure you are going to enjoy it for many years if you like solving math problems and write short programs.

[Colin Fiat]

Thanks for the welcome Raymond,

I loved walking into a store with new TRS-80's (or Dick Smith System80's) and loading
the debugger with the following at mem 32000 and executing then leaving:

21 00 00 11 00 3c 01 ff 03 ed b9 18 f7

Code Select Expand

LD HL,0000
lp: LD DE,3c00
LD BC,03ff
LDIR
JP lp

Actually using an assembler with an Amiga 2000 (68000) was a big jump to my way of
thinking. It also opened up a wide range of programming projects.

Project Euler: the internet is a big place! The link there was on a page about 17 clue
Sudoku puzzles. Before that I'd have no reason to enquire about any of the math
problems the site has to offer.