home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2500 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  3.2 KB
  1. Path: sparky!uunet!usc!cs.utexas.edu!torn!news.ccs.queensu.ca!qucis.queensu.ca!ember!pacolley
  2. From: pacolley@ember.UUCP (Paul Colley)
  3. Newsgroups: comp.theory
  4. Subject: Re: Reassembling a checkerboard jigsaw
  5. Message-ID: <15446@ember.UUCP>
  6. Date: 21 Nov 92 18:57:25 GMT
  7. References: <rreiner.722360646@yorku.ca>
  8. Reply-To: pacolley@ember.UUCP (Paul Colley)
  9. Organization: Ember---private system
  10. Lines: 103
  11.  
  12. In article <rreiner.722360646@yorku.ca> rreiner@nexus.yorku.ca
  13. (Richard Reiner) writes:
  14.  
  15. >    - Given an n x n checkerboard which has been cut into pieces of
  16. >      varing size along the edges of its squares (i.e. no diagonal
  17. >      cuts),
  18. >
  19. >      Efficiently reassemble the pieces into an n x n board (the rebuilt
  20. >      board need not deploy the pieces exactly as the original did,
  21. >      although this would be preferable; ideally, I would like to be
  22. >      able to enumerate *all* the ways of rearranging the pieces into an
  23. >      n x n board).
  24.  
  25. The problem, "given a set of integers that sum to S, find a subset that
  26. sum to 0.5 S" is NP-complete.
  27.  
  28. This problem can be reduced to the stated checkerboard problem as
  29. follows:
  30.  
  31. Make an (S+1) x (S+1) square.
  32.  
  33. For each of the integers i,  Create a rectangular piece that is 2i long
  34. by 0.5 S wide.
  35.  
  36. Add an additional piece that is T-shaped, with the "bars" one unit
  37. wide, such that the T's total height is S+1 and total width is S+1.
  38.  
  39. I will give a small example to clarify the construction:
  40.  
  41.     Integers:  1,2,2,3 (sum S=8)
  42.  
  43. The pieces for the integers:
  44.  
  45.     XX    XXXX    XXXX    XXXXXX
  46.     XX    XXXX    XXXX    XXXXXX
  47.     XX    XXXX    XXXX    XXXXXX
  48.     XX    XXXX    XXXX    XXXXXX
  49.  
  50. The T-shaped piece:
  51.  
  52.     XXXXXXXXX
  53.         X
  54.         X
  55.         X
  56.         X
  57.         X
  58.         X
  59.         X
  60.         X
  61.  
  62. And the 9x9 board:
  63.  
  64.      .........
  65.      .........
  66.      .........
  67.      .........
  68.      .........
  69.      .........
  70.      .........
  71.      .........
  72.      .........
  73.  
  74. The extra T-shaped piece only fits in one way (modulo rotations), dividing the
  75. board into two equal areas, like so:
  76.  
  77.      ........X
  78.      ........X
  79.      ........X
  80.      ........X
  81.      XXXXXXXXX
  82.      ........X
  83.      ........X
  84.      ........X
  85.      ........X
  86.  
  87. The remaining pieces can be fitted in if and only if there is a subset
  88. that adds to 0.5 S (proof let as an exercise for the reader :-) ).
  89.  
  90. Thus the checkerboard problem is NP-complete.
  91.  
  92. Now, the original poster wasn't clear about whether the colouring
  93. of the squares was important (i.e., colour the pieces black and
  94. white in a checkerboard pattern when you create them, and be able
  95. to reassemble them back into a checkerboard colouring).
  96.  
  97. The reduction I gave is still valid if colouring is important; Each
  98. piece is an even number of units wide ("2i"), and the orientation
  99. that the pieces will be put in is known (if there is a solution,
  100. there is a solution with the T bar dividing the board horizontally
  101. and the pieces being placed with the 2i side against the dividing
  102. bar of the T).  So we can just colour the pieces so that they match
  103. a checkerboard when placed this way (and an even distance from the
  104. edge of the board)).
  105.  
  106. ----------
  107.  
  108. Thus the checkerboard problem is NP-hard.
  109.  
  110. - Paul Colley
  111. University:  colley@qucis.queensu.ca
  112. Home:        pacolley@ember.uucp   watmath!ember!pacolley  +1 613 545 3807
  113. <Ring> [...] "Sorry, I'm all booked up." "Who was that?" "The library." - B.C.
  114.  
  115.