General Notes

• This program needs to examine over 270 thousand trillion possible combinations of piece order, piece orientation, and piece location.
  
  
• The program tries to place the 12 pieces into the puzzle in every possible order (permutation). It does this by scanning the puzzle board -- across and down -- to locate an empty cell. It then checks to see if the piece will fit with the "key" monomino in that cell. If not, it rotates and/or flips the piece (cyles the orientation). If it can't fit the piece, it generates the next permutation of the remaining pieces and starts again with the first piece of that list.
  
  When it gets to the point where no more pieces fit, it checks to see if the puzzle is solved, and if not, "backs up" to a previous state (an earlier permutation) and continues.
  
  
• Watch the status line. The program immediately finds reasonable positions for the first four or five pieces, then frantically (but methodically!) juggles the rest as it looks for a solution. Eventually, all of those pieces are ruled out, and it backs off; you'll see, position four change. Then much later, position three changes.... it is a loooog time before a different first piece is chosen (over 12 hours).
  
  
• I start with the arbitrary sequence "FLUPYXZTSWVI". You can try different sequences to see if you find solutions faster. The variable is set near the top of the program.
  
  
• The program runs nearly twice as fast if you remove the display logic (comment out the line in the PlacePc function that sets document.images[] ). But if speed were the object, I would not be writing in an interpreted language like JavaScript.
  
  

Recursive Algorithm

• My favorite version of this program uses a recursive algorithm that boils down to "solve from here" in which here is the list of available pieces and a "board" object that tells what squares are filled.
  
  Each "solve from here" places the first piece from the list into the board, then calls itself, passing as a parameter, the (now shorter) list. Upon return, it removes the piece and tries a different orientation and loops until all orientations are tried.
  
  
• Alas, this technique cannot be used in JScript because the resulting function runs continuously, without giving the system a chance to process button clicks, etc. (see below).
  
  

Quantum Algorithm

• Internet Explorer is not happy with JScript programs that take too long to finish. In this respect, JScript is a "toy" language. Furthermore, IE5 refuses to update the screen until an event (such as the hanlder for a click of a button) has completed.
  
  So, to prevent what appears to be a screen lockup, I needed to rewrite my beautiful recursive solution so that it searches in "quanta" -- single steps.
  
  For what it's worth... this is not a fatal flaw in JScript. It's great for handling simple events like button clicks and mouse-overs. Very few programs designed for embedding in HTML need to perform continuously. That's probably why this deficiency has never been fixed.
  
  
• Each quanta is a single action of placing a new piece or removing a piece. There may be many intermediate steps (trying to find a piece that will fit), but they don't need to be displayed, so they all take place within a single quanta.
  
  
• On a click of the [Start] button, the program fires off a series of interval timers. Each timer calls the same function ProcessState(). By starting multiple timers, I can soak up all available CPU cycles without waiting for the minimum interval (1ms -- 1/1000th of a second; a long time to a 1GHz computer).
  
  
• The result is that the program is able to respond to clicks and as a bonus, IE does not lock up.
  
  

Dual Window Experiment

Browser Compatibility

• This works with Internet Explorer 5
  
  
• This starts to work with Netscape Navigator 5, but the [Cancel] button does not respond (click [Reload]) and a JavaScript error occurs when the program finds the first solution. This might be easy to fix, but who cares?