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.
72
questions
2
votes
1answer
264 views
Given 2 numbers a and b find the smallest number greater than b by interchanging the digits of a and if not possible print -1
I have made the solution for this question it is based on backtracking. Can anyone suggest me how to make it work faster, I haven't practiced backtracking that much, although my solution seems to work....
2
votes
2answers
106 views
Performance is too low, online compiler wants a faster way to find all possible combinations of k numbers out of 1…n
I have to find a method (using backtracking) to list all possible combinations, in lexicographical order,of k numbers out of the interval [1,n].. duplicates are not allowed. i.e: input: 5 3output:1 2 ...
2
votes
1answer
86 views
Improved Backtracking with nqueen
I am implementing conflict-based backjumping with nqueen. I want to optimize my code especially in recursive call.
In short,backjumping is similar to backtracking and it uses conflict set. When ...
2
votes
1answer
269 views
Sudoku verifier program
I implemented a Sudoku validation program.
Can this be optimized even further in terms of performance?
...
2
votes
1answer
1k views
Display all solutions for NQueens
In my previous NQueens Code Review question, I received feedback saying that I should write a program that would find all solutions. This revised program should be more general than before.
...
2
votes
2answers
201 views
List.containsSlice
In an effort to strengthen my functional programming, I'm reading Functional Programming in Scala. One of the assignments is to implement a function that does the same operation as ...
2
votes
1answer
95 views
Python sudoku solver using backtrack algorithm
My first attempt at a sudoku solver using the backtrack algorithm.
...
2
votes
1answer
33 views
Time and Space Complexity of Leetcode Problem #31. Next Permutation
The question is as follows: Given a collection of distinct integers, return all possible permutations. Example:
...
2
votes
3answers
4k views
Beginner's Sudoku solver in C
I'm beginner programmer and I've challenged myself to write sudoku solver in C. I have finished it in few days and now I want to make it faster.
With this sample input execution time is 1.781 ...
2
votes
1answer
308 views
Backtracking maze traversal
I have a functional backtracking solution, but I am only able to finish 22/25 test cases before exceeding my specified time limit. Any suggestions on how to improve the speed are greatly appreciated!
...
2
votes
1answer
581 views
Adding elements in two lists as numbers
The problem is adding two lists as numbers L1 = [1,9,9] and L2 = [0,9,9]:
...
1
vote
2answers
443 views
All permutations of the pairs that add to squares
Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number.
E.g: Given an input number of 16, one of the possible answers would be:
...
1
vote
3answers
656 views
Sudoku solver iterating too much
I need help reducing the number of iterations my current implementation takes to solve the puzzle. I've got a pre-built class I am attempting to implement, albeit I think my backtracking needs ...
1
vote
1answer
164 views
Sudoku-Solver with GUI - follow-up
Background
A few months ago, I asked this and this question on my implementation of a Sudoku-Solver. I now tried to further improve this little project.
Changes
Minor GUI-changes
Input validation
"...
1
vote
1answer
107 views
Speeding up naive backtracking Sudoku Solver in Haskell
After watching a recent computerphile video on building a very simple sudoku solver I tried to implement the same in Haskell. From this CR question I learned that it is probably a better idea to use ...
1
vote
2answers
1k views
Backtrack algorithm
I coded this algorithm in order to have a generic backtracking algorithm. I expect the user to pass a POD for ELEMENT, hopefully as small as possible. Any idea how ...
1
vote
1answer
62 views
Simple backtracking code
Is this good or can it be improved? The program should backtrack the two variables until this logic operation is true: a & b.
...
1
vote
1answer
2k views
Is this a true backtracking algorithm?
So my project was to make an algorithm that finds a path out the maze using "backtracking" to help. This is my first time attempting to solve anything with backtracking so I want to be sure if what I ...
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 ...
0
votes
2answers
2k views
Partition array into 2 sets, such that different of sums in both subsets is minimal
Given a set of \$n\$ integers, divide the set in two subsets of \$\frac{n}{2}\$ sizes
each such that the difference of the sum of two subsets is as minimum
as possible. If \$n\$ is even, then ...
0
votes
1answer
752 views
Partitions of a number (backtracking) - time efficiency
I had to write an algorithm that prints the partitions of a natural number in lexicographic order. Example of I/O:
If the algorithm reads from ...
