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.
84
questions
3
votes
1
answer
89
views
Pentomino solver in Python
When I was a child, I used to play Ubongo board game, recently I discovered Pentomino puzzle and I wanted to create a custom solver in python for it. Here is what I got:
...
- 31
1
vote
1
answer
80
views
Positioning boxes in a box with backtracking in Java
A large cube-shaped box has the dimensions 5x5x5. This box is to be completely filled with smaller boxes. Possible candidates are:
...
- 332
1
vote
0
answers
95
views
Backtracking graph algorithms for a word puzzle in Python
Motivation
Recently, Buzzfeed released a browser-based puzzle game called "Pyramid Scheme." It is available at the following link. The puzzle in an initial state looks like this:
To solve ...
- 153
1
vote
2
answers
244
views
Count the number of ways N queens can be placed on an N✕N chess board
The n-queens puzzle is the problem of placing n queens on an n✕n chessboard such that no two queens attack each other.
Given an integer n, this code returns the number of distinct solutions to the n-...
- 147
1
vote
1
answer
93
views
2 slow and barely working sudoku solving implementations
The code below is working however, if more zeros (empty cells) are added to the sudoku grid g, it takes longer to run, if it ever finishes.
...
2
votes
0
answers
125
views
Followup: Use backtracking to put as many ships on a battleship-board as possible
I created a simple battleship game and wanted to be able to place as many ships on my board as possible.
The logic to place the ships uses some kind of backtracking to find a correct placement.
...
- 127
3
votes
1
answer
117
views
Exceeded time limit on Trie search with Backtracking using Swift
I have been trying to solve Trie related problems over at leet code and came across this interesting problem 211. Design Add and Search Words Data Structure
Here is the question for convenience:
211. ...
- 253
5
votes
2
answers
480
views
Leet Code 139 (Word Break) using a trie with recursion
I was attempting to solve LeetCode 139 - Word Break
Given a string s and a dictionary of strings wordDict, return
...
- 253
9
votes
2
answers
1k
views
Sudoku Solver in C without recursion
I am trying to learn backtracing , so i wrote program for Sudoku
It solves sudoku in approx. 1 ms in online c compiler
but this one sudoku puzzle is taking approx. 35 sec in that online c compiler ...
- 271
0
votes
1
answer
134
views
Speed up performance of backtracking solution for Sudoku solver
I can't improve the performance of the following Sudoku Solver backtracking solution. I know there are 3 loops here and they probably cause slow performance but I can't find a better/more efficient ...
- 11
3
votes
1
answer
473
views
Optimize "Fill magic square" in python with backtracking
I have written a python program with backtracking that fills a n * n magic square. It solves for n = 4 in 4.5 seconds but gets stuck when I run it for n = 5 on my ...
- 133
1
vote
0
answers
76
views
How can I optimise my recursive backtracking sudoku algorithm?
I've tried optimising my program by removing invalid values for possible spaces instead of searching from 1-9, and by choosing values with the lowest number of empty spaces in its row and column, but ...
- 11
6
votes
1
answer
143
views
Rust based Sudoku solver using backtracking
I've just started learning rust and have written a basic sudoku solver, however it seems to run much slower than I expected. So I'm looking for any possible performance improvements as well as any ...
- 63
6
votes
2
answers
428
views
Python backtracking algorithm to solve sudoku
I have recently gotten back into writing python and i decided to take up a project of writing a backtracking algorithm in python to solve Sudoku puzzles
How it Works
A matrix is declared to represent ...
5
votes
1
answer
2k
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, ...
user238196
6
votes
4
answers
1k
views
Solving a sudoku with backtracking
I wrote this java Class to solve a standard 9x9 sudoku board.
It uses backtracking to solve each field of the board.
I am really interested in feedback for the "isValid" and "...
- 127
4
votes
1
answer
155
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 ...
- 127
3
votes
1
answer
130
views
Sudoku Solver using rules of Sudoku and backtracking
This code tries to solve the sudoku board using the rules of sudoku. When it does not make progress in solving, it assumes a cell value and tries again. Please review my code and help me understand ...
- 103
2
votes
1
answer
227
views
Python sudoku solver using backtrack algorithm
My first attempt at a sudoku solver using the backtrack algorithm.
...
- 190
4
votes
1
answer
272
views
Sudoku solver using backtracting and depth-first-search
I've recently finished my first ever C program. I implemented a Sudoku solver that uses backtracking.
Does my code look like a proper C-program? Are there any recommendations for improving my code?
<...
1
vote
1
answer
491
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
"...
user214772
4
votes
1
answer
81
views
Filter out unwanted substrings while generating all possible relevant substrings
Write a Program that determines where to add periods to a decimal string so that
the resulting string is a valid IP address. There may be more than one valid IP address
corresponding to a string, ...
- 173
2
votes
1
answer
216
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:
...
1
vote
1
answer
587
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
2
answers
120
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 ...
- 83
3
votes
0
answers
166
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:
...
user73941
3
votes
1
answer
439
views
C backtracking Sudoku solver
I wrote this program in C to solve a given Sudoku puzzle (represented as 2D array) using backtracking algorithm. How can I make it more efficient, maybe faster and more C-onic?
This is my first post ...
- 31
1
vote
1
answer
252
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 ...
- 261
2
votes
1
answer
102
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 ...
- 21
4
votes
2
answers
646
views
Go function to generate permutations of a given integer array
I'm writing a function to generate a permutation of given []int:
...
- 141
4
votes
2
answers
1k
views
Solving Sudoku with backtracking
I wrote a backtracking Sudoku solving algorithm in Python.
It solves a 2D array like this (zero means "empty field"):
...
- 227
3
votes
1
answer
2k
views
LeetCode #37: Sudoku as Exact Cover Problem solved using Dancing Links
Introduction
I provide a regular 9x9 Sudoku solver, reducing the puzzle to an Exact Cover Problem. The algorithm used is Knuth'...
- 13.9k
21
votes
3
answers
4k
views
Loading military units into ships optimally, using backtracking
I solved the following problem using backtracking:
We are given a list of military units, their weight and their
(numerical) strength. We have a number of ships with a limited
carrying capacity....
- 313
3
votes
1
answer
287
views
Find number of islands Leetcode
Here is the question:
Given a 2d grid map of '1's (land) and '0's (water), count the number
of islands. An island is surrounded by water and is formed by
connecting adjacent lands horizontally ...
- 749
4
votes
3
answers
1k
views
Java Magic square program
Here is my improved version of my Magic square program from following this earlier version.
I also added a few comments.
Any help for improvements would be really appreciated.
...
- 585
4
votes
3
answers
4k
views
N Queens in Python using backtracking
I write this solution to the popular N Queens problem using backtracking algorithm. I am relatively new to Python. I would like to know what are the ways to refactor this code and also code style of ...
- 203
3
votes
1
answer
612
views
Speed up Magic square program
I have written a Java program to calculate magic squares with recursion and backtracking. A 3*3 Magic square is calculated in about 1 sec, but a 4*4 needs about 50 minutes on my laptop with Intel i5. ...
- 585
7
votes
1
answer
2k
views
N Queen Problem C++
Following code is solving n queen problem with c++ using backtracking. I saw other people solution they are very short like 20 to 30 lines. Is there way improve following code?
...
- 73
4
votes
1
answer
169
views
Two versions of Word Break II - exhaustive combinations
I am solving Word Break II from leetcode:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty ...
- 313
9
votes
2
answers
2k
views
C++ code for solving a sudoku using backtracking
I made a sudoku solver using backtracking in C++ and I would like to know what can I do to speed up my code. I am new to this language and I don't know all its special tricks yet! I was told to go to ...
- 91
5
votes
0
answers
502
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 ...
- 261
4
votes
2
answers
1k
views
N Queens in Python
I used Python very occasionally, today I solved n queens in Python just for fun. I am sure there are better way of doing certain things in Python and can't wait for improvement suggestions!
...
- 474
14
votes
1
answer
315
views
Recover flights from found tickets
I just found a whole bunch of plane tickets that only have a start and destination on them. I also know the route started in a certain city. I would like to recover the (alphabetically) first possible ...
- 449
1
vote
1
answer
81
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.
...
- 151
6
votes
1
answer
5k
views
C# recursive backtracker labyrinth generation & game
So for over a weekend I decided to write something rather simple. For maze generation I've followed this algorithm and aside from that I've made a little game, to go from A to B.
Everything works fine ...
- 217
2
votes
3
answers
5k
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 ...
- 21
2
votes
1
answer
333
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!
...
- 23
5
votes
1
answer
757
views
N queens variation recursion Python 3
I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) ...
- 51
5
votes
2
answers
2k
views
Two approaches to print all permutations - returning versus passing through the “result” list
I have noticed many of the backtracking problems have two ways of solving.
One is to return "whatever's the required list", vs passing-through the "result" to every call and appending to it. What is ...
- 101
1
vote
3
answers
976
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 ...
- 159