--- /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

--- /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 @@
+########
+##   ###
+# $# ###
+# . @###
+# *   ##
+## #$ ##
+##.  ###
+########

--- /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 @@
+#######
+###  ##
+###$ ##
+#  * @#
+#  *  #
+#  * ##
+###* ##
+###.###
+#######

--- /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,

--- /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 @@
+######
+#  . #
+#@# *#
+#  $ #
+# #* #
+#    #
+######

--- /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 @@
+#######
+#   @ #
+### # #
+#   $ #
+### # #
+#.    #
+#######

--- /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+ + #
+#  ** ##
+### #+##
+###   ##
+########

--- /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 @@
+######
+###. #
+##   #
+# $  #
+#  @ #
+###  #
+######

--- /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

--- /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 @@
+   ########
+####--#
+#-    ####
+#-$ #  . ##
+#- #   .  #
+## #$$#.  #
+##   @#####
+#-  ###
+#---#
+#####

--- /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 @@
+     #####
+    ## . #
+   ## $. #
+  ## $   #
+ ## $@ ###
+## $  ##
+##.. ##
+##   #
+######

--- /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 @@
+###############
+#..   #     ###
+#..   # $  $  #
+#..   #$####  #
+#..     @ ##  #
+#..   # #  $ ##
+####### ##$ $ #
+### $   $ $ $ #
+###     #     #
+###############

--- /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 @@
+######  ####
+#..  # ## ##
+#..  ###@  #
+#..     $$ #
+#..  # # $ #
+#..### # $ #
+#### $ #$  #
+   #  $# $ #
+   # $  $  #
+   #  ##   #
+   #########

--- /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 @@
+     ####
+ #####--#
+ #-$ $ -#
+ #.# #.-#
+ # $@$ ##
+##.# #.##
+#- * * -#
+#---#---#
+#########

--- /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 @@
+ ######
+##  ###
+#     #
+#.**$@#
+#   ###
+##  #
+ ####

--- /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 @@
+#### ####
+#  ###  #
+# $ * $ #
+#   @   #
+### .$###
+  # . #
+  #####

--- /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 @@
+##########
+####### .#
+# $ $ $$ #
+#   @ ...#
+### - ####
+  #####

--- /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 @@
+###############
+#..   #     ###
+#..   # $  $  #
+#..   #$####  #
+#..     @ ##  #
+#..   # #  $ ##
+####### ##$ $ #
+### $   $ $ $ #
+###     #     #
+###############

--- /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,

--- /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 @@
+     #####
+    ## . #
+   ## $.-#
+  ## $   #
+ ## $@ ###
+## $  ##
+##.. ##
+## - #
+######

--- /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 @@
+########
+###  * #
+## * # #
+## + $ #
+##  # ##
+###   ##
+########
+########

--- /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 @@
+########
+##   ###
+# $# ###
+# . @###
+# *   ##
+## #$ ##
+##.  ###
+########

--- /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,

--- /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 @@
+########
+########
+##  ####
+#..$  .#
+# #$ $ #
+#@  #  #
+#####  #
+########

--- /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,

--- /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 @@
+########
+##  .@##
+##   $.#
+####*# #
+##     #
+#  $  ##
+#   ####
+########

--- /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...

--- /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 @@
+########
+##@ ####
+##  ####
+##. ####
+# $$. .#
+#  $ ###
+###  ###
+########

--- /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 @@
+########
+##@ ####
+##  ####
+##.$####
+# $ . ##
+#    ###
+###  ###
+########

--- /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 @@
+########
+########
+##.  ###
+## # ###
+## *$  #
+##  $. #
+##  @###
+########

--- /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 @@
+########
+########
+###   ##
+### #.##
+###  .##
+#@ $$ ##
+#  .$ ##
+########

--- /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 @@
+########
+#   @###
+# $# ###
+# * $  #
+#   ## #
+##.  . #
+###   ##
+########

--- /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 @@
+########
+##   @##
+##  #  #
+##.  $ #
+## $$#.#
+####  .#
+########
+########

--- /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 @@
+########
+########
+###. ###
+# .  ###
+#   $$ #
+## . $@#
+########
+########

--- /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 @@
+########
+#####  #
+#####$.#
+###  . #
+###  #.#
+# $  $ #
+#   #@ #
+########

--- /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 @@
+########
+###  ###
+###  ###
+### .. #
+#  $# -#
+#  .$$-#
+####@- #
+########

--- /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"

--- /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 @@
+#######
+#     #
+#   . #
+# @   #
+#   $ #
+#     #
+#######

--- /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 @@
+#########
+## ## . #
+# ## $. #
+ ## $   #
+## $@ ###
+# $  ##
+#.. ##
+#   #
+#####

