home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / rec / games / chess / 11833 < prev    next >
Encoding:
Internet Message Format  |  1992-12-29  |  2.5 KB
  1. Xref: sparky rec.games.chess:11833 rec.puzzles:8080 comp.unix.shell:5125
  2. Path: sparky!uunet!pipex!bnr.co.uk!uknet!keele!nott-cs!piaggio!anw
  3. From: anw@maths.nott.ac.uk (Dr A. N. Walker)
  4. Newsgroups: rec.games.chess,rec.puzzles,comp.unix.shell
  5. Subject: Re: A puzzle for Christmas
  6. Message-ID: <1992Dec21.182336.14578@maths.nott.ac.uk>
  7. Date: 21 Dec 92 18:23:36 GMT
  8. References: <1992Dec18.200400.19070@maths.nott.ac.uk>
  9. Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
  10. Organization: Maths Dept., Nott'm Univ., UK.
  11. Lines: 55
  12.  
  13. In article <1992Dec18.200400.19070@maths.nott.ac.uk> I wrote:
  14. >While at a conference recently, I picked up a neat little sliding-block
  15. >puzzle with a chess theme.
  16. [...]
  17. >    If you want to construct [the solution] yourself, "unshar" the files
  18. >below into some unused directory, and type "run".  [...]
  19. >While "run" is running, there is also a large database, which grows to
  20. >around 19 meg;  this has to be sorted, so another 19 meg is needed, total
  21. >44+ meg.
  22.  
  23.     Thanks to Andy Walker, anw@maths.nott.ac.uk, for pointing out that
  24. this database and its sorted version are completely unnecessary, as I knew
  25. at one stage and had forgotten.  In a sliding-block puzzle with a bipartite
  26. graph and in which all moves are reversible, those positions which are
  27. first reached in N moves are exactly those which are obtained by playing
  28. one move from those first reached in N-1 moves and stripping those which
  29. are first reached in N-2;  there is no need to strip also those first
  30. reached in N-4, N-6, ....
  31.  
  32. >    On a Silicon Graphics workstation, the "run" script takes around
  33. >1h45m to complete;
  34.  
  35.     The revised version [below] runs in 13 minutes instead, and is
  36. probably fast enough even on a Sparc or a PC not to need re-coding in C;
  37. also, only 6M of storage, instead of 44M, is needed.  Replace the version
  38. of "run" given in the original shell archive by the one below the "snip"
  39. line.
  40.  
  41. -- 
  42. Andy Walker, Maths Dept., Nott'm Univ., UK.
  43. anw@maths.nott.ac.uk
  44.  
  45. ====8<========8<========8<========8<========8<========8<========8<========8<===
  46.  
  47. #! /bin/sh
  48.  
  49. # This file is Copyright 1992 A. N. Walker, anw@maths.nott.ac.uk
  50. #    Permission is hereby granted to use it freely for academic or
  51. # private purposes, provided that this notice is retained and any changes
  52. # noted in versions made available to other people.
  53.  
  54. case $1 in
  55.     [0-9]*) nn=$1 ;;
  56.      *) echo kBWB:BWFW:KBDD:EWBW 1 D0 > l0 2> l-1
  57.     nn=0
  58. esac
  59.  
  60. nminus=`expr $nn - 1`
  61. while test -s l$nn
  62. do    nplus=`expr $nn + 1`
  63.     generate l$nn l$nminus l$nplus
  64.     compress l$nminus
  65.     nminus=$nn
  66.     nn=$nplus
  67. done
  68.