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.

Filter by
Sorted by
Tagged with
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 ...

1
2