--- /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 <stdio.h>
+#include <string.h>
+
+#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; j<M->SizeY; j++)
+		for (i=0; i<M->SizeX; 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; j<TempMap.SizeY; j++)
+	{
+		for (i=0; i<TempMap.SizeX; i++)
+			printf("%c", TempMap.Cells[j][i]);
+		printf("\n");
+	}
+	printf("Man is at (%i,%i)\n", TempMap.ManX, TempMap.ManY);
+	printf("Platforms: %i, BoxesInPlatform: %i\n", TempMap.NumPlatforms,
+			TempMap.NumBoxesInPlatform);
+}
+
+
+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()
+{
+	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;
+*/
+
+}

--- /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 <stdio.h>
+#include <string.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <signal.h>
+
+#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; j<M->SizeY; j++)
+		for (i=0; i<M->SizeX; 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<Temp.SizeY; j++)
+	{
+		for (i=0; i<Temp.SizeX; i++)
+			fprintf(stderr,"%c", Temp.Cells[j][i]);
+		fprintf(stderr,"\n");
+	}
+
+#if 0
+	// Print Where the man can move
+	for (j = 0; j<Temp.SizeY; j++)
+	{
+		for (i=0; i<Temp.SizeX; i++)
+			printf("%c", Temp.ManMoves[j][i]);
+		printf("\n");
+	}
+#endif
+
+	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);
+	printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,
+			Temp.NumBoxesInPlatform);
+
+}
+
+
+
+int InverseMove(char Dir1, char Dir2)
+{
+	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
+		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))
+		return 1;
+	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");
+}
+
+#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; j<m->SizeY; j++)
+		for (i=0; i<m->SizeX; i++)
+			corners[j][i] = m->Cells[j][i];
+
+	/* Let's put the boxes */
+	for (i = 0; i<m->NumBoxes; 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; i<NewMoves; i++)
+		{
+			pos[i] = new_pos[i];
+		}
+
+		/* Search new positions for each position */
+		NewMoves = 0;
+		for (i=0; i<NumMoves; i++)
+		{
+			/* For each direction */
+			for (j=0; j<4; j++)
+			{
+				next_pos.x = pos[i].x + move_vectors[j].x;
+				next_pos.y = pos[i].y + move_vectors[j].y;
+				next_cell = &corners[next_pos.y][next_pos.x];
+				if(*next_cell == BLANK ||
+					*next_cell == PLATFORM)
+				{
+					return FALSE;
+				}
+				else if(*next_cell == CORNER)
+				{
+					new_pos[NewMoves] = next_pos;
+					*next_cell = MANCANMOVE;
+					NewMoves++;
+				}
+			}
+		}
+	}
+
+	return TRUE;
+}
+
+int does_box_close_corners(const struct Map * m, const struct Position mov,
+	const struct Position box_pos)
+{
+	struct Position p, p2;
+
+	p.x = box_pos.x + mov.x;
+	p.y = box_pos.y + mov.y;
+	
+	/* Let's plan the checks */
+	/* The point will be marked with a MANCANMOVE */
+	p2.x = p.x + mov.x;
+	p2.y = p.y + mov.y;
+	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;
+	}
+
+	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; j<m->SizeY; j++)
+		for (i=0; i<m->SizeX; 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; i<m->NumBoxes; 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; i<NewMoves; i++)
+		{
+			pos[i] = new_pos[i];
+		}
+
+		/* Search new positions for each position */
+		NewMoves = 0;
+		for (i=0; i<NumMoves; i++)
+		{
+			/* For each direction */
+			for (j=0; j<4; j++)
+			{
+				next_pos.x = pos[i].x + move_vectors[j].x;
+				next_pos.y = pos[i].y + move_vectors[j].y;
+				next_cell = &m->man_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; i<max_depth; i++)
+	{
+		/* No l'hem de comparar amb ell mateix */
+		if (i == depth)
+			continue;
+
+		if (m->NumBoxesInPlatform != 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 <mapfile>\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;
+
+}

--- /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 <stdio.h>
+#include <string.h>
+
+#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; j<M->SizeY; j++)
+		for (i=0; i<M->SizeX; 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; j<M->SizeY; j++)
+	{
+		for (i=0; i<M->SizeX; 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 <mapfile> <initial NumMoves>\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);
+	}
+*/
+
+}

--- /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 <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#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; j<M->SizeY; j++)
+		for (i=0; i<M->SizeX; 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; j<M->SizeY; j++)
+	{
+		for (i=0; i<M->SizeX; 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);
+	}
+*/
+
+}

--- /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 <stdio.h>
+#include <string.h>
+
+#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; j<M->SizeY; j++)
+		for (i=0; i<M->SizeX; 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; j<M->SizeY; j++)
+	{
+		for (i=0; i<M->SizeX; 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;
+
+}