Questions tagged [backtracking]
Backtracking is a general algorithm for finding solutions to some computational problem, that incrementally builds candidates to the solutions, and rejects continued processing of tracks that would lead to impossible solutions.
7
questions with no upvoted or accepted answers
5
votes
1answer
68 views
Farmer, Wolf, Goat and Cabbage Problem: full decision tree in C
I put a backtracking algorithm around the Farmer, Wolf, Goat and Cabbage problem - to see if there are any interesting branches, besides the (two) 7-step solutions.
WGC Problem: A Farmer with a wolf, ...
5
votes
0answers
429 views
Backtracking solver for n queens problem and knight's tour
Playing with https://ocaml.org/learn/tutorials/99problems.html#Miscellaneous-Problems I wrote a backtracking solver for the n queens problem, then the knight's tour, and realised I could generalise ...
4
votes
0answers
977 views
Magic square and backtracking
I have to write a program that solves a NxN Magic Square, with digits from 1 to N2.
What do you think?
...
3
votes
0answers
84 views
Putting as many ships on a square board as possible
Github repository
Origanally I wrote a program that let you play battleship against the computer.
Pretty easy:
create a number of ships
generate random cells for all the ships
let the user try to ...
3
votes
0answers
133 views
N-Queens Puzzle
The N-Queens puzzle can be solved in many ways. One is by a depth-first-search backtracking algorithm.
Below is my generalized version using mutual recursion:
...
1
vote
0answers
21 views
1
vote
0answers
98 views
Ruby Sudoku Solver without classes
I'm writing a Sudoku solver in Ruby to complete a coding challenge with the following restrictions.
Failing to follow the following restrictions will result in an invalid
submission:
Do ...