# HG changeset patch # User viric@llimona # Date 1146861645 -7200 # Node ID be33ecaa3619a6e9448dd8819012cffa94d75c6c Initial commit. diff -r 000000000000 -r be33ecaa3619 Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Makefile Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,13 @@ +CC=gcc + +# OPT +CFLAGS=-march=athlon-xp -pipe -O3 -Wall + +# DEBUG +#CFLAGS=-Wall -g -pg +#LDFLAGS=-pg + +all: sokosold2 sokosol5 sokosol-profund +sokosold2: sokosold2.o +sokosol5: sokosol5.o +sokosol-profund: sokosol-profund.o diff -r 000000000000 -r be33ecaa3619 levels/01 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/01 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +## ### +# $# ### +# . @### +# * ## +## #$ ## +##. ### +######## diff -r 000000000000 -r be33ecaa3619 levels/02 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/02 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,9 @@ +####### +### ## +###$ ## +# * @# +# * # +# * ## +###* ## +###.### +####### diff -r 000000000000 -r be33ecaa3619 levels/02.sol --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/02.sol Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,1 @@ +1L,3L,4D,2D,1R,1R,2U,2L,3R,1L,1L,0D,3D,0D,1R,2D,2R, diff -r 000000000000 -r be33ecaa3619 levels/03 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/03 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,7 @@ +###### +# . # +#@# *# +# $ # +# #* # +# # +###### diff -r 000000000000 -r be33ecaa3619 levels/04 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/04 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,7 @@ +####### +# @ # +### # # +# $ # +### # # +#. # +####### diff -r 000000000000 -r be33ecaa3619 levels/2/model --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/2/model Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +## 8 ### +## #* # +# O+ + # +# ** ## +### #+## +### ## +######## diff -r 000000000000 -r be33ecaa3619 levels/2/result diff -r 000000000000 -r be33ecaa3619 levels/3/model --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/3/model Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,7 @@ +###### +###. # +## # +# $ # +# @ # +### # +###### diff -r 000000000000 -r be33ecaa3619 levels/3/result --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/3/result Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,936 @@ +###### +###+-# +##- # +#-* # +#- # +###--# +###### +Man is at (3,4) +Platforms: 1, BoxesInPlatform: 0 +Numero de moviments inicials a provar: LR +LU +LD +RL +RR +RU +RD +UL +UR +UU +UD +DL +DR +DU +DD +Provant 3 moviments... +LLL +LLR +LLU +LLD +InverseMove: LR +LU +LD +InverseMove: RL +RR +RUL +RUR +RUU +RUD +RDL +RDR +RDU +RDD +UL +URL +URR +URU +URD +UUL +UUR +UUU +UUD +InverseMove: UD +DL +DRL +DRR +DRU +DRD +InverseMove: DU +DD +Provant 4 moviments... +LLL +InverseMove: LLR +LLUL +LLUR +LLUU +LLUD +LLD +InverseMove: LR +LU +LD +InverseMove: RL +RR +RULL +RULR +RULU +RULD +RUR +RUUL +RUUR +RUUU +RUUD +InverseMove: RUD +RDLL +RDLR +RDLU +RDLD +RDR +InverseMove: RDU +RDD +UL +InverseMove: URL +URR +URUL +URUR +URUU +URUD +URDL +URDR +URDU +URDD +UULL +UULR +UULU +UULD +UURL +UURR +UURU +UURD +UUUL +UUUR +UUUU +UUUD +InverseMove: UUD +InverseMove: UD +DL +InverseMove: DRL +DRR +DRUL +DRUR +DRUU +DRUD +DRD +InverseMove: DU +DD +Provant 5 moviments... +LLL +InverseMove: LLR +LLUL +LLURL +LLURR +LLURU +LLURD +LLUU +InverseMove: LLUD +LLD +InverseMove: LR +LU +LD +InverseMove: RL +RR +RULL +InverseMove: RULR +RULUL +RULUR +RULUU +RULUD +RULDL +RULDR +RULDU +RULDD +RUR +RUULL +RUULR +RUULU +RUULD +RUUR +RUUUL +RUUUR +RUUUU +RUUUD +InverseMove: RUUD +InverseMove: RUD +RDLL +InverseMove: RDLR +RDLUL +RDLUR +RDLUU +RDLUD +RDLD +RDR +InverseMove: RDU +RDD +UL +InverseMove: URL +URR +URULL +URULR +URULU +URULD +URUR +URUUL +URUUR +URUUU +URUUD +InverseMove: URUD +URDLL +URDLR +URDLU +URDLD +URDR +InverseMove: URDU +URDDL +URDDR +URDDU +URDDD +UULL +InverseMove: UULR +UULU +UULDL +UULDR +UULDU +UULDD +InverseMove: UURL +UURR +UURUL +UURUR +UURUU +UURUD +UURDL +UURDR +UURDU +UURDD +UUUL +UUURL +UUURR +UUURU +UUURD +UUUU +InverseMove: UUUD +InverseMove: UUD +InverseMove: UD +DL +InverseMove: DRL +DRR +DRULL +DRULR +DRULU +DRULD +DRUR +DRUUL +DRUUR +DRUUU +DRUUD +InverseMove: DRUD +DRD +InverseMove: DU +DD +Provant 6 moviments... +LLL +InverseMove: LLR +LLUL +LLURLL +LLURLR +LLURLU +LLURLD +LLURRL +LLURRR +LLURRU +LLURRD +LLURUL +LLURUR +LLURUU +LLURUD +LLURDL +LLURDR +LLURDU +LLURDD +LLUU +InverseMove: LLUD +LLD +InverseMove: LR +LU +LD +InverseMove: RL +RR +RULL +InverseMove: RULR +RULULL +RULULR +RULULU +RULULD +RULURL +RULURR +RULURU +RULURD +RULUUL +RULUUR +RULUUU +RULUUD +InverseMove: RULUD +RULDLL +RULDLR +RULDLU +RULDLD +RULDRL +RULDRR +RULDRU +RULDRD +InverseMove: RULDU +RULDDL +RULDDR +RULDDU +RULDDD +RUR +RUULLL +RUULLR +RUULLU +RUULLD +InverseMove: RUULR +RUULUL +RUULUR +RUULUU +RUULUD +RUULDL +RUULDR +RUULDU +RUULDD +RUUR +RUUULL +RUUULR +RUUULU +RUUULD +RUUUR +RUUUU +InverseMove: RUUUD +InverseMove: RUUD +InverseMove: RUD +RDLL +InverseMove: RDLR +RDLULL +RDLULR +RDLULU +RDLULD +RDLURL +RDLURR +RDLURU +RDLURD +RDLUUL +RDLUUR +RDLUUU +RDLUUD +InverseMove: RDLUD +RDLD +RDR +InverseMove: RDU +RDD +UL +InverseMove: URL +URR +URULLL +URULLR +URULLU +URULLD +InverseMove: URULR +URULUL +URULUR +URULUU +URULUD +URULDL +URULDR +URULDU +URULDD +URUR +URUULL +URUULR +URUULU +URUULD +URUUR +URUUU +InverseMove: URUUD +InverseMove: URUD +URDLLL +URDLLR +URDLLU +URDLLD +InverseMove: URDLR +URDLUL +URDLUR +URDLUU +URDLUD +URDLDL +URDLDR +URDLDU +URDLDD +URDR +InverseMove: URDU +URDDLL +URDDLR +URDDLU +URDDLD +URDDR +InverseMove: URDDU +URDDD +UULL +InverseMove: UULR +UULU +UULDLL +UULDLR +UULDLU +UULDLD +UULDRL +UULDRR +UULDRU +UULDRD +UULDUL +UULDUR +UULDUU +UULDUD +UULDD +InverseMove: UURL +UURR +UURULL +UURULR +UURULU +UURULD +UURUR +UURUU +InverseMove: UURUD +UURDLL +UURDLR +UURDLU +UURDLD +UURDR +InverseMove: UURDU +UURDDL +UURDDR +UURDDU +UURDDD +UUUL +InverseMove: UUURL +UUURR +UUURU +UUURDL +UUURDR +UUURDU +UUURDD +UUUU +InverseMove: UUUD +InverseMove: UUD +InverseMove: UD +DL +InverseMove: DRL +DRR +DRULLL +DRULLR +DRULLU +DRULLD +InverseMove: DRULR +DRULUL +DRULUR +DRULUU +DRULUD +DRULDL +DRULDR +DRULDU +DRULDD +DRUR +DRUULL +DRUULR +DRUULU +DRUULD +DRUUR +DRUUUL +DRUUUR +DRUUUU +DRUUUD +InverseMove: DRUUD +InverseMove: DRUD +DRD +InverseMove: DU +DD +Provant 7 moviments... +LLL +InverseMove: LLR +LLUL +LLURLL +InverseMove: LLURLR +LLURLU +LLURLDL +LLURLDR +LLURLDU +LLURLDD +LLURRLL +LLURRLR +LLURRLU +LLURRLD +LLURRR +LLURRUL +LLURRUR +LLURRUU +LLURRUD +LLURRDL +LLURRDR +LLURRDU +LLURRDD +LLURUL +LLURURL +LLURURR +LLURURU +LLURURD +LLURUU +InverseMove: LLURUD +LLURDLL +LLURDLR +LLURDLU +LLURDLD +LLURDRL +LLURDRR +LLURDRU +LLURDRD +InverseMove: LLURDU +LLURDD +LLUU +InverseMove: LLUD +LLD +InverseMove: LR +LU +LD +InverseMove: RL +RR +RULL +InverseMove: RULR +RULULL +InverseMove: RULULR +RULULU +RULULDL +RULULDR +RULULDU +RULULDD +InverseMove: RULURL +RULURR +RULURUL +RULURUR +RULURUU +RULURUD +RULURDL +RULURDR +RULURDU +RULURDD +RULUUL +RULUURL +RULUURR +RULUURU +RULUURD +RULUUU +InverseMove: RULUUD +InverseMove: RULUD +RULDLLL +RULDLLR +RULDLLU +RULDLLD +InverseMove: RULDLR +RULDLU +RULDLD +InverseMove: RULDRL +RULDRR +RULDRUL +RULDRUR +RULDRUU +RULDRUD +RULDRDL +RULDRDR +RULDRDU +RULDRDD +InverseMove: RULDU +RULDDL +RULDDRL +RULDDRR +RULDDRU +RULDDRD +InverseMove: RULDDU +RULDDD +RUR +RUULLL +InverseMove: RUULLR +RUULLU +RUULLDL +RUULLDR +RUULLDU +RUULLDD +InverseMove: RUULR +RUULUL +RUULURL +RUULURR +RUULURU +RUULURD +RUULUU +InverseMove: RUULUD +RUULDL +RUULDRL +RUULDRR +RUULDRU +RUULDRD +InverseMove: RUULDU +RUULDDL +RUULDDR +RUULDDU +RUULDDD +RUUR +RUUULL +InverseMove: RUUULR +RUUULU +RUUULDL +RUUULDR +RUUULDU +RUUULDD +RUUUR +RUUUU +InverseMove: RUUUD +InverseMove: RUUD +InverseMove: RUD +RDLL +InverseMove: RDLR +RDLULLL +RDLULLR +RDLULLU +RDLULLD +InverseMove: RDLULR +RDLULU +RDLULD +InverseMove: RDLURL +RDLURR +RDLURUL +RDLURUR +RDLURUU +RDLURUD +RDLURDL +RDLURDR +RDLURDU +RDLURDD +RDLUUL +RDLUURL +RDLUURR +RDLUURU +RDLUURD +RDLUUUL +RDLUUUR +RDLUUUU +RDLUUUD +InverseMove: RDLUUD +InverseMove: RDLUD +RDLD +RDR +InverseMove: RDU +RDD +UL +InverseMove: URL +URR +URULLL +InverseMove: URULLR +URULLU +URULLDL +URULLDR +URULLDU +URULLDD +InverseMove: URULR +URULUL +URULURL +URULURR +URULURU +URULURD +URULUU +InverseMove: URULUD +URULDL +URULDRL +URULDRR +URULDRU +URULDRD +InverseMove: URULDU +URULDDL +URULDDR +URULDDU +URULDDD +URUR +URUULL +InverseMove: URUULR +URUULU +URUULDL +URUULDR +URUULDU +URUULDD +URUUR +URUUU +InverseMove: URUUD +InverseMove: URUD +URDLLLL +URDLLLR +URDLLLU +URDLLLD +InverseMove: URDLLR +URDLLU +URDLLD +InverseMove: URDLR +URDLUL +URDLURL +URDLURR +URDLURU +URDLURD +URDLUUL +URDLUUR +URDLUUU +URDLUUD +InverseMove: URDLUD +URDLDL +URDLDRL +URDLDRR +URDLDRU +URDLDRD +InverseMove: URDLDU +URDLDD +URDR +InverseMove: URDU +URDDLL +InverseMove: URDDLR +URDDLUL +URDDLUR +URDDLUU +URDDLUD +URDDLD +URDDR +InverseMove: URDDU +URDDD +UULL +InverseMove: UULR +UULU +UULDLL +InverseMove: UULDLR +UULDLU +UULDLDL +UULDLDR +UULDLDU +UULDLDD +InverseMove: UULDRL +UULDRRL +UULDRRR +UULDRRU +UULDRRD +UULDRUL +UULDRUR +UULDRUU +UULDRUD +UULDRDL +UULDRDR +UULDRDU +UULDRDD +UULDUL +UULDURL +UULDURR +UULDURU +UULDURD +UULDUU +InverseMove: UULDUD +UULDD +InverseMove: UURL +UURR +UURULL +InverseMove: UURULR +UURULU +UURULDL +UURULDR +UURULDU +UURULDD +UURUR +UURUU +InverseMove: UURUD +UURDLL +InverseMove: UURDLR +UURDLUL +UURDLUR +UURDLUU +UURDLUD +UURDLDL +UURDLDR +UURDLDU +UURDLDD +UURDR +InverseMove: UURDU +UURDDLL +UURDDLR +UURDDLU +UURDDLD +UURDDR +InverseMove: UURDDU +UURDDDL +UURDDDR +UURDDDU +UURDDDD +UUUL +InverseMove: UUURL +UUURR +UUURU +UUURDLL +UUURDLR +UUURDLU +UUURDLD +UUURDR +InverseMove: UUURDU +UUURDDL +UUURDDR +UUURDDU +UUURDDD +UUUU +InverseMove: UUUD +InverseMove: UUD +InverseMove: UD +DL +InverseMove: DRL +DRR +DRULLLL +DRULLLR +DRULLLU +DRULLLD +InverseMove: DRULLR +DRULLU +DRULLD +InverseMove: DRULR +DRULUL +DRULURL +DRULURR +DRULURU +DRULURD +DRULUUL +DRULUUR +DRULUUU +DRULUUD +InverseMove: DRULUD +DRULDL +DRULDRL +DRULDRR +DRULDRU +DRULDRD +InverseMove: DRULDU +DRULDD +DRUR +DRUULL +InverseMove: DRUULR +DRUULUL +DRUULUR +DRUULUU +DRUULUD +DRUULDL +DRUULDR +DRUULDU +DRUULDD +DRUUR +DRUUULL +DRUUULR +DRUUULU +DRUUULD +DRUUUR +DRUUUUL +DRUUUUR +DRUUUUU +DRUUUUD +InverseMove: DRUUUD +InverseMove: DRUUD +InverseMove: DRUD +DRD +InverseMove: DU +DD +Provant 8 moviments... +LLL +InverseMove: LLR +LLUL +LLURLL +InverseMove: LLURLR +LLURLU +LLURLDL +LLURLDRL +LLURLDRR +LLURLDRU +LLURLDRD +InverseMove: LLURLDU +LLURLDD +LLURRLLL +LLURRLLR +LLURRLLU +LLURRLLD +InverseMove: LLURRLR +LLURRLUL +LLURRLUR +LLURRLUU +LLURRLUD +LLURRLDL +LLURRLDR +LLURRLDU +LLURRLDD +LLURRR +LLURRULL +LLURRULR +LLURRULU +LLURRULD +LLURRURL +LLURRURR +LLURRURU +LLURRURD +LLURRUUL +LLURRUUR +LLURRUUU +LLURRUUD +InverseMove: LLURRUD +LLURRDLL +LLURRDLR +LLURRDLU +LLURRDLD +LLURRDRL +LLURRDRR +LLURRDRU +LLURRDRD +InverseMove: LLURRDU +LLURRDDL +LLURRDDR +LLURRDDU +LLURRDDD +LLURUL +InverseMove: LLURURL +LLURURRL +LLURURRR +LLURURRU +LLURURRD +LLURURUL +LLURURUR +LLURURUU +LLURURUD +LLURURDL +LLURURDR +LLURURDU +LLURURDD +LLURUU +InverseMove: LLURUD +LLURDLL +InverseMove: LLURDLR +LLURDLUL +LLURDLUR +LLURDLUU +LLURDLUD +LLURDLD +InverseMove: LLURDRL +LLURDRRL +LLURDRRR +LLURDRRU +LLURDRRD +LLURDRUL +LLURDRUR +LLURDRUU +LLURDRUU diff -r 000000000000 -r be33ecaa3619 levels/borja --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/borja Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,10 @@ + ######## +####--# +#- #### +#-$ # . ## +#- # . # +## #$$#. # +## @##### +#- ### +#---# +##### diff -r 000000000000 -r be33ecaa3619 levels/kde --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/kde Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,9 @@ + ##### + ## . # + ## $. # + ## $ # + ## $@ ### +## $ ## +##.. ## +## # +###### diff -r 000000000000 -r be33ecaa3619 levels/level2hp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/level2hp Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,10 @@ +############### +#.. # ### +#.. # $ $ # +#.. #$#### # +#.. @ ## # +#.. # # $ ## +####### ##$ $ # +### $ $ $ $ # +### # # +############### diff -r 000000000000 -r be33ecaa3619 levels/level6hp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/level6hp Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,11 @@ +###### #### +#.. # ## ## +#.. ###@ # +#.. $$ # +#.. # # $ # +#..### # $ # +#### $ #$ # + # $# $ # + # $ $ # + # ## # + ######### diff -r 000000000000 -r be33ecaa3619 levels/mobil-fort --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/mobil-fort Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,9 @@ + #### + #####--# + #-$ $ -# + #.# #.-# + # $@$ ## +##.# #.## +#- * * -# +#---#---# +######### diff -r 000000000000 -r be33ecaa3619 levels/mobil1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/mobil1 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,7 @@ + ###### +## ### +# # +#.**$@# +# ### +## # + #### diff -r 000000000000 -r be33ecaa3619 levels/mobil2 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/mobil2 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,7 @@ +#### #### +# ### # +# $ * $ # +# @ # +### .$### + # . # + ##### diff -r 000000000000 -r be33ecaa3619 levels/mobil3 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/mobil3 Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,6 @@ +########## +####### .# +# $ $ $$ # +# @ ...# +### - #### + ##### diff -r 000000000000 -r be33ecaa3619 levels/model --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/model Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,10 @@ +############### +#.. # ### +#.. # $ $ # +#.. #$#### # +#.. @ ## # +#.. # # $ ## +####### ##$ $ # +### $ $ $ $ # +### # # +############### diff -r 000000000000 -r be33ecaa3619 levels/model.sol --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/model.sol Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,1 @@ +2D,5D,3U,6R,7U,0D,1D,1D,1D,4L, diff -r 000000000000 -r be33ecaa3619 levels/prova --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/prova Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,9 @@ + ##### + ## . # + ## $.-# + ## $ # + ## $@ ### +## $ ## +##.. ## +## - # +###### diff -r 000000000000 -r be33ecaa3619 levels/room0111.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0111.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +### * # +## * # # +## + $ # +## # ## +### ## +######## +######## diff -r 000000000000 -r be33ecaa3619 levels/room0124.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0124.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +## ### +# $# ### +# . @### +# * ## +## #$ ## +##. ### +######## diff -r 000000000000 -r be33ecaa3619 levels/room0124.xsb.sol --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0124.xsb.sol Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,31 @@ +######## +##- -### +#-$# ### +# . @### +#-* -## +## #$-## +##. -### +######## +######## +##+++### +#+##+### +#++++### +#+#+++## +## ##+## +## ### +######## +Man is at (4,3) +Platforms: 3, BoxesInPlatform: 1 +Provant 3 moviments... +Provant 4 moviments... +Provant 5 moviments... +Provant 6 moviments... +Provant 7 moviments... +Provant 8 moviments... +Provant 9 moviments... +Provant 10 moviments... +Provant 11 moviments... +Provant 12 moviments... +Provant 13 moviments... +Provant 14 moviments... +0D,0R,1R,2U,2U,1L,1U,2D,2L,1D,1D,0L,1D,2L, diff -r 000000000000 -r be33ecaa3619 levels/room0125.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0125.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +######## +## #### +#..$ .# +# #$ $ # +#@ # # +##### # +######## diff -r 000000000000 -r be33ecaa3619 levels/room0125.xsb.sol --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0125.xsb.sol Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,31 @@ +######## +######## +##--#### +#..$ .# +# #$ $ # +#@ -# # +#####--# +######## +######## +######## +##++#### +#++# # +#+## # # +#+++# # +##### # +######## +Man is at (1,5) +Platforms: 3, BoxesInPlatform: 0 +Provant 3 moviments... +Provant 4 moviments... +Provant 5 moviments... +Provant 6 moviments... +Provant 7 moviments... +Provant 8 moviments... +Provant 9 moviments... +Provant 10 moviments... +Provant 11 moviments... +Provant 12 moviments... +Provant 13 moviments... +Provant 14 moviments... +0R,1U,2R,2D,1D,0R,1U,1L,0L,1L,0L,0L,2U,2U, diff -r 000000000000 -r be33ecaa3619 levels/room0126.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0126.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +## .@## +## $.# +####*# # +## # +# $ ## +# #### +######## diff -r 000000000000 -r be33ecaa3619 levels/room0126.xsb.sol --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0126.xsb.sol Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,19 @@ +######## +##- .@## +##- $.# +####*# # +##- -# +#- $ -## +#- -#### +######## +######## +##++++## +##+++# # +###### # +## # +# # ## +# #### +######## +Man is at (5,1) +Platforms: 3, BoxesInPlatform: 1 +Provant 24 moviments... diff -r 000000000000 -r be33ecaa3619 levels/room0127.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0127.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +##@ #### +## #### +##. #### +# $$. .# +# $ ### +### ### +######## diff -r 000000000000 -r be33ecaa3619 levels/room0127a.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0127a.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +##@ #### +## #### +##.$#### +# $ . ## +# ### +### ### +######## diff -r 000000000000 -r be33ecaa3619 levels/room0128.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0128.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +######## +##. ### +## # ### +## *$ # +## $. # +## @### +######## diff -r 000000000000 -r be33ecaa3619 levels/room0129.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0129.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +######## +### ## +### #.## +### .## +#@ $$ ## +# .$ ## +######## diff -r 000000000000 -r be33ecaa3619 levels/room0130.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0130.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +# @### +# $# ### +# * $ # +# ## # +##. . # +### ## +######## diff -r 000000000000 -r be33ecaa3619 levels/room0131.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0131.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +## @## +## # # +##. $ # +## $$#.# +#### .# +######## +######## diff -r 000000000000 -r be33ecaa3619 levels/room0132.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0132.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +######## +###. ### +# . ### +# $$ # +## . $@# +######## +######## diff -r 000000000000 -r be33ecaa3619 levels/room0134.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0134.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +##### # +#####$.# +### . # +### #.# +# $ $ # +# #@ # +######## diff -r 000000000000 -r be33ecaa3619 levels/room0136.xsb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/room0136.xsb Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,8 @@ +######## +### ### +### ### +### .. # +# $# -# +# .$$-# +####@- # +######## diff -r 000000000000 -r be33ecaa3619 levels/roomsok.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/roomsok.txt Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,110 @@ +#! Rooms 91-92 (c) Howard Abed ! eabed@compuserve.com +#! Rooms 95-100 (c) Takaken ! takaken@ic-net.or.jp +#! Rooms 101-104,111-162,364-380 & 382-399 (c) Yoshio Murase ! http://www.ne.jp/asahi/ai/yoshio/ +#! Rooms 381 (c) Yoshio Murase & Hiramatsu ! http://www.ne.jp/asahi/ai/yoshio/ +#! Rooms 105-109 (c) Kanou Hiroki ! g92k0323@mse.waseda.ac.jp +Room_91="02060022222222f2220000002f2000303002f2003030302f22222322222f00022010112f00020012002f00020100012f00022220022f0000002222" +Room_92="02042222222f20000022f20303002f20030302f22232222f2010112f2000002f2002012f2001002f2222222" +Room_95="0204022222f02000222f22023002f20410102f20033022f2220212f0020002f0022222" +Room_96="0305222222f200002f203002f224002f204022f20402f20402f20102f22222" +Room_97="0406002222f002002f2223022f2004002f2004002f2004022f222402f002122f00222" +Room_98="060322222f200022222f202020002f203000302f211232322f21030002f21100222f222222" +Room_99="090922222222f2000310202222222f2130000202000012f2222012202100302f0222002002220022f002200200022032f000200200002102f2222322222223222f2000000000000002f2222222222222222" +Room_100="0607000002222f000222002222f222203002002f203003030002f202023232002f201111011022f22222222222" +Room_101="070422222222f22222222f22000022f22122302f20113002f20023002f20000222f22222222" +Room_102="040322222222f22222222f22001022f22020422f22003022f22024022f22000022f22222222" +Room_103="050522222222f22200222f22000022f20101322f20030002f22224202f22220002f22222222" +Room_104="050322222222f22222222f22010402f22002002f22034002f22200022f22200022f22222222" +Room_105="030322222222f20002002f20000302f22322112f02012002f02300002f02002222f02222" +Room_106="03050022222f2220002f2000002f20002022f223201022f020014102f020302302f022200022f00022222" +Room_107="020222222f200022222f202301002f200001202f220321302f022000222f0022222" +Room_108="02050222222f220000222f200313002f203131302f221313122f02013102f02200022f0022222" +Room_109="060622222222f200010022f202212002f200300002f220314222f020210002f020302202f020320002f022000222f0022222" +Room_111="060522222222f22200102f22040202f22013002f22002322f22200022f22222222f22222222" +Room_112="020622222222f22001002f22021202f22000302f22133022f22002222f22222222f22222222" +Room_113="020622222222f22220022f20043022f20000022f22012222f22302222f22012222f22222222" +Room_114="040722222222f22122212f22020012f22033002f22003002f22002002f22002222f22222222" +Room_115="020622222222f22220022f22220002f21023302f20000022f21003222f22100222f22222222" +Room_116="050322222222f20112222f20300002f20023202f20001302f22222222f22222222f22222222" +Room_117="050522222222f22200122f20302022f20430022f20120022f20000222f20002222f22222222" +Room_118="030522222222f22222222f21000122f20032022f20203102f20003202f22220002f22222222" +Room_119="040522222222f21012222f21233022f20000022f20320022f22000222f22222222f22222222" +Room_120="060322222222f21002222f20200022f20102022f20343022f22002222f22002222f22222222" +Room_121="050222222222f22222222f21000102f20202002f20300312f22222032f22222002f22222222" +Room_122="070522222222f20022222f20022222f20140002f22300002f22023222f22100222f22222222" +Room_123="020422222222f22000222f22010002f21031302f22320222f22000222f22222222f22222222" +Room_124="040522222222f22000222f20320222f20100222f20400022f22023022f22100222f22222222" +Room_125="060222222222f22222222f22002222f21130012f20230302f20002002f22222002f22222222" +Room_126="020622222222f22001022f22000312f22224202f22000002f20030022f20002222f22222222" +Room_127="020322222222f22002222f22002222f22102222f20331012f20030222f22200222f22222222" +Room_128="070522222222f22222222f22100222f22020222f22043002f22003102f22000222f22222222" +Room_129="060222222222f22222222f22200022f22202122f22200122f20033022f20013022f22222222" +Room_130="020522222222f20000222f20320222f20403002f20002202f22100102f22200022f22222222" +Room_131="020622222222f22000022f22002002f22100302f22033212f22220012f22222222f22222222" +Room_132="060722222222f22222222f22210222f20100222f20003302f22010302f22222222f22222222" +Room_133="020322222222f22010022f20334022f20020022f20020012f22220202f22220002f22222222" +Room_134="070622222222f22222002f22222312f22200102f22200212f20300302f20002002f22222222" +Room_135="060722222222f20012222f20311022f20022322f22002002f22300002f22002222f22222222" +Room_136="070622222222f22200222f22200222f22201102f20032002f20013302f22220002f22222222" +Room_137="030622222222f20002222f20204022f20040002f22230002f22200012f22222222f22222222" +Room_138="030422222222f22201002f20302102f20032022f20040022f22002022f22200022f22222222" +Room_139="060722222222f22222222f22222222f22002222f20000022f20023302f20010412f22222222" +Room_140="020322222222f22000002f21020002f20333122f20120022f20022222f22222222f22222222" +Room_141="040422222222f20000002f20202242f20200302f21301002f22222002f22222002f22222222" +Room_142="020322222222f22000022f22230002f22201002f20302322f20100122f22220022f22222222" +Room_143="050322222222f20002222f20030022f22330122f22001022f22202022f22200122f22222222" +Room_144="070322222222f20002222f20330002f20121002f20022022f20022322f20000122f22222222" +Room_145="060322222222f22222222f22222222f20100222f20120222f20033002f20310002f22222222" +Room_146="020322222222f20012002f20130102f20023002f20030022f22200222f22200222f22222222" +Room_147="030722222222f22000102f20300302f21312222f20022222f20022222f20022222f22222222" +Room_148="030522222222f20100222f20020222f20030222f22320022f20002022f21040022f22222222" +Room_149="040422222222f22222222f22220102f20400102f20302002f20200302f20002222f22222222" +Room_150="060722222222f22222222f22222222f22200222f20110312f20033002f22220002f22222222" +Room_151="030622222222f22222222f22222002f22222012f20303032f20001002f22201002f22222222" +Room_152="060722222222f20002002f20213032f20003002f22222102f22200002f22200012f22222222" +Room_153="020522222222f22220022f22200112f22032322f20003102f20020002f20000222f22222222" +Room_154="020522222222f20000222f20332222f20301002f22021202f21000202f20000002f22222222" +Room_155="040322222222f22220022f22220322f20031002f20220002f20002202f20004012f22222222" +Room_156="020622222222f22220002f22220002f22030322f22030022f21002022f21100022f22222222" +Room_157="030722222222f22222222f22221002f20013002f20200222f20303012f22220002f22222222" +Room_158="030722222222f22222222f20012002f20203002f20312302f22010002f22002222f22222222" +Room_159="050722222222f22222222f22000002f22122012f22400302f22002302f22002002f22222222" +Room_160="050622222222f21022222f20322222f20022222f20130002f20130202f22200002f22222222" +Room_161="040522222222f20000002f20230002f20300212f22321002f22000012f22222222f22222222" +Room_162="060222222222f20010222f20000222f20233102f21002202f20302202f22200002f22222222" +Room_364="020a2222222222222222222f2000111000001110002f2033300222220033302f2200022200022200022f022002000000022002f002222000000002222" +Room_365="0406002222f2220022f2000302f2021202f2023012f2001302f2200022f022222" +Room_366="06040022222f2220002f20302022f20313102f20221002f20000222f222222" +Room_367="06050022222f222000222f201030102f202131202f203020302f222000222f0022222" +Room_368="06020022222f002000222f222120002f203130202f202403002f200102222f222222" +Room_369="08050022222f00200022f222300022f200131302f202121202f200434002f222000222f0020002f0022222" +Room_370="05050022222f0020002f2220232f200131222f202313002f200130202f222021002f002000222f0022222" +Room_371="020222222222222f203000111122f203333211112f2030031144422f2200020221102f2033320022002f2000022020022f200330200002f200000222002f222222202222" +Room_372="07080222222f22000022f20022002f20200202f210012322f202040302f202040302f200110302f222222222" +Room_373="06062222f2002222f200000222f200230102f220212302f200200402f200040022f22220022f0002222" +Room_374="04070022222f22200022f20010402f20131202f22020302f02030202f02220002f00022222" +Room_375="070600022222f00020002f00021032f00020302f222211022f203044002f201000302f222222222" +Room_376="080c00000222222222f00000211100102f00222202121002f22200001111112f20003030321122f2032222112222f20030002220022f20333030303002f20030303030302f22000000000022f0222222222222" +Room_377="07040000222222f222220000222f2000012210022f2013220002002f2233020030002f2010022323022f200001001022f22222222222" +Room_378="0704022222f020002f021032f020302f2211022f2044302f2000002f2222222" +Room_379="0507222222f200002f20140222f20131302f22030002f02222002f00002222" +Room_380="0707000022222f022220002f021221032f223200302f2040011022f2000244302f2222200002f0000222222" +Room_381="030802222f0200222222f020322000222f221022001002f201000031302f204302321222f2220020002f0022222222" +Room_382="020302222f22002222f20340402f20040202f20040002f20241002f20002002f22222222" +Room_383="08030022222f02200022f020031122f223021312f200021112f203222302f200303022f22000002f02222222" +Room_384="060500002222f22222002f20301002f20004302f22211302f02220222f020310222f020341002f020010302f020022222f02222" +Room_385="07030022222f0020002222f2223000302f2003020002f2020122022f214412232f200010002f222222222" +Room_386="0204222222222f200001002f200124302f203101302f223122302f020022002f022222222" +Room_387="02050022222f0020002f222020222f203323302f201101002f220021322f02000102f02222222" +Room_388="040222222f200022f2043022f20040022f20123002f220111322f022203402f000200002f000222222" +Room_389="0502002222f2220022f201100222f204140002f203313302f200220002f222222222" +Room_390="0a0422222222f20000002f20332302f20314002f22011122f0221322f22111022f20041302f20323302f20000002f22222222" +Room_391="07040022222f2220002f2033132f2010102f2020202f20114022f22203302f00200002f00222222" +Room_392="060500222222f00200002f22233002f20302302f20302002f203002022f203214102f200340212f220010212f022211102f000200002f000222222" +Room_393="02050022222f02200022f02013102f02040402f02302142f220020022f203131302f200020002f222222222" +Room_394="0908002222f002002f002102f002032f002102f22203222f200130022f202033002f201221002f220400322f02001002f02222222" +Room_395="05070022222f222000222f200311302f202022002f202022022f20031132f22202302f00201012f00232012f00200302f00222002f00002222" +Room_396="060700002222f0222200222f0200300302f023113010222f220212211002f200113030302f203010210222f2222300302f0002002222f0002222" +Room_397="0a0a000222222f0222000022f0203333002f0200411402f0200310312f22032132122f20031031002f20334321202f20011110202f22222220002f00000022222" +Room_398="02050022222f00200022f2223330222f2001201002f2021201202f2001021202f2043330002f2220020222f00220002f00022222" +Room_399="02060022222f02201022f02004002f02034302f02112112f223010322f203020302f200020002f222222222" diff -r 000000000000 -r be33ecaa3619 levels/test --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/test Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,7 @@ +####### +# # +# . # +# @ # +# $ # +# # +####### diff -r 000000000000 -r be33ecaa3619 levels/xumi --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/levels/xumi Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,9 @@ +######### +## ## . # +# ## $. # + ## $ # +## $@ ### +# $ ## +#.. ## +# # +##### diff -r 000000000000 -r be33ecaa3619 sokosol-branques.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol-branques.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,381 @@ +#include +#include + +#define BOX '*' +#define WALL '#' +#define MAN '8' +#define PLATFORM '+' +#define BOXINPLATFORM 'O' +#define MANINPLATFORM 'E' +#define BLANK ' ' +#define CANTO '-' + +#define DIR_LEFT 'A' +#define DIR_RIGHT 'B' +#define DIR_UP 'C' +#define DIR_DOWN 'D' + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 100 + +#define MOVE_OK 1 +#define MOVE_BOX 2 +#define MOVE_ILLEGAL 0 + +/* SOKOBAN Solution Finder + * + * Cerca totes les possibilitats de tots els nombres de combinacions possibles, + * menys la que tots els moviments són a l'esquerra del número de combinacions + * incials triat. + */ + + +struct Map +{ + char Cells[MAX_X][MAX_Y]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; + char BoxMoved; // Boolean +}; + + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY++], MAX_X, Fitxer); + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { M->ManX = i; M->ManY = j; } + if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->NumPlatforms++; + M->NumBoxesInPlatform++; + } else if (M->Cells[j][i] != WALL) + if ((M->Cells[j][i-1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i-1] == WALL && + M->Cells[j+1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j+1][i] == WALL)) + M->Cells[j][i] = CANTO; + } + + M->Cells[M->ManY][M->ManX] = BLANK; + M->BoxMoved = 0; // Needed? +} + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + + +void ShowMap (struct Map *M) +{ + struct Map TempMap; + int i,j; + + CopyMap(&TempMap, M); + + if (TempMap.Cells[TempMap.ManY][TempMap.ManX] == BLANK) + TempMap.Cells[TempMap.ManY][TempMap.ManX] = MAN; + else + TempMap.Cells[TempMap.ManY][TempMap.ManX] = MANINPLATFORM; + + for (j = 0; jCells[M->ManY][M->ManX] != MAN && + M->Cells[M->ManY][M->ManX] != MANINPLATFORM) + { + printf("Man isn't where it should be!\n"); + exit(2); + } +*/ + + // Process Movement + if (Direction == DIR_LEFT) + { NewX = M->ManX - 1; NewY = M->ManY; } + else if (Direction == DIR_RIGHT) + { NewX = M->ManX + 1; NewY = M->ManY; } + else if (Direction == DIR_UP) + { NewX = M->ManX; NewY = M->ManY - 1; } + else + { NewX = M->ManX; NewY = M->ManY + 1; } + + + + // What's in front of the man? + + if (M->Cells[NewY][NewX] == WALL) + { + return MOVE_ILLEGAL; // ILLEGAL MOVE + } + else if (M->Cells[NewY][NewX] == BOX) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY][NewX] = BLANK; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + M->ManX = NewX; M->ManY = NewY; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY][NewX] = BLANK; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + M->ManX = NewX; M->ManY = NewY; + + M->NumBoxesInPlatform++; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + { + return MOVE_ILLEGAL; // ILLEGAL MOVE + } + }else + if (M->Cells[NewY][NewX] == BOXINPLATFORM) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY][NewX] = PLATFORM; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + M->ManX = NewX; M->ManY = NewY; + M->NumBoxesInPlatform--; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY][NewX] = PLATFORM; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + M->ManX = NewX; M->ManY = NewY; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + { + return MOVE_ILLEGAL; // ILLEGAL MOVE + } + } + else + { + M->ManX = NewX; M->ManY = NewY; + M->BoxMoved = 0; + return MOVE_OK; + } + + // Not Reachable + return MOVE_ILLEGAL; +} + +int InverseMove(char Dir1, char Dir2) +{ + if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) || + (Dir1 + Dir2 == DIR_UP + DIR_DOWN)) + return 1; + return 0; +} + +int main() +{ + struct Map Morigin; + struct Map M[MAX_MOVES+1]; + char Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + int MoveResult; + int Solution; + + int i; + + ReadMap(&Morigin, "model"); + + ShowMap(&Morigin); + + printf("Numero de moviments inicials a provar: "); + scanf("%i", &NumMoves); + IllegalMove = NumMoves - 1; + + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + CopyMap(&M[NumMoves], &Morigin); // For the first while cond. + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveMan(&M[i+1], Moves[i])) + { + IllegalMove = i; + break; + } + } + + // Process the combinations. + // Order: Left, Right, Up, Down + Solution = 0; + while (Solution == 0) + { + // Increase the Counter + { + Carry = 1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + Carry = 0; + if (Moves[i] == DIR_DOWN + 1) + { Moves[i] = DIR_LEFT; Carry = 1; } + } + OldMaps = i+1; // Sure? I think it's i+1 + // If we change the number of movements for solution + if (Carry) + { + printf("No Solution Found\n"); + NumMoves = 0; + Solution = 1; + break; + } + } + +/* + // Print the combination + + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); +*/ + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = OldMaps; i < NumMoves - 1; i++) + { + CopyMap(&M[i+1], &M[i]); + if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL) + { + IllegalMove = i; + break; + } else + if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) || + (Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) && + !M[i].BoxMoved) + { + IllegalMove = i; + break; + } + if (M[i+1].NumPlatforms == M[i+1].NumBoxesInPlatform) + { + Solution = i+1; + break; + } + + } + // Here i = NumMoves - 1 + CopyMap(&M[i+1], &M[i]); + if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL) + IllegalMove = i; + if (M[i+1].NumPlatforms == M[i+1].NumBoxesInPlatform && + Solution == 0) + { + Solution = i+1; + break; + } + + } + + // Print the combination + for (i=0; i < NumMoves; i++) + { + if (Moves[i] == DIR_LEFT) + printf("L"); + else if (Moves[i] == DIR_RIGHT) + printf("R"); + else if (Moves[i] == DIR_UP) + printf("U"); + else if (Moves[i] == DIR_DOWN) + printf("D"); + } + printf("\n"); + +/* + // Print The Steps + for (i=0; i < NumMoves; i++) + { + ShowMap(&M[i]); + } + return 0; +*/ + +} diff -r 000000000000 -r be33ecaa3619 sokosol-profund.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol-profund.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,856 @@ +#include +#include +#include +#include +#include +#include + +#define BOX '$' +#define WALL '#' +#define MAN '@' +#define PLATFORM '.' +#define BOXINPLATFORM '*' +#define MANINPLATFORM 'E' +#define BLANK ' ' +#define CORNER '-' +#define MANCANMOVE '+' + +#define NBOX(n) ((n)<<2) + +//#define DEBUG + +enum +{ + ALARM_SECONDS=1 +}; + + +enum logic +{ + TRUE=1, + FALSE=0, +}; + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 50 +#define MAX_STEPS 50 +#define MAX_BOXES 15 + +#define MOVE_OK 1 +#define MOVE_BOX 2 +#define MOVE_ILLEGAL 0 + + +/* SOKOBAN Solution Finder + * + * Input File Format: XSB + * + * XSB Format definition: + * Character matrix of: + * @ MAN + * # WALL + * $ BOX + * * BOX over PLATFORM + * + PLATFORM + * - (optional) Where a BOX should not be put + * Everything that cannot be reached by the man or boxes (WALLS) must be + * marked as is: WALLS. + * All lines must be of the same length. + */ + +struct Position +{ + int x; + int y; +}; + +struct Map +{ + char Cells[MAX_Y][MAX_X]; + char cells_boxes[MAX_Y][MAX_X]; + char man_moves[MAX_Y][MAX_X]; + int SizeX, SizeY; + struct Position Man; + int NumPlatforms; + int NumBoxesInPlatform; + struct Position Box[MAX_BOXES]; + int NumBoxes; +}; + + + +enum e_direction +{ + DIR_LEFT, + DIR_RIGHT, + DIR_DOWN, + DIR_UP +}; +const struct Position move_vectors[4] = { + {0, 1}, + {0, -1}, + {1, 0}, + {-1, 0}}; + +struct BoxMove +{ + int box; + struct Position dir; +}; + +float percent_to_show = 0; +int depth_to_show = 0; + +int max_depth = 0; +int min_depth_period = 0; +int max_depth_period = 0; +struct Map * actual_map; + + + + +void CopyMap (struct Map *Mdest, const struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY], MAX_X, Fitxer); + M->SizeY++; + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + M->NumBoxes = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { + M->Man.x = i; M->Man.y = j; + M->Cells[M->Man.y][M->Man.x] = BLANK; + } + + if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->Cells[j][i] = PLATFORM; + + M->NumPlatforms++; + M->NumBoxesInPlatform++; + + M->Box[M->NumBoxes].x = i; + M->Box[M->NumBoxes].y = j; + M->NumBoxes++; + } else if (M->Cells[j][i] == BOX) + { + M->Cells[j][i] = BLANK; + + M->Box[M->NumBoxes].x = i; + M->Box[M->NumBoxes].y = j; + M->NumBoxes++; + } else if (M->Cells[j][i] == CORNER) + { + M->Cells[j][i] = CORNER; + } else if (M->Cells[j][i] != WALL) + { + if ( (M->Cells[j][i-1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i-1] == WALL && + M->Cells[j+1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j+1][i] == WALL)) + M->Cells[j][i] = CORNER; + } + + } + +} + + +void ShowMap (const struct Map *M) +{ + struct Map Temp; + int i,j; + + CopyMap(&Temp, M); + + Temp.Cells[Temp.Man.y][Temp.Man.x] = MAN; + + for (i = 0; i < Temp.NumBoxes; i++) + { + if (Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] == PLATFORM) + Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] =BOXINPLATFORM; + else + Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] = BOX; + } + + for (j = 0; j> 2); + if ((Moves[i] & 0x03) == DIR_LEFT) + printf("L"); + else if ((Moves[i] & 0x03) == DIR_RIGHT) + printf("R"); + else if ((Moves[i] & 0x03) == DIR_UP) + printf("U"); + else + printf("D"); + printf(","); + } + printf("\n"); +} + +#if 0 /*** THIS IS AN ERROR!!! The box_will_be_blocked function doesn't work!*/ + Situation: + + ->@$ # + $ +*/ +int box_will_be_blocked(const struct Map * m, const struct Position mov, + const struct Position box_pos) +{ + struct Position next_pos2, tmp, tmp2[2]; + int i; + + next_pos2.x = box_pos.x + mov.x; + next_pos2.y = box_pos.y + mov.y; + + tmp.x = next_pos2.x + mov.x; + tmp.y = next_pos2.y + mov.y; + tmp2[0].x = next_pos2.x + mov.y; + tmp2[0].y = next_pos2.y + mov.x; + tmp2[1].x = next_pos2.x - mov.y; + tmp2[1].y = next_pos2.y - mov.x; + for (i=0; i < 2; i++) + { + if (m->man_moves[tmp.y][tmp.x] == WALL && + m->man_moves[tmp2[i].y][tmp2[i].x] == BOX) + { + return TRUE; + } + else if (m->man_moves[tmp.y][tmp.x] == BOX && + m->man_moves[tmp2[i].y][tmp2[i].x] == WALL) + { + return TRUE; + } + else if (m->man_moves[tmp.y][tmp.x] == BOX && + m->man_moves[tmp2[i].y][tmp2[i].x] == BOX) + { + return TRUE; + } + } + + return FALSE; +} + +int is_corner_area(const struct Map * m, const struct Position p, + const struct Position box, const struct Position new_box) +{ + int NumMoves, NewMoves; + struct Position pos[MAX_MOVES]; + struct Position new_pos[MAX_MOVES]; + char corners[MAX_Y][MAX_X]; + int i,j; + struct Position next_pos; + char *next_cell; + + + /* Blank the garden */ + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + corners[j][i] = m->Cells[j][i]; + + /* Let's put the boxes */ + for (i = 0; iNumBoxes; i++) + corners[m->Box[i].y][m->Box[i].x] = BOX; + + /* Let's put our box - it can be simply added */ + corners[new_box.y][new_box.x] = BOX; + /* Let's remove the original box. */ + corners[box.y][box.x] = BLANK; + + NewMoves = 1; + new_pos[0] = p; + while (NewMoves > 0) + { + /* The before named "New Moves" become the moves we have + to analyze */ + NumMoves = NewMoves; + for (i=0; iCells[p2.y][p2.x] == CORNER) + { + if (is_corner_area(m, p2, box_pos, p)) + return TRUE; + } + + p2.x = p.x + mov.y; + p2.y = p.y + mov.x; + if (m->Cells[p2.y][p2.x] == CORNER) + { + if (is_corner_area(m, p2, box_pos, p)) + return TRUE; + } + + p2.x = p.x - mov.y; + p2.y = p.y - mov.x; + if (m->Cells[p2.y][p2.x] == CORNER) + { + if (is_corner_area(m, p2, box_pos, p)) + return TRUE; + } + return FALSE; +} +#endif + +/* +Catch the situation where a box is moved next to a corner, where the box +next to it will not be able to be moved. +*/ +int is_dead1(const struct Map * m, const struct Position mov, + const struct Position new_pos) +{ + struct Position opposite1, opposite2; + + /* The wall corners must exist */ + opposite1.x = -mov.y; + opposite1.y = -mov.x; + opposite2.x = mov.y; + opposite2.y = mov.x; + +#ifdef DEBUG + ShowMap(m); +#endif + + /* Test the first corner */ + if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x] + == WALL) + { + /* Test wall at opposites 1*/ + if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x] + == WALL && + m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX) + { + return TRUE; + } + else + if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x] + == BOX && + m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL) + { + return TRUE; + } + /* Test wall at opposites 2 */ + if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x] + == WALL && + m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX) + { + return TRUE; + } + else + if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x] + == BOX && + m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL) + { + return TRUE; + } + } + + /* Test the second corner */ + if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x] + == WALL) + { + /* Test wall at opposites 1*/ + if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x] + == WALL && + m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX) + { + return TRUE; + } + else + if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x] + == BOX && + m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL) + { + return TRUE; + } + /* Test wall at opposites 2 */ + if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x] + == WALL && + m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX) + { + return TRUE; + } + else + if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x] + == BOX && + m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL) + { + return TRUE; + } + } + + return FALSE; +} + +/* +Catch the situation where a corner gets surrounded by boxes. +*/ +int is_dead2(const struct Map * m, const struct Position mov, + const struct Position new_pos) +{ + struct Position next, next2, opposite1, opposite2; + + next.x = new_pos.x+mov.x; + next.y = new_pos.y+mov.y; + + /* The corner must exist */ + if (m->Cells[next.y][next.x] != CORNER) + return FALSE; + + + /* The wall corners must exist */ + opposite1.x = next.x -mov.y; + opposite1.y = next.y -mov.x; + opposite2.x = next.x + mov.y; + opposite2.y = next.y + mov.x; + + if (m->man_moves[opposite1.y][opposite1.x] == BOX) + { + if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL + && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL) + return TRUE; + } + + if (m->man_moves[opposite2.y][opposite2.x] == BOX) + { + if(m->Cells[opposite2.y+mov.y][opposite2.x+mov.x] == WALL + && m->Cells[opposite2.y-mov.y][opposite2.x-mov.x] == WALL) + return TRUE; + } + return FALSE; +} + +int is_box_movable(const struct Map * m, const struct Position mov, + const struct Position box_pos) +{ + struct Position next_pos2; + + next_pos2.x = box_pos.x + mov.x; + next_pos2.y = box_pos.y + mov.y; + + if((m->Cells[next_pos2.y][next_pos2.x] != BLANK && + m->Cells[next_pos2.y][next_pos2.x] != PLATFORM) || + m->man_moves[next_pos2.y][next_pos2.x] == BOX) + { + return FALSE; + } + else if (is_dead1(m, mov, next_pos2) == TRUE) + { + return FALSE; + } + else if (is_dead2(m, mov, next_pos2) == TRUE) + { + return FALSE; + } + return TRUE; +} + +/* It modifies m->man_moves */ +int get_box_movements(struct Map * m, + struct BoxMove movements[]) +{ + struct Position pos[MAX_MOVES]; + struct Position new_pos[MAX_MOVES]; + int NumMoves, NewMoves; + int j, i; + struct Position next_pos; + char *next_cell; + int num_box_movements = 0; + + /* Let's the map with only walls in man_moves - other, blanks */ + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (m->Cells[j][i] == WALL) + m->man_moves[j][i] = WALL; + else + m->man_moves[j][i] = BLANK; + } + + /* Let's put the boxes */ + for (i = 0; iNumBoxes; i++) + { + m->man_moves[m->Box[i].y][m->Box[i].x] = BOX; + m->cells_boxes[m->Box[i].y][m->Box[i].x] = i; + } + + NewMoves = 1; + new_pos[0].x = m->Man.x; + new_pos[0].y = m->Man.y; + m->man_moves[m->Man.y][m->Man.x] = MANCANMOVE; + while (NewMoves > 0) + { + /* The before named "New Moves" become the moves we have + to analyze */ + NumMoves = NewMoves; + for (i=0; iman_moves[next_pos.y][next_pos.x]; + if(*next_cell == BLANK) + { + new_pos[NewMoves] = next_pos; + *next_cell = MANCANMOVE; + NewMoves++; + } + else if (*next_cell == BOX) + { + + /* Check if the box is movable */ + + if (is_box_movable(m, move_vectors[j], + next_pos )) + { + { + movements[num_box_movements].box = + m->cells_boxes[next_pos.y][next_pos.x]; + movements[num_box_movements].dir = + move_vectors[j]; + num_box_movements++; + } + } + + } + + } + } + } + + return num_box_movements; +} + +void force_move_box(struct Map *m, struct BoxMove move) +{ + struct Position newpos; + + + /* Add coords */ + newpos.x = m->Box[move.box].x + move.dir.x; + newpos.y = m->Box[move.box].y + move.dir.y; + + /* Be certain the move can be done */ + assert(m->Cells[newpos.y][newpos.x] != BOX); + assert(m->Cells[newpos.y][newpos.x] != WALL); + + /* Control if we moved the box to a platform */ + if(m->Cells[newpos.y][newpos.x] == PLATFORM) + { + m->NumBoxesInPlatform++; + } + + /* Control if we moved the box from a platform */ + if (m->Cells[m->Box[move.box].y][m->Box[move.box].x] == PLATFORM) + { + m->NumBoxesInPlatform--; + } + m->Man = m->Box[move.box]; + + m->Box[move.box] = newpos; +} + +int are_boxes_equal(const struct Position b1[], const struct Position b2[], + int n) +{ + int i; + char tmp[MAX_Y][MAX_X]; /* !!!argh */ + + memset(tmp, 0, sizeof(tmp)); + + for (i=0; i < n; i++) + { + tmp[b1[i].y][b1[i].x] = 1; + } + for (i=0; i < n; i++) + { + if (tmp[b2[i].y][b2[i].x] != 1) + return FALSE; + } + return TRUE; +} + +int is_new_map(struct Map maps[], int depth) +{ + struct Map *m; + int i; + + m = &maps[depth]; + + for(i=0; iNumBoxesInPlatform != maps[i].NumBoxesInPlatform) + continue; + else + { + if (!are_boxes_equal(m->Box, maps[i].Box, m->NumBoxes)) + continue; + } + return FALSE; + } + return TRUE; +} + +void PrintMove(struct BoxMove b) +{ + printf("Box: %i, Direction: {%i,%i}\n", b.box, b.dir.x, b.dir.y); +} + +void show_percent_callback(int parameter) +{ + fprintf(stderr, "Percent: %2.12f, depth: %i-%i\n", percent_to_show, + min_depth_period, max_depth_period); + ShowMap(actual_map); + fflush(stderr); + min_depth_period = MAX_STEPS; + max_depth_period = 0; +#ifndef DEBUG + alarm(ALARM_SECONDS); +#endif +} + +int search_depth(struct Map maps[], int depth, + struct BoxMove movements[], + int num_movements, float percent, float total_percent) +{ + struct BoxMove new_movements[MAX_MOVES]; + int num_new_movements; + struct Map *m; + int i; + float next_percent; + + next_percent = percent / num_movements; + + m = &maps[depth+1]; + if (depth > max_depth) + max_depth = depth; + if (depth > max_depth_period) + max_depth_period = depth; + if (depth < min_depth_period) + min_depth_period = depth; + + for (i=0; i < num_movements; i++) + { + CopyMap(m, &maps[depth]); + force_move_box(m, movements[i]); + if (m->NumPlatforms == m->NumBoxesInPlatform) + { + printf("\nSolved!\n"); + PrintMove(movements[i]); + return 0; + } + + if (is_new_map(maps, depth+1)) + { + num_new_movements = get_box_movements(m, new_movements); + assert(num_new_movements < MAX_MOVES); + } + else + num_new_movements = 0; + + if (num_new_movements == 0) + { + percent_to_show = total_percent + next_percent*i; + depth_to_show = depth; + actual_map = &maps[depth]; +#ifdef DEBUG /* to be out */ + show_percent_callback(0); +#endif + + } + else + { + if (depth+1 < MAX_STEPS) + { + if(search_depth(maps, depth+1, new_movements, + num_new_movements, next_percent, + total_percent + next_percent*i) == 0) + { + PrintMove(movements[i]); + return 0; + } + } + } + } + return 1; +} + + + + +void program_alarm() +{ + struct sigaction my_action; + int result; + + my_action.sa_handler = show_percent_callback; + my_action.sa_flags = 0; + memset(&my_action.sa_mask, 0, sizeof(my_action.sa_mask)); + + result = sigaction(SIGALRM, &my_action, NULL); + assert(result == 0); + + alarm(1); +} + +int main(int argn, char **argv) +{ + struct Map Morigin; + struct Map maps[MAX_STEPS+1]; + struct BoxMove new_movements[MAX_MOVES]; + int num_new_movements; + + + if (argn != 2) + { + printf("Usage: %s \n", argv[0]); + exit(3); + } + ReadMap(&Morigin, argv[1]); + + // Reget the original map + CopyMap(&maps[0], &Morigin); + + assert(maps[0].NumPlatforms > maps[0].NumBoxesInPlatform); + + num_new_movements = get_box_movements(&maps[0], new_movements); + assert(num_new_movements < MAX_MOVES); + assert(num_new_movements > 0); + +#ifndef DEBUG + program_alarm(); +#endif + search_depth(maps, 0, new_movements, + num_new_movements, 100. / num_new_movements, + 0); + + return 0; + +} diff -r 000000000000 -r be33ecaa3619 sokosol.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,381 @@ +#include +#include + +#define BOX '*' +#define WALL '#' +#define MAN '8' +#define PLATFORM '+' +#define BOXINPLATFORM 'O' +#define MANINPLATFORM 'E' +#define BLANK ' ' + +#define DIR_LEFT 'A' +#define DIR_RIGHT 'B' +#define DIR_UP 'C' +#define DIR_DOWN 'D' + +#define MAX_X 500 +#define MAX_Y 500 +#define MAX_MOVES 100 + +/* SOKOBAN Solution Finder + * + * Cerca totes les possibilitats de tots els nombres de combinacions possibles, + * menys la que tots els moviments són a l'esquerra del número de combinacions + * incials triat. + */ + + +struct Map +{ + char Cells[MAX_X][MAX_Y]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; +}; + + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY++], MAX_X, Fitxer); + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { M->ManX = i; M->ManY = j; } + else if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->NumPlatforms++; + M->NumBoxesInPlatform++; + } + } +} + + +void ShowMap (struct Map *M) +{ + int i,j; + for (j = 0; jSizeY; j++) + { + for (i=0; iSizeX; i++) + printf("%c", M->Cells[j][i]); + printf("\n"); + } + printf("Man is at (%i,%i)\n", M->ManX, M->ManY); + printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms, + M->NumBoxesInPlatform); +} + + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + +int MoveMan (struct Map *M, int Direction) +{ + int NewX, NewY; + +/* + // Check if man is where it should be + if (M->Cells[M->ManY][M->ManX] != MAN && + M->Cells[M->ManY][M->ManX] != MANINPLATFORM) + { + printf("Man isn't where it should be!\n"); + exit(2); + } +*/ + + // Process Movement + if (Direction == DIR_LEFT) + { NewX = M->ManX - 1; NewY = M->ManY; } + else if (Direction == DIR_RIGHT) + { NewX = M->ManX + 1; NewY = M->ManY; } + else if (Direction == DIR_UP) + { NewX = M->ManX; NewY = M->ManY - 1; } + else if (Direction == DIR_DOWN) // if not needed + { NewX = M->ManX; NewY = M->ManY + 1; } + + + + // What's in front of the man? + + if (M->Cells[NewY][NewX] == WALL) + { + return 0; // ILLEGAL MOVE + } + else if (M->Cells[NewY][NewX] == BOX) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + + M->NumBoxesInPlatform++; + return 1; + } + else + { + return 0; // ILLEGAL MOVE + } + }else + if (M->Cells[NewY][NewX] == BOXINPLATFORM) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + M->NumBoxesInPlatform--; + return 1; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + else + { + return 0; // ILLEGAL MOVE + } + } + else if (M->Cells[NewY][NewX] == PLATFORM) + { + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + else if (M->Cells[NewY][NewX] == BLANK) // IF not needed + { + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + return 1; +} + +int main(int argn, char **argv) +{ + struct Map Morigin, M[MAX_MOVES]; + char Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + + int i, j; + + if (argn != 2) + { + printf("Usage: %s \n", argv[0]); + exit(3); + } + + ReadMap(&Morigin, argv[1]); + sscanf(argv[2], "%i", &NumMoves); + + ShowMap(&Morigin); + + CopyMap(&M, &Morigin); + + IllegalMove = NumMoves - 1; + + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + + OldMaps = 0; + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + // Could we use OldMaps for indexing, as faster than i+1? + if (!MoveMan(&M[i+1], Moves[i])) + { + IllegalMove = i; + break; + } + } + + // Process the combinations. + // Order: Left, Right, Up, Down + while (M.NumPlatforms != M.NumBoxesInPlatform) + { + // Increase the Counter + { + Carry = 1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + if (Moves[i] == DIR_DOWN + 1) + { Moves[i] = DIR_LEFT; Carry = 1; } + } + OldMaps = i; // Sure? + // If we change the number of movements for solution + if (Carry) + { + if (NumMoves > MAX_MOVES) + break; // MAX MOVES EXCEEDED!!! + NumMoves++; + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + printf("Provant %i moviments...\n", NumMoves); + } + } + +/* + // Print the combination + + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); +*/ + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + if (i>=OldMaps) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveMan(&M[i+1], Moves[i])) + { + IllegalMove = i; + break; + } + } + } + + } + + // Print the combination + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); + +/* + // Print The Steps + strcpy(Moves, "DDDRUU"); + + for (i=0; i < 6; i++) + { + printf("%i", MoveMan(&M, Moves[i])); + ShowMap(&M); + } +*/ + +} diff -r 000000000000 -r be33ecaa3619 sokosol2.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol2.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,311 @@ +#include +#include +#include + +#define BOX '*' +#define WALL '#' +#define MAN '8' +#define PLATFORM '+' +#define BOXINPLATFORM 'O' +#define MANINPLATFORM 'E' +#define BLANK ' ' + +#define DIR_LEFT 0 +#define DIR_RIGHT 1 +#define DIR_UP 2 +#define DIR_DOWN 3 + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 100 + +struct Map +{ + char Cells[MAX_X][MAX_Y]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; +}; + + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY++], MAX_X, Fitxer); + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { M->ManX = i; M->ManY = j; } + else if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->NumPlatforms++; + M->NumBoxesInPlatform++; + } + } +} + + +void ShowMap (struct Map *M) +{ + int i,j; + for (j = 0; jSizeY; j++) + { + for (i=0; iSizeX; i++) + printf("%c", M->Cells[j][i]); + printf("\n"); + } + printf("Man is at (%i,%i)\n", M->ManX, M->ManY); + printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms, + M->NumBoxesInPlatform); +} + + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + +int MoveMan (struct Map *M, int Direction) +{ + int NewX, NewY; + + // Check if man is where it should be + if (M->Cells[M->ManY][M->ManX] != MAN && + M->Cells[M->ManY][M->ManX] != MANINPLATFORM) + { + printf("Man isn't where it should be!\n"); + exit(2); + } + + // Process Movement + if (Direction == DIR_LEFT) + { NewX = M->ManX - 1; NewY = M->ManY; } + else if (Direction == DIR_RIGHT) + { NewX = M->ManX + 1; NewY = M->ManY; } + else if (Direction == DIR_UP) + { NewX = M->ManX; NewY = M->ManY - 1; } + else if (Direction == DIR_DOWN) // if not needed + { NewX = M->ManX; NewY = M->ManY + 1; } + + + + // What's in front of the man? + + if (M->Cells[NewY][NewX] == WALL) + { + return 0; // ILLEGAL MOVE + } + else if (M->Cells[NewY][NewX] == BOX) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + + M->NumBoxesInPlatform++; + } + else + { + return 0; // ILLEGAL MOVE + } + }else + if (M->Cells[NewY][NewX] == BOXINPLATFORM) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + M->NumBoxesInPlatform--; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + } + else + { + return 0; // ILLEGAL MOVE + } + } + else if (M->Cells[NewY][NewX] == PLATFORM) + { + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + } + else if (M->Cells[NewY][NewX] == BLANK) // IF not needed + { + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + } + return 1; +} + +int main() +{ + struct Map Morigin, M; + char Moves[MAX_MOVES]; + int NumMoves; + int IllegalMove; + int Carry; + int Arrel; + + int i, j; + + ReadMap(&Morigin, "model"); + + ShowMap(&Morigin); + + CopyMap(&M, &Morigin); + + printf("Numero de moviments a provar: "); + scanf("%i", &NumMoves); + printf("Arrel: "); + scanf("%i", &Arrel); + srand(Arrel); + + // Process the combinations. + // Order: Left, Right, Up, Down + while (M.NumPlatforms != M.NumBoxesInPlatform) + { + // Reget the original map + CopyMap(&M, &Morigin); + +/* + // Print the combination + + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); +*/ + + // Process the combination + for (i = 0; i < NumMoves; i++) + { + if (!MoveMan(&M, Moves[i]=rand()%4)) + break; + } + + } + + // Print the combination + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]+48); + } + printf("\n"); + +/* + // Print The Steps + strcpy(Moves, "DDDRUU"); + + for (i=0; i < 6; i++) + { + printf("%i", MoveMan(&M, Moves[i])); + ShowMap(&M); + } +*/ + +} diff -r 000000000000 -r be33ecaa3619 sokosol3.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol3.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,375 @@ +#include +#include + +#define BOX '*' +#define WALL '#' +#define MAN '8' +#define PLATFORM '+' +#define BOXINPLATFORM 'O' +#define MANINPLATFORM 'E' +#define BLANK ' ' + +#define DIR_LEFT 'A' +#define DIR_RIGHT 'B' +#define DIR_UP 'C' +#define DIR_DOWN 'D' + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 50 + +/* SOKOBAN Solution Finder + * + * Cerca totes les possibilitats de tots els nombres de combinacions possibles, + * menys la que tots els moviments són a l'esquerra del número de combinacions + * incials triat. + */ + + +struct Map +{ + char Cells[MAX_X][MAX_Y]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; +}; + + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY++], MAX_X, Fitxer); + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { M->ManX = i; M->ManY = j; } + else if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->NumPlatforms++; + M->NumBoxesInPlatform++; + } + } +} + + +void ShowMap (struct Map *M) +{ + int i,j; + for (j = 0; jSizeY; j++) + { + for (i=0; iSizeX; i++) + printf("%c", M->Cells[j][i]); + printf("\n"); + } + printf("Man is at (%i,%i)\n", M->ManX, M->ManY); + printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms, + M->NumBoxesInPlatform); +} + + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + +int MoveMan (struct Map *M, int Direction) +{ + int NewX, NewY; + +/* + // Check if man is where it should be + if (M->Cells[M->ManY][M->ManX] != MAN && + M->Cells[M->ManY][M->ManX] != MANINPLATFORM) + { + printf("Man isn't where it should be!\n"); + exit(2); + } +*/ + + // Process Movement + if (Direction == DIR_LEFT) + { NewX = M->ManX - 1; NewY = M->ManY; } + else if (Direction == DIR_RIGHT) + { NewX = M->ManX + 1; NewY = M->ManY; } + else if (Direction == DIR_UP) + { NewX = M->ManX; NewY = M->ManY - 1; } + else + { NewX = M->ManX; NewY = M->ManY + 1; } + + + + // What's in front of the man? + + if (M->Cells[NewY][NewX] == WALL) + { + return 0; // ILLEGAL MOVE + } + else if (M->Cells[NewY][NewX] == BOX) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + + M->NumBoxesInPlatform++; + return 1; + } + else + { + return 0; // ILLEGAL MOVE + } + }else + if (M->Cells[NewY][NewX] == BOXINPLATFORM) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + M->NumBoxesInPlatform--; + return 1; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + else + { + return 0; // ILLEGAL MOVE + } + } + else if (M->Cells[NewY][NewX] == PLATFORM) + { + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MANINPLATFORM; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + else if (M->Cells[NewY][NewX] == BLANK) // IF not needed + { + if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) + { // Man is over Platform + M->Cells[M->ManY][M->ManX] = PLATFORM; + M->Cells[NewY][NewX] = MAN; + } + else // Man is over Blank + { + M->Cells[M->ManY][M->ManX] = BLANK; + M->Cells[NewY][NewX] = MAN; + } + M->ManX = NewX; M->ManY = NewY; + return 1; + } + return 1; +} + +int main() +{ + struct Map Morigin; + struct Map M[MAX_MOVES+1]; + char Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + + int i; + + ReadMap(&Morigin, "model"); + + ShowMap(&Morigin); + + printf("Numero de moviments inicials a provar: "); + scanf("%i", &NumMoves); + IllegalMove = NumMoves - 1; + + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + CopyMap(&M[NumMoves], &Morigin); // For the first while cond. + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveMan(&M[i+1], Moves[i])) + { + IllegalMove = i; + break; + } + } + + // Process the combinations. + // Order: Left, Right, Up, Down + while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform) + { + // Increase the Counter + { + Carry = 1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + Carry = 0; + if (Moves[i] == DIR_DOWN + 1) + { Moves[i] = DIR_LEFT; Carry = 1; } + } + OldMaps = i+1; // Sure? I think it's i+1 + // If we change the number of movements for solution + if (Carry) + { + if (NumMoves > MAX_MOVES) + break; // MAX MOVES EXCEEDED!!! + NumMoves++; + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + OldMaps=0; + CopyMap(&M[NumMoves], &Morigin); + // For the first while cond. + printf("Provant %i moviments...\n", NumMoves); + } + } + +/* + // Print the combination + + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); +*/ + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = OldMaps; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveMan(&M[i+1], Moves[i])) + { + IllegalMove = i; + break; + } + } + + } + + // Print the combination + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); + +/* + // Print The Steps + strcpy(Moves, "DDDRUU"); + + for (i=0; i < 6; i++) + { + printf("%i", MoveMan(&M, Moves[i])); + ShowMap(&M); + } +*/ + return 0; + +} diff -r 000000000000 -r be33ecaa3619 sokosol4.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol4.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,366 @@ +#include +#include + +#define BOX '$' +#define WALL '#' +#define MAN '@' +#define PLATFORM '.' +#define BOXINPLATFORM '*' +#define MANINPLATFORM 'E' +#define BLANK ' ' +#define CANTO '-' + +#define DIR_LEFT 'A' +#define DIR_RIGHT 'B' +#define DIR_UP 'C' +#define DIR_DOWN 'D' + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 50 + +#define MOVE_OK 1 +#define MOVE_BOX 2 +#define MOVE_ILLEGAL 0 + +/* SOKOBAN Solution Finder + * + * Cerca totes les possibilitats de tots els nombres de combinacions possibles, + * menys la que tots els moviments són a l'esquerra del número de combinacions + * incials triat. + */ + + +struct Map +{ + char Cells[MAX_X][MAX_Y]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; + char BoxMoved; // Boolean +}; + + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY++], MAX_X, Fitxer); + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { M->ManX = i; M->ManY = j; } + if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->NumPlatforms++; + M->NumBoxesInPlatform++; + } else if (M->Cells[j][i] != WALL) + if ((M->Cells[j][i-1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i-1] == WALL && + M->Cells[j+1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j+1][i] == WALL)) + M->Cells[j][i] = CANTO; + } + + M->Cells[M->ManY][M->ManX] = BLANK; + M->BoxMoved = 0; // Needed? +} + + +void ShowMap (struct Map *M) +{ + int i,j; + for (j = 0; jSizeY; j++) + { + for (i=0; iSizeX; i++) + printf("%c", M->Cells[j][i]); + printf("\n"); + } + printf("Man is at (%i,%i)\n", M->ManX, M->ManY); + printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms, + M->NumBoxesInPlatform); +} + + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + +int MoveMan (struct Map *M, int Direction) +{ + int NewX, NewY; + +/* + // Check if man is where it should be + if (M->Cells[M->ManY][M->ManX] != MAN && + M->Cells[M->ManY][M->ManX] != MANINPLATFORM) + { + printf("Man isn't where it should be!\n"); + exit(2); + } +*/ + + // Process Movement + if (Direction == DIR_LEFT) + { NewX = M->ManX - 1; NewY = M->ManY; } + else if (Direction == DIR_RIGHT) + { NewX = M->ManX + 1; NewY = M->ManY; } + else if (Direction == DIR_UP) + { NewX = M->ManX; NewY = M->ManY - 1; } + else + { NewX = M->ManX; NewY = M->ManY + 1; } + + + + // What's in front of the man? + + if (M->Cells[NewY][NewX] == WALL) + { + return MOVE_ILLEGAL; // ILLEGAL MOVE + } + else if (M->Cells[NewY][NewX] == BOX) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY][NewX] = BLANK; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + M->ManX = NewX; M->ManY = NewY; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY][NewX] = BLANK; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + M->ManX = NewX; M->ManY = NewY; + + M->NumBoxesInPlatform++; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + { + return MOVE_ILLEGAL; // ILLEGAL MOVE + } + }else + if (M->Cells[NewY][NewX] == BOXINPLATFORM) + { + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + BLANK) + { + M->Cells[NewY][NewX] = PLATFORM; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOX; + + M->ManX = NewX; M->ManY = NewY; + M->NumBoxesInPlatform--; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == + PLATFORM) + { + M->Cells[NewY][NewX] = PLATFORM; + M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] + = BOXINPLATFORM; + + M->ManX = NewX; M->ManY = NewY; + M->BoxMoved = 1; + return MOVE_BOX; + } + else + { + return MOVE_ILLEGAL; // ILLEGAL MOVE + } + } + else + { + M->ManX = NewX; M->ManY = NewY; + M->BoxMoved = 0; + return MOVE_OK; + } + + // Not Reachable + return MOVE_ILLEGAL; +} + +int InverseMove(char Dir1, char Dir2) +{ + if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) || + (Dir1 + Dir2 == DIR_UP + DIR_DOWN)) + return 1; + return 0; +} + +int main(int argn, char **argv) +{ + struct Map Morigin; + struct Map M[MAX_MOVES+1]; + char Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + int MoveResult; + + int i; + + if (argn != 3) + { + printf("Usage: %s \n", argv[0]); + exit(3); + } + ReadMap(&Morigin, argv[1]); + sscanf(argv[2], "%i", &NumMoves); + + ShowMap(&Morigin); + + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + CopyMap(&M[NumMoves], &Morigin); // For the first while cond. + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveMan(&M[i+1], Moves[i])) + { + IllegalMove = i; + break; + } + } + + // Process the combinations. + // Order: Left, Right, Up, Down + while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform) + { + // Increase the Counter + { + Carry = 1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + Carry = 0; + if (Moves[i] == DIR_DOWN + 1) + { Moves[i] = DIR_LEFT; Carry = 1; } + } + OldMaps = i+1; // Sure? I think it's i+1 + // If we change the number of movements for solution + if (Carry) + { + if (NumMoves > MAX_MOVES) + break; // MAX MOVES EXCEEDED!!! + NumMoves++; + for (i = 0; i < NumMoves; i++) + Moves[i] = DIR_LEFT; + OldMaps=0; + CopyMap(&M[NumMoves], &Morigin); + // For the first while cond. + printf("Provant %i moviments...\n", NumMoves); + } + } + +/* + // Print the combination + + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); +*/ + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = OldMaps; i < NumMoves - 1; i++) + { + CopyMap(&M[i+1], &M[i]); + if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL) + { + IllegalMove = i; + break; + } else + if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) || + (Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) && + !M[i].BoxMoved) + { + IllegalMove = i; + break; + } + + } + // Here i = NumMoves - 1 + CopyMap(&M[i+1], &M[i]); + if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL) + IllegalMove = i; + + } + + // Print the combination + for (i=0; i < NumMoves; i++) + { + if (Moves[i] == DIR_LEFT) + printf("L"); + else if (Moves[i] == DIR_RIGHT) + printf("R"); + else if (Moves[i] == DIR_UP) + printf("U"); + else if (Moves[i] == DIR_DOWN) + printf("D"); + } + printf("\n"); + +/* + // Print The Steps + for (i=0; i < NumMoves; i++) + { + ShowMap(&M[i]); + } +*/ + return 0; + +} diff -r 000000000000 -r be33ecaa3619 sokosol5.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosol5.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,486 @@ +#include +#include + +#define BOX '$' +#define WALL '#' +#define MAN '@' +#define PLATFORM '.' +#define BOXINPLATFORM '*' +#define MANINPLATFORM 'E' +#define BLANK ' ' +#define CANTO '-' +#define MANCANMOVE '+' + +#define NBOX(n) ((n)<<2) + +#define DIR_LEFT 0 +#define DIR_RIGHT 1 +#define DIR_UP 2 +#define DIR_DOWN 3 + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 50 +#define MAX_BOXES 15 + +#define MOVE_OK 1 +#define MOVE_BOX 2 +#define MOVE_ILLEGAL 0 + +/* SOKOBAN Solution Finder + * + * Input File Format: XSB + * + * XSB Format definition: + * Character matrix of: + * @ MAN + * # WALL + * $ BOX + * * BOX over PLATFORM + * + PLATFORM + * - (optional) Where a BOX should not be put + * Everything that cannot be reached by the man or boxes (WALLS) must be + * marked as is: WALLS. + * All lines must be of the same length. + */ + + +struct Map +{ + char Cells[MAX_Y][MAX_X]; + char ManMoves[MAX_Y][MAX_X]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; + int BoxX[MAX_BOXES]; + int BoxY[MAX_BOXES]; + int NumBoxes; +}; + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY], MAX_X, Fitxer); + M->SizeY++; + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + M->NumBoxes = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { + M->ManX = i; M->ManY = j; + M->Cells[M->ManY][M->ManX] = BLANK; + } + + if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->Cells[j][i] = PLATFORM; + + M->NumPlatforms++; + M->NumBoxesInPlatform++; + + M->BoxX[M->NumBoxes] = i; + M->BoxY[M->NumBoxes] = j; + M->NumBoxes++; + } else if (M->Cells[j][i] == BOX) + { + M->Cells[j][i] = BLANK; + + M->BoxX[M->NumBoxes] = i; + M->BoxY[M->NumBoxes] = j; + M->NumBoxes++; + } else if (M->Cells[j][i] != WALL) + { + if ( (M->Cells[j][i-1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i-1] == WALL && + M->Cells[j+1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j+1][i] == WALL)) + M->Cells[j][i] = CANTO; + } + + } + +} + + +void ShowMap (struct Map *M) +{ + struct Map Temp; + int i,j; + + CopyMap(&Temp, M); + + Temp.Cells[Temp.ManY][Temp.ManX] = MAN; + + for (i = 0; i < Temp.NumBoxes; i++) + { + if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM) + Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM; + else + Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX; + } + + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK; + for (i = 0; iNumBoxes; i++) + M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL; + + NewMoves = 1; + NewX[0] = M->ManX; + NewY[0] = M->ManY; + while (NewMoves) + { + NumMoves = NewMoves; + for (i=0; iManMoves[Y[i]][X[i]-1] == BLANK) + { + NewX[NewMoves] = X[i]-1; + NewY[NewMoves] = Y[i]; + M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE; + NewMoves++; + } + if(M->ManMoves[Y[i]][X[i]+1] == BLANK) + { + NewX[NewMoves] = X[i]+1; + NewY[NewMoves] = Y[i]; + M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE; + NewMoves++; + } + if(M->ManMoves[Y[i]-1][X[i]] == BLANK) + { + NewX[NewMoves] = X[i]; + NewY[NewMoves] = Y[i]-1; + M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE; + NewMoves++; + } + if(M->ManMoves[Y[i]+1][X[i]] == BLANK) + { + NewX[NewMoves] = X[i]; + NewY[NewMoves] = Y[i]+1; + M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE; + NewMoves++; + } + } + } +} + +int MoveBox(struct Map *M, int NumBox, int Direction) +{ + char InPlatform; + + InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM); + + switch(Direction) + { + case DIR_LEFT: + if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] == + MANCANMOVE && + M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] != + WALL && + M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]-1] != + CANTO) + { + M->ManX = M->BoxX[NumBox]; + M->ManY = M->BoxY[NumBox]; + + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxX[NumBox]--; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + case DIR_RIGHT: + if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] == + MANCANMOVE && + M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] != + WALL && + M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] != + CANTO) + { + M->ManX = M->BoxX[NumBox]; + M->ManY = M->BoxY[NumBox]; + + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxX[NumBox]++; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + case DIR_UP: + if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] == + MANCANMOVE && + M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] != + WALL && + M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] != + CANTO) + { + M->ManX = M->BoxX[NumBox]; + M->ManY = M->BoxY[NumBox]; + + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxY[NumBox]--; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + case DIR_DOWN: + if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] == + MANCANMOVE && + M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] != + WALL && + M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] != + CANTO) + { + M->ManX = M->BoxX[NumBox]; + M->ManY = M->BoxY[NumBox]; + + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxY[NumBox]++; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + } + return 0; +} + +void PrintCombination(int Moves[], int NumMoves) +{ + int i; + + for (i=0; i < NumMoves; i++) + { + printf("%i", Moves[i] >> 2); + if ((Moves[i] & 0x03) == DIR_LEFT) + printf("L"); + else if ((Moves[i] & 0x03) == DIR_RIGHT) + printf("R"); + else if ((Moves[i] & 0x03) == DIR_UP) + printf("U"); + else + printf("D"); + printf(","); + } + printf("\n"); +} + +int main(int argn, char **argv) +{ + struct Map Morigin; + struct Map M[MAX_MOVES+1]; + int Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + + int i; + + if (argn != 3) + { + printf("Usage: %s \n", argv[0]); + exit(3); + } + ReadMap(&Morigin, argv[1]); + sscanf(argv[2], "%i", &NumMoves); + + + for (i = 0; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + CopyMap(&M[NumMoves], &Morigin); // For the first while cond. + + GetManMoves(&M[0]); + + ShowMap(&M[0]); + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + { + IllegalMove = i; + break; + } + GetManMoves(&M[i+1]); + } + + // Main solution finder loop + while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform) + { + // Increase the Counter + { + Carry = 1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + Carry = 0; + if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1) + { Moves[i] = NBOX(0) + DIR_LEFT; Carry = 1; } + } + OldMaps = i+1; // Sure? I think it's i+1 + // If we change the number of movements for solution + if (Carry) + { + if (NumMoves > MAX_MOVES) + break; // MAX MOVES EXCEEDED!!! + NumMoves++; + for (i = 0; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + OldMaps=0; + CopyMap(&M[NumMoves], &Morigin); + // For the first while cond. + printf("Provant %i moviments...\n", NumMoves); + } + } + + // Print the combination +// PrintCombination(Moves, NumMoves); + + IllegalMove = NumMoves - 1; + // Process the combination +// printf("------- STARTING COMBINATION ------------\n"); + for (i = OldMaps; i < NumMoves - 1; i++) + { + CopyMap(&M[i+1], &M[i]); +// GetManMoves(&M[i+1]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + { + IllegalMove = i; + break; + }/* else // Si el moviment es bo + if ((Moves[i] >> 2) == (Moves[i+1] >> 2) && + ((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 1|| + ((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 5))) + { + IllegalMove = i; + break; + }*/ + GetManMoves(&M[i+1]); +// ShowMap(&M[i+1]); + + } + // Here i = NumMoves - 1 + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + IllegalMove = i; +/* + for (i=0;i < IllegalMove; i++) + { + ShowMap(&M[i+1]); + } +*/ + + } + + // Print the combination + PrintCombination(Moves, NumMoves); + +/* + // Print The Steps + for (i=0; i < NumMoves; i++) + { + ShowMap(&M[i]); + } +*/ + return 0; + +} diff -r 000000000000 -r be33ecaa3619 sokosold.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosold.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,445 @@ +#include +#include + +#define BOX '$' +#define WALL '#' +#define MAN '@' +#define PLATFORM '.' +#define BOXINPLATFORM '*' +#define MANINPLATFORM 'E' +#define BLANK ' ' +#define CANTO '-' +#define MANCANMOVE '+' + +#define NBOX(n) ((n)<<2) + +#define DIR_LEFT 0 +#define DIR_RIGHT 1 +#define DIR_UP 2 +#define DIR_DOWN 3 + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 50 +#define MAX_BOXES 15 + +#define MOVE_OK 1 +#define MOVE_BOX 2 +#define MOVE_ILLEGAL 0 + +/* SOKOBAN Solution Finder + * + * Cerca totes les possibilitats de tots els nombres de combinacions possibles, + * menys la que tots els moviments són a l'esquerra del número de combinacions + * incials triat. + + * 13/01/2002 + * Comentari afegit el 4/01/2003: + * Cerca la solució segons el moviment de caixes, i no el de l'home. + * Falta optimitzar: Llocs on no posar caixes segons les caixes (són dinàmics + * segons cada element de l'array de mapes!) + */ + + +struct Map +{ + char Cells[MAX_Y][MAX_X]; + char ManMoves[MAX_Y][MAX_X]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; + int BoxX[MAX_BOXES]; + int BoxY[MAX_BOXES]; + int NumBoxes; +}; + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY], MAX_X, Fitxer); + M->SizeY++; + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + M->NumBoxes = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { + M->ManX = i; M->ManY = j; + M->Cells[M->ManY][M->ManX] = BLANK; + } + + if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->Cells[j][i] = PLATFORM; + + M->NumPlatforms++; + M->NumBoxesInPlatform++; + + M->BoxX[M->NumBoxes] = i; + M->BoxY[M->NumBoxes] = j; + M->NumBoxes++; + } else if (M->Cells[j][i] == BOX) + { + M->Cells[j][i] = BLANK; + + M->BoxX[M->NumBoxes] = i; + M->BoxY[M->NumBoxes] = j; + M->NumBoxes++; + } else if (M->Cells[j][i] != WALL) + { + if ( (M->Cells[j][i-1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i-1] == WALL && + M->Cells[j+1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j+1][i] == WALL)) + M->Cells[j][i] = CANTO; + } + + } + +} + + +void ShowMap (struct Map *M) +{ + struct Map Temp; + int i,j; + + CopyMap(&Temp, M); + + Temp.Cells[Temp.ManY][Temp.ManX] = MAN; + + for (i = 0; i < Temp.NumBoxes; i++) + { + if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == BLANK) + Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX; + else if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM) + Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM; + } + + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK; + for (i = 0; iNumBoxes; i++) + M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL; + + NewMoves = 1; + NewX[0] = M->ManX; + NewY[0] = M->ManY; + while (NewMoves) + { + NumMoves = NewMoves; + for (i=0; iManMoves[Y[i]][X[i]-1] == BLANK) + { + NewX[NewMoves] = X[i]-1; + NewY[NewMoves] = Y[i]; + M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE; + NewMoves++; + } + else if(M->ManMoves[Y[i]][X[i]+1] == BLANK) + { + NewX[NewMoves] = X[i]+1; + NewY[NewMoves] = Y[i]; + M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE; + NewMoves++; + } + else if(M->ManMoves[Y[i]-1][X[i]] == BLANK) + { + NewX[NewMoves] = X[i]; + NewY[NewMoves] = Y[i]-1; + M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE; + NewMoves++; + } + else if(M->ManMoves[Y[i]+1][X[i]] == BLANK) + { + NewX[NewMoves] = X[i]; + NewY[NewMoves] = Y[i]+1; + M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE; + NewMoves++; + } + } + } +} + +int MoveBox(struct Map *M, int NumBox, int Direction) +{ + char InPlatform; + + InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM); + + switch(Direction) + { + case DIR_LEFT: + if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] == + MANCANMOVE) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxX[NumBox]--; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + case DIR_RIGHT: + if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] == + MANCANMOVE) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxX[NumBox]++; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + case DIR_UP: + if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] == + MANCANMOVE) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxY[NumBox]--; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + case DIR_DOWN: + if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] == + MANCANMOVE) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxY[NumBox]++; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return 1; + }else return 0; + break; + } + return 0; +} + + +int main(int argn, char **argv) +{ + struct Map Morigin; + struct Map M[MAX_MOVES+1]; + int Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + + int i; + + if (argn != 3) + { + printf("Usage: %s \n", argv[0]); + exit(3); + } + ReadMap(&Morigin, argv[1]); + sscanf(argv[2], "%i", &NumMoves); + + ShowMap(&Morigin); + + for (i = 0; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + CopyMap(&M[NumMoves], &Morigin); // For the first while cond. + + GetManMoves(&M[0]); + ShowMap(&Morigin); + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + { + IllegalMove = i; + break; + } + } + + // Main solution finder loop + while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform) + { + // Increase the Counter + { + Carry = 1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + Carry = 0; + if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1) + { Moves[i] = NBOX(0) + DIR_LEFT; Carry = 1; } + } + OldMaps = i+1; // Sure? I think it's i+1 + // If we change the number of movements for solution + if (Carry) + { + if (NumMoves > MAX_MOVES) + break; // MAX MOVES EXCEEDED!!! + NumMoves++; + for (i = 0; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + OldMaps=0; + CopyMap(&M[NumMoves], &Morigin); + // For the first while cond. + printf("Provant %i moviments...\n", NumMoves); + } + } + +/* + // Print the combination + + for (i=0; i < NumMoves; i++) + { + printf("%c", Moves[i]); + } + printf("\n"); +*/ + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = OldMaps; i < NumMoves - 1; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + { + IllegalMove = i; + break; + } /*else + if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) || + (Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) && + !M[i].BoxMoved) + { + IllegalMove = i; + break; + }*/ + GetManMoves(&M[i+1]); + + } + // Here i = NumMoves - 1 + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + IllegalMove = i; + + } + + // Print the combination + for (i=0; i < NumMoves; i++) + { + printf("%i", Moves[i] >> 2); + if ((Moves[i] & 0x03) == DIR_LEFT) + printf("L"); + else if ((Moves[i] & 0x03) == DIR_RIGHT) + printf("R"); + else if ((Moves[i] & 0x03) == DIR_UP) + printf("U"); + else + printf("D"); + printf(","); + } + printf("\n"); + +/* + // Print The Steps + for (i=0; i < NumMoves; i++) + { + ShowMap(&M[i]); + } +*/ + return 0; + +} diff -r 000000000000 -r be33ecaa3619 sokosold2.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sokosold2.c Fri May 05 22:40:45 2006 +0200 @@ -0,0 +1,543 @@ +#include +#include + +#define BOX '$' +#define WALL '#' +#define MAN '@' +#define PLATFORM '.' +#define BOXINPLATFORM '*' +#define MANINPLATFORM 'E' +#define BLANK ' ' +#define CANTO '-' +#define MANCANMOVE '+' + +#define NBOX(n) ((n)<<2) + +#define DIR_LEFT 0 +#define DIR_RIGHT 1 +#define DIR_UP 2 +#define DIR_DOWN 3 + +#define MAX_X 50 +#define MAX_Y 50 +#define MAX_MOVES 50 +#define MAX_MANMOVES 50 +#define MAX_BOXES 15 + +#define MOVE_OK 1 +#define MOVE_BOX 2 +#define MOVE_ILLEGAL 0 + +/* SOKOBAN Solution Finder + * + * Cerca totes les possibilitats de tots els nombres de combinacions possibles, + * menys la que tots els moviments són a l'esquerra del número de combinacions + * incials triat. + + * 13/01/2002 + * Comentari afegit el 4/01/2003: + * Cerca la solució segons el moviment de caixes, i no el de l'home. + * Falta optimitzar: Llocs on no posar caixes segons les caixes (són dinàmics + * segons cada element de l'array de mapes!) + * + * Diria que el programa no es deixa cap branca de l'arbre de backtracking + */ + + +struct Map +{ + char Cells[MAX_Y][MAX_X]; + char ManMoves[MAX_Y][MAX_X]; + int SizeX, SizeY; + int ManX, ManY; + int NumPlatforms; + int NumBoxesInPlatform; + int BoxX[MAX_BOXES]; + int BoxY[MAX_BOXES]; + int NumBoxes; +}; + + +void CopyMap (struct Map *Mdest, struct Map *Morig) +{ + memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); +} + + +void ReadMap(struct Map *M, char *FileName) +{ + FILE *Fitxer; + int i,j; + + if(!(Fitxer = fopen(FileName, "r"))) + { + printf("Error opening %s!", FileName); + exit(1); + } + + M->SizeX=0; + M->SizeY=0; + while (!feof(Fitxer)) + { + fgets(M->Cells[M->SizeY], MAX_X, Fitxer); + M->SizeY++; + } + M->SizeY--; + M->SizeX = strlen(M->Cells[0]) - 1; + + M->NumPlatforms = 0; + M->NumBoxesInPlatform = 0; + M->NumBoxes = 0; + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + { + if (M->Cells[j][i] == MAN) + { + M->ManX = i; M->ManY = j; + M->Cells[M->ManY][M->ManX] = BLANK; + } + + if (M->Cells[j][i] == PLATFORM) + M->NumPlatforms++; + else if (M->Cells[j][i] == BOXINPLATFORM) + { + M->Cells[j][i] = PLATFORM; + + M->NumPlatforms++; + M->NumBoxesInPlatform++; + + M->BoxX[M->NumBoxes] = i; + M->BoxY[M->NumBoxes] = j; + M->NumBoxes++; + } else if (M->Cells[j][i] == BOX) + { + M->Cells[j][i] = BLANK; + + M->BoxX[M->NumBoxes] = i; + M->BoxY[M->NumBoxes] = j; + M->NumBoxes++; + } else if (M->Cells[j][i] != WALL) + { + if ( (M->Cells[j][i-1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i-1] == WALL && + M->Cells[j+1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j-1][i] == WALL) || + (M->Cells[j][i+1] == WALL && + M->Cells[j+1][i] == WALL)) + M->Cells[j][i] = CANTO; + } + + } + + if(M->NumBoxes > M->NumPlatforms) + { + printf("More boxes than platforms!\n"); + exit(2); + } +} + + +void ShowMap (struct Map *M) +{ + struct Map Temp; + int i,j; + + CopyMap(&Temp, M); + + Temp.Cells[Temp.ManY][Temp.ManX] = MAN; + + for (i = 0; i < Temp.NumBoxes; i++) + { + if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == BLANK) + Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX; + else if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM) + Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM; + } + + for (j = 0; jSizeY; j++) + for (i=0; iSizeX; i++) + M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK; + for (i = 0; iNumBoxes; i++) + M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL; + + NewMoves = 1; + NewX[0] = M->ManX; + NewY[0] = M->ManY; + M->ManMoves[M->ManY][M->ManX] = MANCANMOVE; + while (NewMoves) + { + NumMoves = NewMoves; + for (i=0; iManMoves[Y[i]][X[i]-1] == BLANK) + { + NewX[NewMoves] = X[i]-1; + NewY[NewMoves] = Y[i]; + M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE; + NewMoves++; + } + if(M->ManMoves[Y[i]][X[i]+1] == BLANK) + { + NewX[NewMoves] = X[i]+1; + NewY[NewMoves] = Y[i]; + M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE; + NewMoves++; + } + if(M->ManMoves[Y[i]-1][X[i]] == BLANK) + { + NewX[NewMoves] = X[i]; + NewY[NewMoves] = Y[i]-1; + M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE; + NewMoves++; + } + if(M->ManMoves[Y[i]+1][X[i]] == BLANK) + { + NewX[NewMoves] = X[i]; + NewY[NewMoves] = Y[i]+1; + M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE; + NewMoves++; + } + } + } +} + + +/* Returns bool */ +char IsStupidPos(struct Map *M, int X, int Y) +{ + struct Map MTemp; + int NumBoxes, NumWalls, NumBoxesInPlatform; + int j, i; + + CopyMap(&MTemp, M); + + + for (i = 0; i= 1)) + return MOVE_ILLEGAL; + } + + return MOVE_OK; +} + + +int MoveBox(struct Map *M, int NumBox, int Direction) +{ + char InPlatform; + + InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM); + + switch(Direction) + { + case DIR_LEFT: + if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] == + MANCANMOVE && + (M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] + != WALL) && + (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]-1] + != CANTO) ) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxX[NumBox]--; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); + }else return 0; + break; + case DIR_RIGHT: + if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] == + MANCANMOVE && + (M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] + != WALL) && + (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]+1] + != CANTO) ) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxX[NumBox]++; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); + }else return 0; + break; + case DIR_UP: + if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] == + MANCANMOVE && + (M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] + != WALL) && + (M->Cells[M->BoxY[NumBox]-1][M->BoxX[NumBox]] + != CANTO) ) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxY[NumBox]--; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); + }else return 0; + break; + case DIR_DOWN: + if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] == + MANCANMOVE && + (M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] + != WALL) && + (M->Cells[M->BoxY[NumBox]+1][M->BoxX[NumBox]] + != CANTO) ) + { + if(InPlatform) + M->NumBoxesInPlatform--; + M->BoxY[NumBox]++; + if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == + PLATFORM) + M->NumBoxesInPlatform++; + return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]); + }else return 0; + break; + } + /* Check for stupid movement */ + return 0; +} + +void PrintCombination(int Moves[], int NumMoves) +{ + int i; + + for (i=0; i < NumMoves; i++) + { + printf("%i", Moves[i] >> 2); + if ((Moves[i] & 0x03) == DIR_LEFT) + printf("L"); + else if ((Moves[i] & 0x03) == DIR_RIGHT) + printf("R"); + else if ((Moves[i] & 0x03) == DIR_UP) + printf("U"); + else + printf("D"); + printf(","); + } + printf("\n"); +} + +int main(int argn, char **argv) +{ + struct Map Morigin; + struct Map M[MAX_MOVES+1]; + int Moves[MAX_MOVES]; + int NumMoves; + int OldMaps; + int IllegalMove; + int Carry; + + int i; + + if (argn != 3) + { + printf("Usage: %s \n", argv[0]); + exit(3); + } + ReadMap(&Morigin, argv[1]); + sscanf(argv[2], "%i", &NumMoves); + + //ShowMap(&Morigin); + + for (i = 0; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + + // Reget the original map + CopyMap(&M[0], &Morigin); + CopyMap(&M[NumMoves], &Morigin); // For the first while cond. + + GetManMoves(&M[0]); + ShowMap(&M[0]); + + IllegalMove = NumMoves - 1; + // Process the combination + for (i = 0; i < NumMoves; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + { + IllegalMove = i; + break; + } + } + + // Main solution finder loop + while (!(M[NumMoves].NumPlatforms == M[NumMoves].NumBoxesInPlatform && + IllegalMove == -1)) + { + // Increase the Counter + { + Carry = 1; + // If last combination was legal + if (IllegalMove == -1) + IllegalMove = NumMoves -1; + // Reset the direction of sure-invalid moves + for (i = IllegalMove + 1; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + // Increase Counter for a new try of moves + for (i = IllegalMove; i >= 0 && Carry; i--) + { + Moves[i]++; + Carry = 0; + if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1) + { Moves[i] = NBOX(0) + DIR_LEFT; Carry = 1; } + } + OldMaps = i+1; // Sure? I think it's i+1 + // If we change the number of movements for solution + if (Carry) + { + if (NumMoves > MAX_MOVES) + break; // MAX MOVES EXCEEDED!!! + NumMoves++; + for (i = 0; i < NumMoves; i++) + Moves[i] = NBOX(0) + DIR_LEFT; + OldMaps=0; + CopyMap(&M[NumMoves], &Morigin); + // For the first while cond. + printf("Provant %i moviments...\n", NumMoves); + fflush(stdout); + } + } + + + // First assume combination is legal + IllegalMove = -1; + // Process the combination + for (i = OldMaps; i < NumMoves - 1; i++) + { + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + { + IllegalMove = i; + break; + } /*else + if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) || + (Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) && + !M[i].BoxMoved) + { + IllegalMove = i; + break; + }*/ + // For next map: + GetManMoves(&M[i+1]); + + } + // Here i = NumMoves - 1 + CopyMap(&M[i+1], &M[i]); + if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03)) + IllegalMove = i; + //ShowMap(&M[i+1]); + + //printf("IM: %i\n", IllegalMove); + + } + + // Print the combination + PrintCombination(Moves, NumMoves); +/* + // Print The Steps + for (i=0; i < NumMoves; i++) + { + ShowMap(&M[i]); + } +*/ + return 0; + +}