\ eliminated some iForthisms in favour of Gforthisms - anton

\ Article: 112984 of comp.lang.forth
\ From: mhx@iae.nl (Marcel Hendrix)
\ Subject: Re: Sudoku puzzle solver
\ Newsgroups: comp.lang.forth
\ Message-ID: <38770920143562@frunobulax.edu>
\ Date: Sat, 3 Sep 2005 14:46:17 GMT
\ References: <18311112153562@frunobulax.edu> <98781222143562@frunobulax.edu> <4318ed8a.193669031@news.demon.co.uk>
\ X-Newsreader: iForth 2.0 console (3 February 2003)
\ X-Complaints-To: abuse@chello.nl
\ Organization: chello.nl
\ Lines: 148
\ NNTP-Posting-Host: 80.56.92.162 (80.56.92.162)
\ NNTP-Posting-Date: Sat, 03 Sep 2005 14:46:10 +0200
\ X-Trace: d618c43199b12f59df90724055
\ Xref: tunews.univie.ac.at comp.lang.forth:112984

\ stephenXXX@mpeforth.com (Stephen Pelc) writes Re: Sudoku puzzle solver
\ [..]
\ > Putting the timer around StartSolving on my P4 2.8GHz WXPpro box
\ > yields 3 ms on VFX Forth 3.80 build 1921. The timer resolution is
\ > 1 ms. I suspect that Rob's results are dominated by text display
\ > time.

\ Must be.

\ I whacked at Robert's source as hard as I could (without actually improving
\ the algorithm), and below are the results for 8 different grids. Each
\ grid is solved 1000 times and the times are averaged.

\ 	FORTH> speedthem ( 3 GHz PIVht )
\ 	0.496 milliseconds (originally 4.36 ms for the computer)
\ 	0.488 milliseconds (45 minutes human)
\ 	2.087 milliseconds (2 hours human)
\ 	0.464 milliseconds (2 hours for a human, maybe impossible)
\ 	0.041 milliseconds (unknown source)
\ 	0.080 milliseconds (Paul Hsieh example #1)
\ 	0.058 milliseconds (Paul Hsieh example #2)
\ 	0.058 milliseconds (Paul Hsieh example #3) ok

\ Changes involve the suggestion already done by Robert to count spaces
\ differently, some inlining, an unbeatable COUNTBITS, and unrolling.
\ I used the development version of iForth (4 free registers).

\ The grids used by Paul Hsieh are apparently particularly easy.

\ -marcel
\ -- ---------------------------------------------

\ These are the 8 grids used:

: rg 9 0 DO  PARSE-NAME >FLOAT DROP F>D D>S C, LOOP ;

CREATE grid0 
	rg      0 9 0  0 0 4  0 0 7
	rg      0 0 0  0 0 7  9 0 0
	rg      8 0 0  0 0 0  0 0 0

	rg      4 0 5  8 0 0  0 0 0
	rg      3 0 0  0 0 0  0 0 2
	rg      0 0 0  0 0 9  7 0 6

	rg      0 0 0  0 0 0  0 0 4
	rg      0 0 3  5 0 0  0 0 0
	rg      2 0 0  6 0 0  0 8 0
	," originally 4.36 ms for the computer" 

CREATE grid1 
	rg      0 0 6  0 5 0  0 0 0
	rg      0 7 0  0 3 9  1 0 0
	rg      0 8 0  0 0 0  0 3 0

	rg      0 0 0  0 0 2  5 1 8
	rg      0 0 0  0 0 0  0 0 0
	rg      7 5 9  8 0 0  0 0 0

	rg      0 6 0  0 0 0  0 7 0
	rg      0 0 2  5 9 0  0 4 0
	rg      0 0 0  0 6 0  3 0 0
	," 45 minutes human"

CREATE grid2 
	rg      9 2 0  0 0 0  0 0 8
	rg      0 8 0  0 0 0  0 5 1
	rg      0 0 1  5 0 0  3 0 0

	rg      0 0 0  9 0 7  8 0 0
	rg      0 0 0  0 0 0  0 0 0
	rg      0 0 3  6 0 2  0 0 0

	rg      0 0 6  0 0 4  7 0 0
	rg      5 7 0  0 0 0  0 8 0
	rg      8 0 0  0 0 0  0 9 3
	," 2 hours human"

CREATE grid3 
	rg      0 0 0  0 0 3  5 0 0
	rg      0 0 0  7 0 0  4 0 0
	rg      7 0 3  0 0 6  0 1 0

	rg      0 1 0  0 0 5  0 0 6
	rg      8 0 0  0 0 0  0 0 2
	rg      4 0 0  3 0 0  0 8 0

	rg      0 5 0  4 0 0  1 0 8
	rg      0 0 8  0 0 9  0 0 0
	rg      0 0 9  8 0 0  0 0 0
	," 2 hours for a human, maybe impossible"

CREATE grid4 
	rg      2 0 0  0 3 0  7 0 6
	rg      0 0 8  4 0 0  0 0 0
	rg      6 0 0  0 9 0  0 3 0

	rg      0 0 0  0 7 0  0 5 0
	rg      8 0 9  3 0 5  1 0 2
	rg      0 4 0  0 6 0  0 0 0

	rg      0 6 0  0 2 0  0 0 8
	rg      0 0 0  0 0 7  4 0 0
	rg      3 0 2  0 5 0  0 0 9
	," unknown source"

CREATE grid5
	rg      9 0 0  0 1 0  6 0 0
	rg      0 0 0  8 0 0  0 0 7
	rg      6 3 0  0 0 7  2 0 0

	rg      0 0 0  0 0 0  5 7 4
	rg      0 0 0  2 4 3  0 0 0
	rg      0 4 1  0 0 0  0 0 0

	rg      0 0 9  6 0 4  8 3 1
	rg      4 0 0  0 0 8  0 0 0
	rg      0 0 8  0 2 0  0 0 9
	 ," Paul Hsieh example #1" 

CREATE grid6
	rg      0 0 9  6 0 0  1 0 0
	rg      0 0 0  0 0 0  0 2 4
	rg      6 0 0  0 0 2  0 9 0

	rg      3 0 0  4 2 0  0 0 0
	rg      0 8 0  3 1 0  0 0 7
	rg      2 0 4  0 0 0  0 1 8

	rg      0 0 0  7 0 4  8 0 2
	rg      5 4 0  0 3 0  0 0 1
	rg      7 9 0  5 0 0  0 0 0
	," Paul Hsieh example #2"

CREATE grid7 
	rg      0 5 0  0 0 8  6 0 0
	rg      7 0 0  5 4 0  0 0 9
	rg      0 1 0  0 6 0  0 0 3

	rg      6 0 0  0 0 0  0 0 0
	rg      0 3 0  0 0 0  0 8 0
	rg      0 0 0  0 0 0  0 0 5

	rg      9 0 0  0 3 0  0 1 0
	rg      4 0 0  0 7 6  0 0 8
	rg      0 0 1  8 0 0  0 7 0
	," Paul Hsieh example #3"