Search Results

Search found 51 results on 3 pages for 'backtracking'.

facebook twitter digg google delicious technorati stumbleupon myspace wordpress linkedin gmail igoogle windows live tumblr viadeo yahoo buzz yahoo mail yahoo bookmarks favorites email print

Page 1/3 | 1 2 3  | Next Page >

  • Explain BFS and DFS in terms of backtracking

    - by HH
    Wikipedia about DFS Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. So is BFS? "an algorithm that choose a starting node, checks all nodes -- backtracks --, chooses the shortest path, chose neighbour nodes -- backtracks --, chose the shortest path -- finally finds the optimal path because of traversing each path due to continuos backtracking. Regex, find's pruning -- backtracking? The term backtracking confuseses due to its variety of use. UNIX find's pruning an SO-user explained with backtracking. Regex Buddy uses the term "catastrophic backtracking" if you do not limit the scope of your Regexes. It seems to be too wide umbrella-term. So: how do you define "Backtracking" GRAPH-theoretically? what is "backtracking" in BFS and DFS?

    Read the article

  • Backtracking Problem

    - by Joshua Green
    Could someone please guide me through backtracking in Prolog-C using the simple example below? Here is my Prolog file: likes( john, mary ). likes( john, emma ). likes( john, ashley ). Here is my C file: #include... term_t tx; term_t tv; term_t goal_term; functor_t goal_functor; int main( int argc, char** argv ) { argv[0] = "libpl.dll"; PL_initialise( argc, argv ); PlCall( "consult( swi( 'plwin.rc' ) )" ); PlCall( "consult( 'likes.pl' )" ); tv = PL_new_term_ref( ); PL_put_atom_chars( tv, "john" ); tx = PL_new_term_ref( ); goal_term = PL_new_term_ref( ); goal_functor = PL_new_functor( PL_new_atom( "likes" ), 2 ); PL_cons_functor( goal_term, goal_functor, tv, tx ); PlQuery q( "likes", ??? ); while ( q.next_solution( ) ) { char* solution; PL_get_atom_chars( tx, &solution ); cout << solution << endl; } PL_halt( PL_toplevel() ? 0 : 1 ); } What should I replace ??? with? Or is this the right approach to get all the backtracking results generated and printed? Thank you,

    Read the article

  • Stopping Backtracking

    - by John Retallack
    Is there any way in C/C++ to stop a backtracking algorithm after finding the first solution without exiting the program. I want my function to immediately exit the function,not to quit every level of recurrsion one by one stating return.

    Read the article

  • backtracking in haskell

    - by dmindreader
    I have to traverse a matrix and say how many "characteristic areas" of each type it has. A characteristic area is defined as a zone where elements of value n or n are adjacent. For example, given the matrix: 0 1 2 2 0 1 1 2 0 3 0 0 There's a single characteristic area of type 1 which is equal to the original matrix: 0 1 2 2 0 1 1 2 0 3 0 0 There are two characteristic areas of type 2: 0 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 3 0 0 And one characteristic area of type 3: 0 0 0 0 0 0 0 0 0 3 0 0 So, for the function call: countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]] The result should be [1,2,1] I haven't defined countAreas yet, I'm stuck with my visit function when it has no more possible squares in which to move it gets stuck and doesn't make the proper recursive call. I'm new to functional programming and I'm still scratching my head about how to implement a backtracking algorithm here. Take a look at my code, what can I do to change it? move_right :: (Int,Int) -> [[Int]] -> Int -> Bool move_right (i,j) mat cond | (j + 1) < number_of_columns mat && consult (i,j+1) mat /= cond = True | otherwise = False move_left :: (Int,Int) -> [[Int]] -> Int -> Bool move_left (i,j) mat cond | (j - 1) >= 0 && consult (i,j-1) mat /= cond = True | otherwise = False move_up :: (Int,Int) -> [[Int]] -> Int -> Bool move_up (i,j) mat cond | (i - 1) >= 0 && consult (i-1,j) mat /= cond = True | otherwise = False move_down :: (Int,Int) -> [[Int]] -> Int -> Bool move_down (i,j) mat cond | (i + 1) < number_of_rows mat && consult (i+1,j) mat /= cond = True | otherwise = False imp :: (Int,Int) -> Int imp (i,j) = i number_of_rows :: [[Int]] -> Int number_of_rows i = length i number_of_columns :: [[Int]] -> Int number_of_columns (x:xs) = length x consult :: (Int,Int) -> [[Int]] -> Int consult (i,j) l = (l !! i) !! j visited :: (Int,Int) -> [(Int,Int)] -> Bool visited x y = elem x y add :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)] add x y = x:y visit :: (Int,Int) -> [(Int,Int)] -> [[Int]] -> Int -> [(Int,Int)] visit (i,j) vis mat cond | move_right (i,j) mat cond && not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond | move_down (i,j) mat cond && not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond | move_left (i,j) mat cond && not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond | move_up (i,j) mat cond && not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond | otherwise = vis

    Read the article

  • Parsec: backtracking not working

    - by Nathan Sanders
    I am trying to parse F# type syntax. I started writing an [F]Parsec grammar and ran into problems, so I simplified the grammar down to this: type ::= identifier | type -> type identifier ::= [A-Za-z0-9.`]+ After running into problems with FParsec, I switched to Parsec, since I have a full chapter of a book dedicated to explaining it. My code for this grammar is typeP = choice [identP, arrowP] identP = do id <- many1 (digit <|> letter <|> char '.' <|> char '`') -- more complicated code here later return id arrowP = do domain <- typeP string "->" range <- typeP return $ "("++domain++" -> "++range++")" run = parse (do t <- typeP eof return t) "F# type syntax" The problem is that Parsec doesn't backtrack by default, so > run "int" Right "int" -- works! > run "int->int" Left "F# type syntax" unexpected "-" expecting digit, letter, ".", "`" or end of input -- doesn't work! The first thing I tried was to reorder typeP: typeP = choice [arrowP, identP] But this just stack overflows because the grammar is left-recursive--typeP never gets to trying identP because it keeps trying arrowP over and over. Next I tried try in various places, for example: typeP = choice [try identP, arrowP] But nothing I do seems to change the basic behaviours of (1) stack overflow or (2) non-recognition of "-" following an identifier. My mistake is probably obvious to anybody who has successfully written a Parsec grammar. Can somebody point it out?

    Read the article

  • Prolog Backtracking

    - by AhmadAssaf
    I am trying to do a word calculator .. read words from a file .. translate them into numbers and then calculate the result .. i managed to do all of that but i think i have two bugs in my program .. I mainly have two functions ... extract(Words), calculate( Words,0). extract will read from the file .. and then return a list of Words .. ex: [one,plus,three] .. now calculate will translate the value for these words into numbers and calculate .. i managed to do that also .. now the bugs are : i must stop reading and terminate if i encounter stop in the file .. so if Words was [stop] End. i tried the following ... execute :- extract(Words), Words = [stop],nl,print('Terminating ...'),!. execute :- extract(Words), calculate( Words,0). it successfully terminates .. but it skips lines as i extract more than once .. i have tried to do .. execute :- extract(Words), Words \= [stop],execute(Words). execute(Words) :- calculate( Words,0). if the Words is not stop .. then go and calculate .. but its not working !! i appreciate the help .. Thank You

    Read the article

  • Understanding Backtracking in C++

    - by nikhil
    I have a good basic understanding of the fundamentals of C++, I also have an understanding of how recursion works too. I came across certain problems like the classic eight queens problem and solving a Sudoku with Backtracking. I realize that I'm quite lost when it comes to this, I can't seem to be able to get my mind around the concept of going back in the recursion stack and starting again in order to solve the problem. It seems easy with a pen and paper but when it comes to writing code for this, I'm confused on how to begin attacking these problems. It would be helpful if there were a tutorial aimed at beginners to backtracking or if there were a good book where this was covered. If somebody can shed light on this topic or give me some links to decent references, I'd be really grateful. And yes I do know that it would be easier in functional languages but I'd like to understand the implementation in imperative languages too.

    Read the article

  • Trie Backtracking in Recursion

    - by Darksky
    I am building a tree for a spell checker with suggestions. Each node contains a key (a letter) and a value (array of letters down that path). So assume the following sub-trie in my big trie: W / \ a e | | k k | | is word--> e e | ... This is just a subpath of a sub-trie. W is a node and a and e are two nodes in its value array etc... At each node, I check if the next letter in the word is a value of the node. I am trying to support mistyped vowels for now. So 'weke' will yield 'wake' as a suggestion. Here's my searchWord function in my trie: def searchWord(self, word, path=""): if len(word) > 0: key = word[0] word = word[1:] if self.values.has_key(key): path = path + key nextNode = self.values[key] return nextNode.searchWord(word, path) else: # check here if key is a vowel. If it is, check for other vowel substitutes else: if self.isWord: return path # this is the word found else: return None Given 'weke', at the end when word is of length zero and path is 'weke', my code will hit the second big else block. weke is not marked as a word and so it will return with None. This will return out of searchWord with None. To avoid this, at each stack unwind or recursion backtrack, I need to check if a letter is a vowel and if it is, do the checking again. I changed the if self.values.has_key(key) loop to the following: if self.values.has_key(key): path = path + key nextNode = self.values[key] ret = nextNode.searchWord(word, path) if ret == None: # check if key == vowel and replace path # return nextNode.searchWord(... return ret What am I doing wrong here? What can I do when backtracking to achieve what I'm trying to do?

    Read the article

  • DFS Backtracking with java

    - by Cláudio Ribeiro
    I'm having problems with DFS backtracking in an adjacency matrix. Here's my code: (i added the test to the main in case someone wants to test it) public class Graph { private int numVertex; private int numEdges; private boolean[][] adj; public Graph(int numVertex, int numEdges) { this.numVertex = numVertex; this.numEdges = numEdges; this.adj = new boolean[numVertex][numVertex]; } public void addEdge(int start, int end){ adj[start-1][end-1] = true; adj[end-1][start-1] = true; } List<Integer> visited = new ArrayList<Integer>(); public Integer DFS(Graph G, int startVertex){ int i=0; if(pilha.isEmpty()) pilha.push(startVertex); for(i=1; i<G.numVertex; i++){ pilha.push(i); if(G.adj[i-1][startVertex-1] != false){ G.adj[i-1][startVertex-1] = false; G.adj[startVertex-1][i-1] = false; DFS(G,i); break; }else{ visited.add(pilha.pop()); } System.out.println("Stack: " + pilha); } return -1; } Stack<Integer> pilha = new Stack(); public static void main(String[] args) { Graph g = new Graph(6, 9); g.addEdge(1, 2); g.addEdge(1, 5); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(6, 4); g.DFS(g, 1); } } I'm trying to solve the euler path problem. the program solves basic graphs but when it needs to backtrack, it just does not do it. I think the problem might be in the stack manipulations or in the recursive dfs call. I've tried a lot of things, but still can't seem to figure out why it does not backtrack. Can somebody help me ?

    Read the article

  • Backtracking infinite loop

    - by Greenhorn
    This is Exercise 28.1.2 from HtDP. I've successfully implemented the neighbors function and all test cases pass. (define Graph (list (list 'A (list 'B 'E)) (list 'B (list 'E 'F)) (list 'C (list 'D)) (list 'D empty) (list 'E (list 'C 'F)) (list 'F (list 'D 'G)) (list 'G empty))) (define (first-line n alist) (cond [(symbol=? (first alist) n) alist] [else empty])) ;; returns empty if node is not in graph (define (neighbors n g) (cond [(empty? g) empty] [(cons? (first g)) (cond [(symbol=? (first (first g)) n) (first-line n (first g))] [else (neighbors n (rest g))])])) ; test cases (equal? (neighbors 'A Graph) (list 'A (list 'B 'E))) (equal? (neighbors 'B Graph) (list 'B (list 'E 'F))) (equal? (neighbors 'C Graph) (list 'C (list 'D))) (equal? (neighbors 'D Graph) (list 'D empty)) (equal? (neighbors 'E Graph) (list 'E (list 'C 'F))) (equal? (neighbors 'F Graph) (list 'F (list 'D 'G))) (equal? (neighbors 'G Graph) (list 'G empty)) (equal? (neighbors 'H Graph) empty) The problem comes when I copy-paste the code from Figure 77 of the text. It is supposed to determine whether a destination node is reachable from an origin node. However it appears that the code goes into an infinite loop except for the most trivial case where the origin and destination nodes are the same. ;; find-route : node node graph -> (listof node) or false ;; to create a path from origination to destination in G ;; if there is no path, the function produces false (define (find-route origination destination G) (cond [(symbol=? origination destination) (list destination)] [else (local ((define possible-route (find-route/list (neighbors origination G) destination G))) (cond [(boolean? possible-route) false] [else (cons origination possible-route)]))])) ;; find-route/list : (listof node) node graph -> (listof node) or false ;; to create a path from some node on lo-Os to D ;; if there is no path, the function produces false (define (find-route/list lo-Os D G) (cond [(empty? lo-Os) false] [else (local ((define possible-route (find-route (first lo-Os) D G))) (cond [(boolean? possible-route) (find-route/list (rest lo-Os) D G)] [else possible-route]))])) Does the problem lie in my code? Thank you.

    Read the article

  • Can someone describe through code a practical example of backtracking with iteration instead of recursion?

    - by chrisapotek
    Recursion makes backtracking easy as it guarantees that you won't go through the same path again. So all ramifications of your path are visited just once. I am trying to convert a backtracking tail-recursive (with accumulators) algorithm to iteration. I heard it is supposed to be easy to convert a perfectly tail-recursive algorithm to iteration. But I am stuck in the backtracking part. Can anyone provide a example through code so myself and others can visualize how backtracking is done? I would think that a STACK is not needed here because I have a perfectly tail-recursive algorithm using accumulators, but I can be wrong here.

    Read the article

  • Comparison of algorithmic approaches to the N queens problem

    - by iceman
    I wanted to evaluate performance comparisons for various approaches to solving the N queens problem. Mainly AI metaheuristics based algorithms like simulated annealing, tabu search and genetic algorithm etc compared to exact methods(like backtracking). Is there any code available for study? A lot of real-world optimization problems like it consider cooperative schemes between exact methods and metaheuristics.

    Read the article

  • Algorithm complexity question

    - by Itsik
    During a recent job interview, I was asked to give a solution to the following problem: Given a string s (without spaces) and a dictionary, return the words in the dictionary that compose the string. For example, s= peachpie, dic= {peach, pie}, result={peach, pie}. I will ask the the decision variation of this problem: if s can be composed of words in the dictionary return yes, otherwise return no. My solution to this was in backtracking (written in Java) public static boolean words(String s, Set<String> dictionary) { if ("".equals(s)) return true; for (int i=0; i <= s.length(); i++) { String pre = prefix(s,i); // returns s[0..i-1] String suf = suffix(s,i); // returns s[i..s.len] if (dictionary.contains(pre) && words(suf, dictionary)) return true; } return false; } public static void main(String[] args) { Set<String> dic = new HashSet<String>(); dic.add("peach"); dic.add("pie"); dic.add("1"); System.out.println(words("peachpie1", dic)); // true System.out.println(words("peachpie2", dic)); // false } What is the time complexity of this solution? I'm calling recursively in the for loop, but only for the prefix's that are in the dictionary. Any idea's?

    Read the article

  • algorithm to find longest non-overlapping sequences

    - by msalvadores
    I am trying to find the best way to solve the following problem. By best way I mean less complex. As an input a list of tuples (start,length) such: [(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)] Each element represets a sequence by its start and length, for example (5,7) is equivalent to the sequence (5,6,7,8,9,10,11) - a list of 7 elements starting with 5. One can assume that the tuples are sorted by the start element. The output should return a non-overlapping combination of tuples that represent the longest continuos sequences(s). This means that, a solution is a subset of ranges with no overlaps and no gaps and is the longest possible - there could be more than one though. For example for the given input the solution is: [(0,5),(5,7)] equivalent to (0,1,2,3,4,5,6,7,8,9,10,11) is it backtracking the best approach to solve this problem ? I'm interested in any different approaches that people could suggest. Also if anyone knows a formal reference of this problem or another one that is similar I'd like to get references. BTW - this is not homework. Edit Just to avoid some mistakes this is another example of expected behaviour for an input like [(0,1),(1,7),(3,20),(8,5)] the right answer is [(3,20)] equivalent to (3,4,5,..,22) with length 20. Some of the answers received would give [(0,1),(1,7),(8,5)] equivalent to (0,1,2,...,11,12) as right answer. But this last answer is not correct because is shorter than [(3,20)].

    Read the article

  • Maze not being random.

    - by Matt Habel
    Hey there, I am building a program that generates a maze so I can later translate the path to my graphical part. I have most of it working, however, every time you can just take the east and south routes, and you'll get to the end. Even if I set the width as high as 64, so the maze is 64*64, I'm able to choose those 2 options and get to the end every time. I really don't understand why it is doing that. The code is below, it's fairly easy to understand. import random width = 8 def check(x,y): """Figures out the directions that Gen can move while""" if x-1 == -1: maze[x][y][3] = 0 if x+1 == width + 1: maze[x][y][1] = 0 if y+1 == width + 1: maze[x][y][2] = 0 if y-1 == -1: maze[x][y][0] = 0 if x + 1 in range(0,width) and visited[x+1][y] == False: maze[x][y][1] = 2 if x - 1 in range(0,width) and visited[x-1][y] == False: maze[x][y][3] = 2 if y + 1 in range(0,width) and visited[x][y+1] == False: maze[x][y][2] = 2 if y - 1 in range(0,width) and visited[x][y-1] == False: maze[x][y][0] = 2 def possibleDirs(x,y): """Figures out the ways that the person can move in each square""" dirs = [] walls = maze[x][y] if walls[0] == 1: dirs.append('n') if walls[1] == 1: dirs.append('e') if walls[2] == 1: dirs.append('s') if walls[3] == 1: dirs.append('w') return dirs def Gen(x,y): """Generates the maze using a depth-first search and recursive backtracking.""" visited[x][y] = True dirs = [] check(x,y) if maze[x][y][0] == 2: dirs.append(0) if maze[x][y][1] == 2: dirs.append(1) if maze[x][y][2] == 2: dirs.append(2) if maze[x][y][3] == 2: dirs.append(3) print dirs if len(dirs): #Randonly selects a derection for the current square to move past.append(current[:]) pos = random.choice(dirs) maze[x][y][pos] = 1 if pos == 0: current[1] -= 1 maze[x][y-1][2] = 1 if pos == 1: current[0] += 1 maze[x+1][y][3] = 1 if pos == 2: current[1] += 1 maze[x][y+1][0] = 1 if pos == 3: current[0] -= 1 maze[x-1][y][1] = 1 else: #If there's nowhere to go, go back one square lastPlace = past.pop() current[0] = lastPlace[0] current[1] = lastPlace[1] #Build the initial values for the maze to be replaced later maze = [] visited = [] past = [] #Generate empty 2d list with a value for each of the xy coordinates for i in range(0,width): maze.append([]) for q in range(0, width): maze[i].append([]) for n in range(0, 4): maze[i][q].append(4) #Makes a list of falses for all the non visited places for x in range(0, width): visited.append([]) for y in range(0, width): visited[x].append(False) dirs = [] print dirs current = [0,0] #Generates the maze so every single square has been filled. I'm not sure how this works, as it is possible to only go south and east to get to the final position. while current != [width-1, width-1]: Gen(current[0], current[1]) #Getting the ways the person can move in each square for i in range(0,width): dirs.append([]) for n in range(0,width): dirs[i].append([]) dirs[i][n] = possibleDirs(i,n) print dirs print visited pos = [0,0] #The user input part of the maze while pos != [width - 1, width - 1]: dirs = [] print pos if maze[pos[0]][pos[1]][0] == 1: dirs.append('n') if maze[pos[0]][pos[1]][1] == 1: dirs.append('e') if maze[pos[0]][pos[1]][2] == 1: dirs.append('s') if maze[pos[0]][pos[1]][3] == 1: dirs.append('w') print dirs path = raw_input("What direction do you want to go: ") if path not in dirs: print "You can't go that way!" continue elif path.lower() == 'n': pos[1] -= 1 elif path.lower() == 'e': pos[0] += 1 elif path.lower() == 's': pos[1] += 1 elif path.lower() == 'w': pos[0] -= 1 print"Good job!" As you can see, I think the problem is at the point where I generate the maze, however, when I just have it go until the current point is at the end, it doesn't fill every maze and is usually just one straight path. Thanks for helping. Update: I have changed the for loop that generates the maze to a simple while loop and it seems to work much better. It seems that when the for loop ran, it didn't go recursively, however, in the while loop it's perfectly fine. However, now all the squares do not fill out.

    Read the article

  • How to Solve N-Queens Problem in Scheme?

    - by Philip
    Hi, I'm stuck on the extended exercise 28.2 of How to Design Programs. Here is the link to the question: http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-35.html#node_chap_28 I used a vector of true or false values to represent the board instead of using a list. This is what I've got which doesn't work: #lang Scheme (define-struct posn (i j)) ;takes in a position in i, j form and a board and returns a natural number that represents the position in index form ;example for board xxx ; xxx ; xxx ;(0, 1) - 1 ;(2, 1) - 7 (define (board-ref a-posn a-board) (+ (* (sqrt (vector-length a-board)) (posn-i a-posn)) (posn-j a-posn))) ;reverse of the above function ;1 - (0, 1) ;7 - (2, 1) (define (get-posn n a-board) (local ((define board-length (sqrt (vector-length a-board)))) (make-posn (floor (/ n board-length)) (remainder n board-length)))) ;determines if posn1 threatens posn2 ;true if they are on the same row/column/diagonal (define (threatened? posn1 posn2) (cond ((= (posn-i posn1) (posn-i posn2)) #t) ((= (posn-j posn1) (posn-j posn2)) #t) ((= (abs (- (posn-i posn1) (posn-i posn2))) (abs (- (posn-j posn1) (posn-j posn2)))) #t) (else #f))) ;returns a list of positions that are not threatened or occupied by queens ;basically any position with the value true (define (get-available-posn a-board) (local ((define (get-ava index) (cond ((= index (vector-length a-board)) '()) ((vector-ref a-board index) (cons index (get-ava (add1 index)))) (else (get-ava (add1 index)))))) (get-ava 0))) ;consume a position in the form of a natural number and a board ;returns a board after placing a queen on the position of the board (define (place n a-board) (local ((define (foo x) (cond ((not (board-ref (get-posn x a-board) a-board)) #f) ((threatened? (get-posn x a-board) (get-posn n a-board)) #f) (else #t)))) (build-vector (vector-length a-board) foo))) ;consume a list of positions in the form of natural number and consumes a board ;returns a list of boards after placing queens on each of the positions on the board (define (place/list alop a-board) (cond ((empty? alop) '()) (else (cons (place (first alop) a-board) (place/list (rest alop) a-board))))) ;returns a possible board after placing n queens on a-board ;returns false if impossible (define (placement n a-board) (cond ((zero? n) a-board) (else (local ((define available-posn (get-available-posn a-board))) (cond ((empty? available-posn) #f) (else (or (placement (sub1 n) (place (first available-posn) a-board)) (placement/list (sub1 n) (place/list (rest available-posn) a-board))))))))) ;returns a possible board after placing n queens on a list of boards ;returns false if all the boards are not valid (define (placement/list n boards) (cond ((empty? boards) #f) ((zero? n) (first boards)) ((not (boolean? (placement n (first boards)))) (first boards)) (else (placement/list n (rest boards)))))

    Read the article

  • How can I return default at loop end in Scheme?

    - by Kufi Annan
    I'm trying to implement back-tracking search in Scheme. So far, I have the following: (define (backtrack n graph assignment) (cond (assignment-complete n assignment) (assignment) ) (define u (select-u graph assignment)) (define c 1) (define result 0) (let forLoop () (when (valid-choice graph assignment c) (hash-set! assignment u c) (set! result (backtrack n graph assignment)) (cond ((not (eq? result #f)) result)) (hash-remove! assignment u) ) (set! c (+ c 1)) (when (>= n c) (forLoop)) ) #f ) My functions assignment-complete and select-u pass unit tests. The argument assignment is a hash-table make with (make-hash), so it should be fine. I believe the problem I have is related to returning false at the end of the loop, if no recursive returns a non-false value (which should be a valid assignment).

    Read the article

  • Recursion Problems in Prolog

    - by Humble_Student
    I'm having some difficulties in prolog, I'm trying to write a predicate that will return all paths between two cities, although at the moment it returns the first path it finds on an infinite loop. Not sure where I'm going wrong but I've been trying to figure this out all day and I'm getting nowhere. Any help that could be offered would be appreciated. go:- repeat, f([],0,lon,spa,OP,OD), write(OP), write(OD), fail. city(lon). city(ath). city(spa). city(kol). path(lon,1,ath). path(ath,3,spa). path(spa,2,kol). path(lon,1,kol). joined(X,Y,D):- path(X,D,Y);path(Y,D,X). f(Ci_Vi,Di,De,De,PaO,Di):- append([De],Ci_Vi,PaO), !. f(Cities_Visited,Distance,Start,Destination,Output_Path,Output_Distance):- repeat, city(X), joined(Start,X,D), not_member(X,Cities_Visited), New_Distance is Distance + D, f([Start|Cities_Visited],New_Distance,X,Destination,Output_Path,Output_Distance). not_member(X,List):- member(X,List), !, fail. not_member(X,List). The output I'm expecting here is [spa,ath,lon]4 [spa,kol,lon]3. Once again, any help would be appreciated. Many thanks in advance.

    Read the article

  • Is there any algorithm that can solve ANY traditional sudoku puzzles, WITHOUT guessing (or similar techniques)?

    - by justin
    Is there any algorithm that solves ANY traditional sudoku puzzle, WITHOUT guessing? Here Guessing means trying an candidate and see how far it goes, if a contradiction is found with the guess, backtracking to the guessing step and try another candidate; when all candidates are exhausted without success, backtracking to the previous guessing step (if there is one; otherwise the puzzle proofs invalid.), etc. EDIT1: Thank you for your replies. traditional sudoku means 81-box sudoku, without any other constraints. Let us say the we know the solution is unique, is there any algorithm that can GUARANTEE to solve it without backtracking? Backtracking is a universal tool, I have nothing wrong with it but, using a universal tool to solve sudoku decreases the value and fun in deciphering (manually, or by computer) sudoku puzzles. How can a human being solve the so called "the hardest sudoku in the world", does he need to guess? I heard some researcher accidentally found that their algorithm for some data analysis can solve all sudoku. Is that true, do they have to guess too?

    Read the article

  • Ubuntu 12.10 Wine Crash Error Help

    - by Hao
    I'm trying to get wine to work for Hawken. I used winetricks and installed all the necessary components. Wine works fine with other games I have installed but when I try to run Hawken it crashes while loading with the following error: fixme:iphlpapi:CancelIPChangeNotify (overlapped 0xf2afb8): stub I'm new to Ubuntu so I have no idea how to fix this. Any help would be much appreciated. *Update: I've done some backtracking and it seems that this error is caused by the launcher not wine itself.

    Read the article

  • Parsing Lisp S-Expressions with known schema in C#

    - by Drew Noakes
    I'm working with a service that provides data as a Lisp-like S-Expression string. This data is arriving thick and fast, and I want to churn through it as quickly as possible, ideally directly on the byte stream (it's only single-byte characters) without any backtracking. These strings can be quite lengthy and I don't want the GC churn of allocating a string for the whole message. My current implementation uses CoCo/R with a grammar, but it has a few problems. Due to the backtracking, it assigns the whole stream to a string. It's also a bit fiddly for users of my code to change if they have to. I'd rather have a pure C# solution. CoCo/R also does not allow for the reuse of parser/scanner objects, so I have to recreate them for each message. Conceptually the data stream can be thought of as a sequence of S-Expressions: (item 1 apple)(item 2 banana)(item 3 chainsaw) Parsing this sequence would create three objects. The type of each object can be determined by the first value in the list, in the above case "item". The schema/grammar of the incoming stream is well known. Before I start coding I'd like to know if there are libraries out there that do this already. I'm sure I'm not the first person to have this problem.

    Read the article

  • Project Euler 15: (Iron)Python

    - by Ben Griswold
    In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 15.  As always, any feedback is welcome. # Euler 15 # http://projecteuler.net/index.php?section=problems&id=15 # Starting in the top left corner of a 2x2 grid, there # are 6 routes (without backtracking) to the bottom right # corner. How many routes are their in a 20x20 grid? import time start = time.time() def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) rows, cols = 20, 20 print factorial(rows+cols) / (factorial(rows) * factorial(cols)) print "Elapsed Time:", (time.time() - start) * 1000, "millisecs" a=raw_input('Press return to continue')

    Read the article

facebook twitter digg google delicious technorati stumbleupon myspace wordpress linkedin gmail igoogle windows live tumblr viadeo yahoo buzz yahoo mail yahoo bookmarks favorites email print

1 2 3  | Next Page >