Commits

Vincent L committed b536da0

new version with fixed point

  • Participants
  • Parent commits c159c6e

Comments (0)

Files changed (1)

File src/knights.cc

 #include <iostream>
 #include "bddLib/bdd.hh"
 #include <list>
+#include <stdio.h>
 
 int N = 5;
 Bdd::Bdd** cell; // pre-state board.
     {
         int x;
         int y;
+        bool** passed;
     }       Coord;
 
+    bool**
+    mcopy(bool** t)
+    {
+        bool** ret = new bool*[N];;
+        for (int i = 0; i < N; ++i)
+            memcpy(ret[i], t[i], N * sizeof (bool));
+
+        return ret;
+    }
+
+    bool passedEverywhere(bool** t)
+    {
+        for (int x = 0; x < N; ++x)
+            for (int y = 0; y < N; ++y)
+                if (!t[x][y])
+                    return false;
+        return true;
+    }
+
     // We only want cells inside the board.
     bool
     isNotOnBoard(Coord& value)
     {
         return value.x < 0 || value.x >= N
-            || value.y < 0 || value.y >= N;
+            || value.y < 0 || value.y >= N
+            || value.passed[value.x][value.y];
     }
 
     // We get the next moves of our knight for a Coord (x, y)
     nextMoves(Coord& c)
     {
         std::list<Coord> moves =
-           {{c.x + 2, c.y + 1},
-            {c.x - 2, c.y + 1},
-            {c.x + 2, c.y - 1},
-            {c.x - 2, c.y - 1},
-            {c.x + 1, c.y + 2},
-            {c.x - 1, c.y + 2},
-            {c.x + 1, c.y - 2},
-            {c.x - 1, c.y - 2}};
+           {{c.x + 2, c.y + 1, mcopy(c.passed)},
+            {c.x - 2, c.y + 1, mcopy(c.passed)},
+            {c.x + 2, c.y - 1, mcopy(c.passed)},
+            {c.x - 2, c.y - 1, mcopy(c.passed)},
+            {c.x + 1, c.y + 2, mcopy(c.passed)},
+            {c.x - 1, c.y + 2, mcopy(c.passed)},
+            {c.x + 1, c.y - 2, mcopy(c.passed)},
+            {c.x - 1, c.y - 2, mcopy(c.passed)}};
         moves.remove_if(isNotOnBoard);
 
         return moves;
     }
 
     Bdd::Bdd
-    move(Coord& s, Coord& d)
+    move(Coord& d)
     {
         Bdd::Bdd v1 = cell[d.x][d.y]; // destination
-        Bdd::Bdd v2 = cell[s.x][s.y]; // source
 
-        return v2 && !v1;
+        return v1;
     }
 
     Bdd::Bdd
         Bdd::Bdd ret = Bdd::getFalseBdd();
 
         for (Coord d : moves)
-            ret = ret || move(s, d);
+            ret = ret || move(d);
 
         return ret;
     }
 
     Bdd::Bdd
-    tour(int size, Coord& s, Bdd::Bdd path)
+    tour(Coord& s, Bdd::Bdd path)
     {
-        if (size == 0 || size == 1)
+        if (passedEverywhere(s.passed))
             return Bdd::getTrueBdd();
 
+        s.passed[s.x][s.y] = true;
+
         std::list<Coord> moves = nextMoves(s);
 
         path = path && transition(s);
         for (Coord d : moves)
-            path = path && tour(size - 1, d, path);
+            path = path && tour(d, path);
 
         return path;
     }
 int main(int argc, char** argv)
 {
     std::cout << "Knight's Tour" << std::endl;
+    bool** ptrs;
 
     if (argc < 2)
     {
     for (int line = 0; line < N; ++line)
         cell[line] = new Bdd::Bdd[N];
 
+    ptrs = new bool*[N];
+    for (int line = 0; line < N; ++line)
+        ptrs[line] = new bool[N];
+
     int i = -1;
     for (int x = 0; x < N; ++x)
         for (int y = 0; y < N; ++y)
+        {
             cell[x][y] = Bdd::bdd_ithvar(++i);
+            ptrs[x][y] = false;
+        }
 
-    Coord c = {0, 0};
-    Bdd::Bdd ret = tour(N, c, Bdd::getTrueBdd());
+    Coord c = {0, 0, ptrs};
+    Bdd::Bdd ret = tour(c, Bdd::getTrueBdd());
 
     // Print the results
     ret.print();