;;;; Copyright 2003 Nils Goesche ;;;; ;;;; License: Do whatever you want with this code at your own risk. ;;;; Should solve a puzzle, but no guarantees whatsoever. ;;;; ;;;; Second submission #|| aka Third submission - NDL 2003-08-21 ||# ;;;; ;;;; Compile and load this file, then evaluate (puzzle:solve) ;;;; (defpackage "PUZZLE" (:use "CL") (:export "SOLVE")) (in-package "PUZZLE") ;;; For readability, we first represent pieces as lists of ;;; coordinate vectors. The first coordinate is always (0 0) ;;; and is chosen to be a square of the piece with slots! ;;; Later, these lists will be used to compute our real ;;; representation which is less readable. Note also, ;;; that we will think of the x-axis as going from right to ;;; left, so we reverse signs right now. #| (defparameter *piece-vecs* (mapcar (lambda (piece) (loop for (x y) in piece collect (list (- x) y))) '(((0 1) (0 2) (0 3) (1 2)) ; F ((-1 0) (0 1) (0 2) (0 3)) ; J ((-1 0) (-1 1) (-1 2) (-1 3)); L ((0 1) (1 1) (2 1) (2 2)) ; N ((0 1) (1 0) (2 0) (2 -1)) ; Q ((0 1) (0 2) (-1 2) (-1 3)) ; S ((1 0) (1 1) (1 -1) (1 -2)) ; T ((1 0) (0 1) (-1 1) (-1 2)) ; W ((1 0) (0 1) (-1 1) (-2 1)) ; Z ((-1 0) (0 1) (0 2)) ; j ((-1 0) (-1 1) (-1 2)) ; l ((0 -1) (-1 0) (-1 1)) ; s ((0 1) (0 2) (-1 1))))) ; t (defparameter *rotations* '(((1 0) (0 1)) ((0 -1) (1 0)) ((-1 0) (0 -1)) ((0 1) (-1 0)))) ;;; I've always wanted to use this matrix representation some time ;-) (defun dot-product (vector-1 vector-2) (reduce #'+ (mapcar #'* vector-1 vector-2))) (defun rotate-vector (matrix vector) (mapcar (lambda (row) (dot-product row vector)) matrix)) ;;; Don't worry about duplicates for now (defun compute-rotated-pieces () (loop for piece in *piece-vecs* collect (loop for rotation in *rotations* collect (loop for vector in piece collect (rotate-vector rotation vector))))) ;;; We will represent both a piece and the whole frame as a ;;; 64-bit number. The bits are ordered as follows: ;;; 63 62 ... 56 ;;; 55 54 ... 48 ;;; ... ;;; 07 06 ... 00 ;;; Two-dimensional coordinates: x-axis goes left, y-axis up (defun frame-ref (frame i j) (if (logbitp (logior i (ash j 3)) frame) 1 0)) (defun set-frame-ref (frame i j) (logior frame (ash 1 (logior i (ash j 3))))) (defun make-start-frame () (loop for ret = 0 then (set-frame-ref ret stone-x stone-y) for (stone-x stone-y) in '((0 0) (1 0) (1 1)) finally (return ret))) (defconstant +start-frame+ (make-start-frame)) |# (defconstant +start-frame+ 515) #| ;;; Now we compute every possible placement of a piece ;;; on the start-frame and collect its integer representation. ;;; Turns out there are 826 of them. (defun compute-placements () (loop for vec-list in (compute-rotated-pieces) collect (delete-duplicates (loop for vecs in vec-list nconc (flet ((convert-coordinates (start-x start-y) (let ((ret (set-frame-ref 0 start-x start-y))) (unless (logtest ret +start-frame+) (loop for (dx dy) in vecs for next-x = (+ start-x dx) for next-y = (+ start-y dy) do (unless (and (<= 0 next-x 7) (<= 0 next-y 7)) (return-from convert-coordinates)) (setq ret (set-frame-ref ret next-x next-y)) (when (logtest ret +start-frame+) (return-from convert-coordinates))) ret)))) (loop for start-y below 8 nconc (loop for start-x from (if (evenp start-y) 7 6) downto 0 by 2 when (convert-coordinates start-x start-y) collect it))))))) ;;; A strategic decision: Put unsymmetric pieces at the end of the list (defparameter *all-placements* (sort (compute-placements) #'< :key #'length)) |# (defparameter *all-placements* '((2154624 538656 275791872 68947968 17236992 141205438464 35301359616 8825339904 18074296123392 4518574030848 1129643507712 9254039615176704 2313509903794176 578377475948544 1184517070742618112 296129267685654528 74032316921413632 12599392 3149848 1612722176 403180544 825713754112 206428438528 51607109632 105691360526336 26422840131584 6605710032896 54113976589484032 13528494147371008 3382123536842752 6926589003453956096 1731647250863489024 432911812715872256) (4222992 1055748 2162171904 540542976 276758003712 69189500928 17297375232 141700097900544 35425024475136 8856256118784 18137612531269632 4534403132817408 1133600783204352 9286457616010051584 2321614404002512896 580403601000628224 3154016 788504 1614856192 403714048 100928512 206701592576 51675398144 12918849536 105831215398912 26457803849728 6614450962432 13546395571060736 3386598892765184 846649723191296 6935754532383096832 1733938633095774208 433484658273943552) (2160099456 540024864 135006216 276492730368 69123182592 17280795648 141564277948416 35391069487104 8847767371776 2211941842944 18120227577397248 4530056894349312 1132514223587328 9277556519627390976 2319389129906847744 579847282476711936 144961820619177984 30736 15736832 3934208 2014314496 503578624 1031329021952 257832255488 64458063872 132010114809856 33002528702464 67589178782646272 16897294695661568 4224323673915392 8651414884178722816 2162853721044680704 1077985344 269496336 67374084 137982124032 34495531008 70646847504384 17661711876096 4415427969024 1103856992256 9042796480561152 2260699120140288 565174780035072 4629911798047309824 1157477949511827456 289369487377956864 72342371844489216 8312 4255744 1063936 544735232 136183808 278904438784 69726109696 17431527424 35699768164352 8924942041088 18278281300148224 4569570325037056 1142392581259264 2339620006418972672 584905001604743168) (538976352 134744088 275955892224 68988973056 17247243264 35322354204672 8830588551168 2207647137792 18085045352792064 4521261338198016 1130315334549504 282578833637376 2314885805157384192 578721451289346048 144680362822336512 33008 8252 4225024 2163212288 540803072 135200768 276891172864 69222793216 141768280506368 35442070126592 8860517531648 18146339904815104 4536584976203776 9290926031265333248 2322731507816333312 580682876954083328 1614823488 403705872 100926468 826789625856 206697406464 51674351616 105829072109568 26457268027392 6614317006848 54184484920098816 13546121230024704 3386530307506176 846632576876544 6935614069772648448 1733903517443162112 433475879360790528 61456 15364 7866368 4027580416 1006895104 251723776 515530293248 128882573312 263951510142976 65987877535744 16496969383936 33785793298300928 8446448324575232 17298326168730075136 4324581542182518784 1081145385545629696) (57392 14348 7346176 3761242112 940310528 235077632 481438990336 120359747584 246496763052032 61624190763008 15406047690752 31551585670660096 7887896417665024 16154411863377969152 4038602965844492288 1009650741461123072 538992704 134748176 275964264448 68991066112 17247766528 35323425849344 8830856462336 2207714115584 18085594034864128 4521398508716032 1130349627179008 282587406794752 2314956036462608384 578739009115652096 144684752278913024 49264 12316 6305792 3228565504 807141376 201785344 413256384512 103314096128 211587268870144 52896817217536 13224204304384 27083170415378432 6770792603844608 13866583252673757184 3466645813168439296 866661453292109824 543178816 135794704 33948676 278107553792 69526888448 17381722112 35597766885376 8899441721344 2224860430336 18226056645312512 4556514161328128 1139128540332032 284782135083008 2332935250600001536 583233812650000384 145808453162500096) (1077952608 269488152 551911735296 137977933824 34494483456 70644702117888 17661175529472 4415293882368 36170087484358656 9042521871089664 2260630467772416 565157616943104 4629771197997907968 1157442799499476992 289360699874869248 61568 15392 7880704 1970176 4034920448 1008730112 252182528 516469817344 129117454336 264432546480128 66108136620032 16527034155008 33847365949456384 8461841487364096 17329851366121668608 4332462841530417152 1083115710382604288 1612718112 403179528 825711673344 206427918336 51606979584 12901744896 105691094188032 26422773547008 6605693386752 54113840224272384 13528460056068096 3382115014017024 845528753504256 6926571548706865152 1731642887176716288 432910721794179072 4336 1084 555008 284164096 71041024 17760256 36373004288 9093251072 18622978195456 4655744548864 1163936137216 2383741209018368 595935302254592 1220475499017404416 305118874754351104 76279718688587776) (1086341184 271585296 67896324 139051671552 34762917888 71194455834624 17798613958656 4449653489664 1112413372416 9112890346831872 2278222586707968 569555646676992 4665799857577918464 1166449964394479616 291612491098619904 72903122774654976 4216 2158592 539648 276299776 69074944 141465485312 35366371328 8841592832 18107582119936 4526895529984 9271082045407232 2317770511351808 579442627837952 1186698501812125696 296674625453031424 2155921536 538980384 134745096 275957956608 68989489152 17247372288 141290473783296 35322618445824 8830654611456 2207663652864 18085180644261888 4521295161065472 1130323790266368 9259612489862086656 2314903122465521664 578725780616380416 144681445154095104 30752 15745024 3936256 984064 2015363072 503840768 1031865892864 257966473216 64491618304 132078834286592 33019708571648 67624363154735104 16906090788683776 4226522697170944 8655918483806093312 2163979620951523328) (1080041504 270010376 552981250048 138245312512 34561328128 8640332032 70781600006144 17695400001536 4423850000384 36240179203145728 9060044800786432 2265011200196608 566252800049152 4638742938002653184 1159685734500663296 289921433625165824 12512 3128 1601536 400384 819986432 204996608 51249152 104958263296 26239565824 53738630807552 13434657701888 3358664425472 6878544743366656 1719636185841664 3521814908603727872 880453727150931968 220113431787732992 1077960736 269490184 551915896832 137978974208 34494743552 8623685888 70645234794496 17661308698624 4415327174656 36170360214781952 9042590053695488 2260647513423872 565161878355968 4629806107492089856 1157451526873022464 289362881718255616 28864 7216 3694592 923648 1891631104 472907776 118226944 242128781312 60532195328 123969936031744 30992484007936 7748121001984 15868151812063232 3967037953015808 8124493727776374784 2031123431944093696 507780857986023424) (4218928 1054732 2160091136 540022784 276491665408 69122916352 17280729088 141563732688896 35390933172224 8847733293056 18120157784178688 4530039446044672 1132509861511168 9277520785499488256 2319380196374872064 579845049093718016 3170368 792592 1623228416 405807104 101451776 207773237248 51943309312 12985827328 106379897470976 26594974367744 6648743591936 13616626876284928 3404156719071232 851039179767808 6971712960657883136 1742928240164470784 435732060041117696 6303760 1575940 3227525120 806881280 413123215360 103280803840 25820200960 211519086264320 52879771566080 13219942891520 27074443041832960 6768610760458240 1692152690114560 13862114837418475520 3465528709354618880 866382177338654720 1060960 265240 543211520 135802880 33950720 69531074560 17382768640 4345692160 35599910174720 8899977543680 2224994385920 4556788502364160 1139197125591040 284799281397760 2333075713210449920 583268928302612480 145817232075653120) (2105440 526360 1077985280 269496320 67374080 137982115840 34495528960 8623882240 70646843310080 17661710827520 4415427706880 1103856926720 9042795943690240 2260698985922560 565174746480640 4629911523169402880 1157477880792350720 289369470198087680 72342367549521920 32992 8248 4222976 1055744 2162163712 540540928 135135232 276756955136 69189238784 17297309696 141699561029632 35424890257408 8856222564352 18137543811792896 4534385952948224 1133596488237056 9286422431637962752 2321605607909490688 580401401977372672 12615808 3153952 788488 1614823424 403705856 100926464 826789593088 206697398272 51674349568 12918587392 105829067915264 26457266978816 6614316744704 54184482772615168 13546120693153792 3386530173288448 846632543322112 6935613794894741504 1733903448723685376 433475862180921344 28688 7172 14688256 3672064 1880096768 470024192 117506048 962609545216 240652386304 60163096576 123214021787648 30803505446912 7700876361728 63085579155275776 15771394788818944 3942848697204736 8074954131875299328 2018738532968824832 504684633242206208) (4210784 1052696 2155921408 538980352 134745088 275957940224 68989485056 17247371264 141290465394688 35322616348672 8830654087168 2207663521792 18085179570520064 4521294892630016 1130323723157504 9259611940106272768 2314902985026568192 578725746256642048 144681436564160512 57472 14368 7356416 1839104 459776 3766484992 941621248 235405312 482110078976 120527519744 30131879936 246840360435712 61710090108928 15427522527232 31595566135771136 7898891533942784 1974722883485696 16176929861514821632 4044232465378705408 1011058116344676352 12599360 3149840 787460 1612718080 403179520 825711656960 206427914240 51606978560 12901744640 105691092090880 26422773022720 6605693255680 54113839150530560 13528459787632640 3382114946908160 845528736727040 6926571411267911680 1731642852816977920 432910713204244480 4208 1052 2154496 538624 275775488 68943872 17235968 141197049856 35299262464 8824815616 18073222381568 4518305595392 1129576398848 9253489859362816 2313372464840704 578343116210176 1184446701998440448 296111675499610112 74027918874902528) (8437824 2109456 527364 1080041472 270010368 552981233664 138245308416 34561327104 8640331776 70781597908992 17695399477248 4423849869312 36240178129403904 9060044532350976 2265011133087744 566252783271936 4638742800563699712 1159685700140924928 289921425035231232 12384 3096 6340608 1585152 396288 811597824 202899456 50724864 415538085888 103884521472 25971130368 53188874993664 13297218748416 3324304687104 27232703996755968 6808175999188992 1702043999797248 3485786111584763904 871446527896190976 217861631974047744 4218912 1054728 2160082944 540020736 135005184 33751296 276490616832 69122654208 17280663552 141563195817984 35390798954496 8847699738624 2211924934656 18120089064701952 4530022266175488 1132505566543872 9277485601127399424 2319371400281849856 579842850070462464 144960712517615616 24768 6192 3170304 792576 1623195648 405798912 101449728 207769042944 51942260736 12985565184 106377749987328 26594437496832 6648609374208 13616351998377984 3404087999594496 851021999898624 6971572223169527808 1742893055792381952 435723263948095488) (2121760 530440 1086341120 271585280 67896320 16974080 139051663360 34762915840 8690728960 71194451640320 17798612910080 4449653227520 1112413306880 9112889809960960 2278222452490240 569555613122560 4665799582700011520 1166449895675002880 291612473918750720 72903118479687680 16608 4152 2125824 531456 1088421888 272105472 68026368 139318001664 34829500416 8707375104 71330816851968 17832704212992 4458176053248 9130344557051904 2282586139262976 570646534815744 4674736413210574848 1168684103302643712 292171025825660928 8437888 2109472 527368 1080049664 270012416 67503104 552985427968 138246356992 34561589248 8640397312 70782134779904 17695533694976 4423883423744 36240453007310848 9060113251827712 2265028312956928 566257078239232 4638777984935788544 1159694496233947136 289923624058486784 28704 7176 14696448 3674112 918528 1881145344 470286336 117571584 963146416128 240786604032 60196651008 123282741264384 30820685316096 7705171329024 63120763527364608 15780190881841152 3945047720460288 8079457731502669824 2019864432875667456 504966108218916864))) #| (defun compute-neighbor-table () (let ((buf (make-array 64))) (dotimes (bit 64 buf) (let ((list nil) (i (logand bit 7)) (j (ash bit -3))) (flet ((check-at (dx dy) (let ((new-x (+ i dx)) (new-y (+ j dy))) (when (and (<= 0 new-x 7) (<= 0 new-y 7)) (push (set-frame-ref 0 new-x new-y) list))))) (check-at 1 0) (check-at -1 0) (check-at 0 1) (check-at 0 -1)) (setf (svref buf bit) list))))) (defparameter *neighbors* (compute-neighbor-table)) |# (defparameter *neighbors* #((256 2) (512 1 4) (1024 2 8) (2048 4 16) (4096 8 32) (8192 16 64) (16384 32 128) (32768 64) (1 65536 512) (2 131072 256 1024) (4 262144 512 2048) (8 524288 1024 4096) (16 1048576 2048 8192) (32 2097152 4096 16384) (64 4194304 8192 32768) (128 8388608 16384) (256 16777216 131072) (512 33554432 65536 262144) (1024 67108864 131072 524288) (2048 134217728 262144 1048576) (4096 268435456 524288 2097152) (8192 536870912 1048576 4194304) (16384 1073741824 2097152 8388608) (32768 2147483648 4194304) (65536 4294967296 33554432) (131072 8589934592 16777216 67108864) (262144 17179869184 33554432 134217728) (524288 34359738368 67108864 268435456) (1048576 68719476736 134217728 536870912) (2097152 137438953472 268435456 1073741824) (4194304 274877906944 536870912 2147483648) (8388608 549755813888 1073741824) (16777216 1099511627776 8589934592) (33554432 2199023255552 4294967296 17179869184) (67108864 4398046511104 8589934592 34359738368) (134217728 8796093022208 17179869184 68719476736) (268435456 17592186044416 34359738368 137438953472) (536870912 35184372088832 68719476736 274877906944) (1073741824 70368744177664 137438953472 549755813888) (2147483648 140737488355328 274877906944) (4294967296 281474976710656 2199023255552) (8589934592 562949953421312 1099511627776 4398046511104) (17179869184 1125899906842624 2199023255552 8796093022208) (34359738368 2251799813685248 4398046511104 17592186044416) (68719476736 4503599627370496 8796093022208 35184372088832) (137438953472 9007199254740992 17592186044416 70368744177664) (274877906944 18014398509481984 35184372088832 140737488355328) (549755813888 36028797018963968 70368744177664) (1099511627776 72057594037927936 562949953421312) (2199023255552 144115188075855872 281474976710656 1125899906842624) (4398046511104 288230376151711744 562949953421312 2251799813685248) (8796093022208 576460752303423488 1125899906842624 4503599627370496) (17592186044416 1152921504606846976 2251799813685248 9007199254740992) (35184372088832 2305843009213693952 4503599627370496 18014398509481984) (70368744177664 4611686018427387904 9007199254740992 36028797018963968) (140737488355328 9223372036854775808 18014398509481984) (281474976710656 144115188075855872) (562949953421312 72057594037927936 288230376151711744) (1125899906842624 144115188075855872 576460752303423488) (2251799813685248 288230376151711744 1152921504606846976) (4503599627370496 576460752303423488 2305843009213693952) (9007199254740992 1152921504606846976 4611686018427387904) (18014398509481984 2305843009213693952 9223372036854775808) (36028797018963968 4611686018427387904))) (defun compute-neighbors (frame) (let ((ret 0)) (dotimes (i 64 ret) (unless (logbitp i frame) (dolist (neighbor (svref *neighbors* i)) (when (logtest neighbor frame) (setq ret (logior ret (ash 1 i))) (return))))))) (defun check-neighbors (frame neighbors pieces) (dotimes (i 64 t) (when (logbitp i neighbors) (block ok (dolist (piece pieces) (dolist (action piece) (when (and (logbitp i action) (not (logtest frame action))) (return-from ok)))) (return-from check-neighbors))))) ;;; It's a brute force search, but we place pieces so they ;;; touch some that are already there to discover dead ends ;;; early. Remember, also, that the order we try pieces is ;;; not totally arbitrary. Note how Common Lisp's RETURN-FROM ;;; simplifies the code a lot without the overhead of throwing ;;; exceptions. And isn't it funny how we cons so much in loops ;;; and still get fast code? (defun choose-neighbor (neighbors) (dotimes (i 64) (when (logbitp i neighbors) (return i)))) (defun compute-action () (labels ((fill-with (frame pieces action-list) (if (null pieces) (return-from compute-action (nreverse action-list)) (let ((neighbors (compute-neighbors frame))) (unless (check-neighbors frame neighbors pieces) (return-from fill-with)) (let ((bit (choose-neighbor neighbors))) (loop for piece in pieces for rest-pieces = (remove piece pieces :test #'eq) do (loop for action in piece do (when (logbitp bit action) (let ((next (logior frame action))) (block walk (let ((next-pieces (loop for rest-piece in rest-pieces collect (let ((ret (loop for action in rest-piece unless (logtest action next) collect action))) (or ret (return-from walk)))))) (fill-with next next-pieces (cons action action-list))))))))))))) (fill-with +start-frame+ *all-placements* nil))) (defun solve () (let ((action-list (compute-action)) (buf (make-array '(8 8) :initial-element #\.))) (loop for i from 0 for char = (digit-char i 24) for action in action-list do (dotimes (bit 64) (when (logbitp bit action) (let ((i (logand bit 7)) (j (ash bit -3))) (setf (aref buf i j) char))))) (loop for j from 7 downto 0 do (fresh-line) (loop for i from 7 downto 0 do (write-char (aref buf i j)))) (values))) ;; $Id: //info.ravenbrook.com/user/ndl/lisp/contest/entries/nils-goesche.lisp#2 $