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
3 votes
1 answer
84 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 ...
user avatar
  • 133
1 vote
0 answers
42 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 ...
user avatar
6 votes
1 answer
99 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 ...
user avatar
  • 63
6 votes
2 answers
210 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 ...
user avatar
5 votes
1 answer
679 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, ...
user avatar
6 votes
4 answers
954 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 "...
user avatar
  • 95
3 votes
0 answers
94 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 ...
user avatar
  • 95
3 votes
1 answer
96 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 ...
user avatar
  • 103
2 votes
1 answer
180 views

Python sudoku solver using backtrack algorithm

My first attempt at a sudoku solver using the backtrack algorithm. ...
user avatar
  • 190
4 votes
1 answer
160 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? <...
user avatar
1 vote
1 answer
317 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 "...
user avatar
4 votes
1 answer
69 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, ...
user avatar
  • 173
2 votes
1 answer
134 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: ...
user avatar
  • 21
1 vote
1 answer
352 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....
user avatar
2 votes
2 answers
111 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 ...
user avatar
  • 83
3 votes
0 answers
147 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: ...
user avatar
3 votes
1 answer
235 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 ...
user avatar
1 vote
1 answer
183 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 ...
user avatar
  • 261
2 votes
1 answer
92 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 ...
user avatar
  • 21
4 votes
2 answers
438 views

Go function to generate permutations of a given integer array

I'm writing a function to generate a permutation of given []int: ...
user avatar
  • 141
2 votes
2 answers
751 views

How to make my backtraching sudoku solving algorithm in Python faster?

I wrote a backtracking Sudoku solving algorithm in Python. It solves a 2D array like this (zero means "empty field"): ...
user avatar
  • 207
3 votes
1 answer
1k 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'...
user avatar
  • 13.8k
20 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....
user avatar
  • 303
3 votes
1 answer
237 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 ...
user avatar
  • 739
4 votes
3 answers
954 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. ...
user avatar
  • 575
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 ...
user avatar
  • 203
3 votes
1 answer
490 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. ...
user avatar
  • 575
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? ...
user avatar
  • 73
4 votes
1 answer
156 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 ...
user avatar
9 votes
2 answers
1k 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 ...
user avatar
5 votes
0 answers
461 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 ...
user avatar
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! ...
user avatar
  • 474
14 votes
1 answer
297 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 ...
user avatar
  • 449
1 vote
1 answer
74 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. ...
user avatar
  • 151
6 votes
1 answer
4k 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 ...
user avatar
  • 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 ...
user avatar
2 votes
1 answer
319 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! ...
user avatar
  • 23
1 vote
0 answers
107 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 ...
user avatar
5 votes
1 answer
645 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) ...
user avatar
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 ...
user avatar
  • 101
1 vote
3 answers
867 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 ...
user avatar
  • 119
6 votes
1 answer
369 views

Puzzle game solver via Backtracking

I'm relatively new to Haskell and I'd like to get feedback on the style of my program. Specifically: Coding Style: Can any parts be written in a more concise or more readable way? Misuse: Are there ...
user avatar
  • 261
17 votes
2 answers
2k views

A KenKen puzzle/solver in Python

I've written a simple KenKen puzzle/solver in Python. I'd love some feedback on the design of the puzzle, as well as the architecture for the solver. To model the puzzle, I have the following classes:...
user avatar
4 votes
1 answer
204 views

Google Code Jam 2017 1B - Stable Neigh-bors

Last week I participated in Google code Jam round 2B and miserably failed. I still decided to finish the second question, for practice. Here it is: Problem You are lucky enough to own N pet ...
user avatar
  • 113
7 votes
1 answer
947 views

Leetcode 17. Letter Combinations of a Phone Number

Problem Statement Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. ...
user avatar
  • 2,376
3 votes
2 answers
803 views

Problems with backtracking algorithm in C++

I have to implement an algorithm that generates a modified version of a Thue Sequence, being that there can't be any adjacent sub-sequence can repeat itself using the letters N,P and O. For example, ...
user avatar
8 votes
3 answers
828 views

UVA 750: 8 Queens Chess

In chess it is possible to place eight queens on the board so that no one queen can be taken by any other. Write a program that will determine all such possible arrangements for eight queens given ...
user avatar
  • 337
2 votes
1 answer
1k views

Knight's tour code

Another one for some late night snack. - Knight's tour! Please provide your suggestions/flaws/optimization to this knight's tour backtracking code.. ...
user avatar
0 votes
1 answer
844 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 ...
user avatar
  • 151
8 votes
3 answers
2k views

n-Queens backtracking code

I was learning backtracking algorithms earlier today, and was excited and wrote this code for n-Queens problem. Being my first try at backtracking algorithms, I would appreciate if you guys could chip ...
user avatar