/* Numberlink puzzle in Picat Also known as Arukone and Nanbarinku. See - https://en.wikipedia.org/wiki/Numberlink """ Versions of this known as Wire Storm, Flow Free and Alphabet Connection have been released as apps for iOS and Android. """ - Aaron Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando S'nchez Villaamil, and Blair D. Sullivan: "Zig-Zag Numberlink is NP-Complete" http://arxiv.org/pdf/1410.5845 This Picat model was inspired by Neng-Fa Zhou: "The SAT Compiler in B-Prolog": http://www.cs.nmsu.edu/ALP/2013/03/the-sat-compiler-in-b-prolog/ and - perhaps more - the B-Prolog model by Neng-Fa Zhou & Wen Wei Rong, March (2012) http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl Model created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import sat. % much faster % import cp. % slow % import mip. % very slow main => go. % % Just one solution % go ?=> nolog, inputM(INo,NP,InputM), printf("solving %d%n",INo), time2(once(subMat(NP,InputM.length,InputM[1].length,InputM))), fail, nl. go => true. % % Also test for uniqueness, i.e. search for all solutions. % go2 ?=> nolog, inputM(INo,NP,InputM), printf("solving %d%n",INo), time2(subMat(NP,InputM.length,InputM[1].length,InputM)), % prove uniqueness fail, nl. go2 => true. % Skipping #4 go3 ?=> nolog, inputM(INo,NP,InputM), INo != 4, % Skip the hard instance #4 printf("solving %d%n",INo), time2(once(subMat(NP,InputM.length,InputM[1].length,InputM))), fail, nl. go3 => true. % % Test a single instance % test(INo) => inputM(INo,NP,InputM), INo != 4, % Skip the hard instance #4 printf("solving %d%n",INo), time2(once(subMat(NP,InputM.length,InputM[1].length,InputM))), nl. subMat(NP,NR,NC,InputM) => SubM = new_array(NR, NC), Vars = vars(SubM), Vars :: 1..NP, % initialize preoccupied squares foreach(I in 1..NR, J in 1..NC) if InputM[I,J]!==0 then SubM[I,J] #= InputM[I,J] end end, % "each end node has one connected neighbor and each interior node has two connected neighbors" % (original formulation from http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl) foreach(J in 1..NR, K in 1..NC) (InputM[J,K] != 0-> sum([SubM[J1,K1]#=SubM[J,K] : (J1,K1) in [(J-1,K),(J+1,K),(J,K-1),(J,K+1)], (J1>=1, K1>=1, J1==1, K1>=1, J1==1, K1>=1, J1= % TheSum #= 1 % ; % TheSum #= 2 % ) % end, % solve($[split],Vars), % CP: 5.6s on #3 (CP) % solve($[updown],Vars), % CP: 0.38s on #3 (CP solve(Vars), % CP: 0.38s on #3 (CP write_matrix(SubM,NR,NC). write_matrix(M,NR,NC) => foreach(I in 1..NR, J in 1..NC) printf("%2d",M[I,J]), print(' '), (J==NC->nl;true) end, nl,nl. % % Problem 0 % From http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl % inputM(INo,NP,M) ?=> INo = 0, NP = 2, M = {{1,0}, {2,0}, {2,1}}. % # Numberlink Puzzle % # Author: Otto Janko % # Source: http://www.janko.at/Raetsel/ % # URL: http://www.janko.at/Raetsel/Arukone/109.a.htm % size 10 10 % - - - 6 - - - - - - % - - - - - - - - - - % - - 5 - 1 4 - 3 - - % - - - - 3 - - 8 - - % - 2 - 2 - - - - - - % - 4 - 8 - 7 - - - - % - - - - - - - - - - % - - 5 - 6 1 - 7 - - % - - - - - - - - - - % - - - - - - - - - - % From http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl inputM(1,NP,M) ?=> NP=8, M={{0,0,0,6,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,5,0,1,4,0,3,0,0}, {0,0,0,0,3,0,0,8,0,0}, {0,2,0,2,0,0,0,0,0,0}, {0,4,0,8,0,7,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,5,0,6,1,0,7,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}}. % # Numberlink Puzzle % # Author: The Afis Project % # Source: http://www.afis.to/~start/ % # URL: http://www.janko.at/Raetsel/Arukone/001.a.htm % size 5 5 % 3 - - - 2 % 4 1 2 - - % - - - 3 - % - - - - - % 4 - - - 1 % From http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl inputM(INo,NP,M) ?=> INo=2, NP=4, M={{3,0,0,0,2}, {4,1,2,0,0}, {0,0,0,3,0}, {0,0,0,0,0}, {4,0,0,0,1}}. % - - - 10 - - - - - - 11 - - - - % - 3 - 6 - - - - - - - - - - 11 % - - - - - - - - - - - - 6 - - % - - - - - - - - 2 - - - - 12 - % - - - - - - - - - - - 9 - - - % 4 - - - 4 - - - - - - - - - - % - - - - - - - - 9 - - - - - - % - - - - - - - - - - - - - - - % - - - - - - - 1 - - 12 - - - - % - - - - - - - - - - - - - 7 - % - - - - 2 - - - - - 10 8 - - - % - - - - - - - - 5 8 - - - - - % - - - - - - - - - - 1 3 5 - - % - - - - - - - - - - - - 7 - - % - - - - - - - - - - - - - - - % % From http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl % % CP : 8.45s % SAT: 1.33s % inputM(INo,NP,M) ?=> INo = 3, NP=12, M = {% {0,0,0,10,0,0,0,0,0,0,11,0,0,0}, % hakank: only 14 elements {0,0,0,10,0,0,0,0,0,0,11,0,0,0,0}, % hakank: added 0 last {0,3,0,6,0,0,0,0,0,0,0,0,0,0,11}, {0,0,0,0,0,0,0,0,0,0,0,0,6,0,0}, {0,0,0,0,0,0,0,0,2,0,0,0,0,12,0}, {0,0,0,0,0,0,0,0,0,0,0,9,0,0,0}, {4,0,0,0,4,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,9,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,1,0,0,12,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,7,0}, {0,0,0,0,2,0,0,0,0,0,10,8,0,0,0}, {0,0,0,0,0,0,0,0,5,8,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,3,5,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,7,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}. % size 42 25 % - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 % - - - - - - - - - - - - - 12 - - - - - - - - - - - - - - - - - - 25 - - - - - - - - - % - - 5 - - - - - - - - - - 10 - 17 62 - 56 61 60 18 - - - - - - 50 - - - - - - - 49 - 39 - - - % - - - - - - - - - - - - - - - - - - 61 - - - - 34 - - - - - - - 59 - - - - - - - 24 - - % - - - - - - - - - - - - - - - - 62 15 60 - - - - - - 56 - - - 46 - 47 - - - - - - - - 49 - % - - - - - 14 - - - - - - - - 16 19 18 - - - - - - - - 33 - - - - - - 59 - - - - - - - - - % - - - 4 - 13 - - - - - - - - 17 - - - - - 55 53 - 34 - 35 - - - - 48 - - - - - - - - - - - % - - - - - 7 - - - - - - - - - - 13 - - - 54 - - 33 - 57 - - - - - - - - - - - - - - - - % - - - - - 12 - - - - - - - - 3 41 42 - - - 53 - 52 32 - - - - - 57 - - - - - - - 47 - - - - % - - - - - 11 - - - - - - - - - - - - - - - - - - - - 35 - - - - - 45 - - - 58 - - - - - % - - - - - 10 - - - - - - - - - - - - - 55 - - - - 21 - - - 51 - - - - 26 - - 46 - - - - - % - - - - - - 11 5 - - - - - - - - - - - 19 54 - - - - - - - - - - - - - - 58 - - - - - - % - - - - - - - - - - - - - - - - - - - 52 - - - - - - - - - - - - - - - - - - - - - - % - - - - - - - - - - - - - - - - - - - - - 42 - - - - - - - 29 45 - - - - - - - - - - - % - - - - - 9 8 6 - - - 16 - - - - - - - - - - - 32 51 - - - - - - - - - - - 28 - - - - - % - - - - - 8 - - - - - - - - - - - 36 - - 38 - - - 44 50 - 30 - - - - - - - - 27 - - - - - % - - - - - - 7 - - - - - - - - - - - 41 22 - 22 - - - 43 23 31 - - - - - - - - 26 - - - - - % - - - - - 6 - - - - - - - - - - - - 36 - - 21 - - - 27 - - - - - - - - - - 25 - - - - - % - - - - - - - - 9 15 - - 14 - - - - - 37 - 20 44 - - - - - 43 - 31 - - - - - - 24 - - - - - % - - - - - - - - - - - - - - - - - - - - - - - - 38 39 40 28 - 30 - - - - - - 23 - - - - - % - 2 - - - - - - - - - - - - - 4 - - - - 20 - 37 - 48 - - - - 29 - - - - - - - - - - - - % - - 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - % - - - 2 - - - - - - - - - - - - - - - - - - - - - 40 - - - - - - - - - - - - - - - - % - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - % 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - % % CP : > 10min % SAT: 4.94s % % From http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl inputM(INo,NP,M) ?=> % INo=4, NP=63, % original from http://www.picat-lang.org/bprolog/cp_sat_lp/numberlink_nb.pl INo=4, NP=62, M = {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,25,0,0,0,0,0,0,0,0,0}, {0,0,5,0,0,0,0,0,0,0,0,0,0,10,0,17,62,0,56,61,60,18,0,0,0,0,0,0,50,0,0,0,0,0,0,0,49,0,39,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,61,0,0,0,0,34,0,0,0,0,0,0,0,59,0,0,0,0,0,0,0,24,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,62,15,60,0,0,0,0,0,0,56,0,0,0,46,0,47,0,0,0,0,0,0,0,0,49,0}, {0,0,0,0,0,14,0,0,0,0,0,0,0,0,16,19,18,0,0,0,0,0,0,0,0,33,0,0,0,0,0,0,59,0,0,0,0,0,0,0,0,0}, {0,0,0,4,0,13,0,0,0,0,0,0,0,0,17,0,0,0,0,0,55,53,0,34,0,35,0,0,0,0,48,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,0,13,0,0,0,54,0,0,33,0,57,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,12,0,0,0,0,0,0,0,0,3,41,42,0,0,0,53,0,52,32,0,0,0,0,0,57,0,0,0,0,0,0,0,47,0,0,0,0}, {0,0,0,0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,35,0,0,0,0,0,45,0,0,0,58,0,0,0,0,0}, {0,0,0,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,55,0,0,0,0,21,0,0,0,51,0,0,0,0,26,0,0,46,0,0,0,0,0}, {0,0,0,0,0,0,11,5,0,0,0,0,0,0,0,0,0,0,0,19,54,0,0,0,0,0,0,0,0,0,0,0,0,0,0,58,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,52,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,42,0,0,0,0,0,0,0,29,45,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,9,8,6,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,32,51,0,0,0,0,0,0,0,0,0,0,0,28,0,0,0,0,0}, {0,0,0,0,0,8,0,0,0,0,0,0,0,0,0,0,0,36,0,0,38,0,0,0,44,50,0,30,0,0,0,0,0,0,0,0,27,0,0,0,0,0}, {0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,0,0,41,22,0,22,0,0,0,43,23,31,0,0,0,0,0,0,0,0,26,0,0,0,0,0}, {0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,36,0,0,21,0,0,0,27,0,0,0,0,0,0,0,0,0,0,25,0,0,0,0,0}, {0,0,0,0,0,0,0,0,9,15,0,0,14,0,0,0,0,0,37,0,20,44,0,0,0,0,0,43,0,31,0,0,0,0,0,0,24,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,38,39,40,28,0,30,0,0,0,0,0,0,23,0,0,0,0,0}, {0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,20,0,37,0,48,0,0,0,0,29,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}. % % A Flow Free problem % 5x5 % inputM(INo,NP,M) ?=> INo=5, NP=5, M = {{1,0,0,0,2}, {3,0,0,4,0}, {0,1,2,5,0}, {0,0,3,0,0}, {5,0,0,0,4}}. % From % http://www.wired.com/2010/11/dr-sudoku-prescribes-numberlink-puzzles-2/ % 12 x 12 % % CP : 204s % SAT: 0.24s. inputM(INo,NP,M) ?=> INo = 6, NP = 10, M = { {0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,1,2,3,4,0,0,0,5,0,0}, {0,0,0,0,0,0,0,6,0,6,0,0}, {0,0,0,0,0,0,0,0,0,7,0,0}, {0,0,0,0,0,0,2,0,0,8,0,0}, {0,0,4,0,0,9,0,0,0,0,0,0}, {0,0,8,0,0,0,0,0,0,0,0,0}, {0,0,10,0,3,0,0,0,0,0,0,0}, {0,0,1,0,0,0,10,5,9,7,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0} }. % % From https://en.wikipedia.org/wiki/Numberlink % inputM(INo,NP,M) ?=> INo = 7, NP=5, M = { {0,0,0,4,0,0,0}, {0,3,0,0,2,5,0}, {0,0,0,3,1,0,0}, {0,0,0,5,0,0,0}, {0,0,0,0,0,0,0}, {0,0,1,0,0,0,0}, {2,0,0,0,4,0,0} }.