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
6
votes
1answer
2k 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 ...
2
votes
2answers
62 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"): ...
3
votes
1answer
69 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'...
19
votes
3answers
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....
3
votes
1answer
49 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 ...
4
votes
3answers
158 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. ...
3
votes
1answer
154 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. ...
3
votes
3answers
605 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 ...
7
votes
1answer
827 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? ...
1
vote
0answers
63 views

I have written two versions of Word Break exhaustive combinations. Please comment

I am solving Word Break II from leetcode. https://leetcode.com/problems/word-break-ii/description/ Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add ...
10
votes
2answers
423 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 ...
5
votes
0answers
314 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
2answers
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! ...
14
votes
1answer
265 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 ...
1
vote
1answer
59 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. ...
2
votes
3answers
2k 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 ...
7
votes
3answers
1k 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 ...
2
votes
1answer
285 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! ...
1
vote
0answers
80 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 ...
6
votes
1answer
254 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 ...
5
votes
1answer
370 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) ...
5
votes
2answers
1k 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 ...
1
vote
2answers
374 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 ...
16
votes
2answers
1k 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:...
22
votes
5answers
10k views

Algorithm to transform one word to another through valid words

I have been practicing backtracking and I wanted to know how I can improve my code. For eg, I don't want to use global. Also, I am not sure if my code will work for all the cases. ...
4
votes
1answer
170 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 ...
6
votes
1answer
662 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 ...
3
votes
2answers
173 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, ...
4
votes
3answers
2k views

Coloring grid game

I have grid N × M in which each cell is coloured with one colour. When the player clicks on any cell of the grid of colour α, the cell in the top-leftmost corner of the grid, of colour β, receives ...
8
votes
3answers
630 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 ...
2
votes
1answer
637 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.. ...
0
votes
1answer
568 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 ...
3
votes
2answers
131 views

CLP(FD) labeling on possibly infinite domains

As a follow-up to this SO question, I implemented, for my Prolog-based language Brachylog, my own labeling predicate brachylog_equals/2 which is not guaranteed to ...
4
votes
1answer
98 views

Knights Tour — Something I am doing wrong

I have an assignment to write a knights tour backtracking program in Java where the professor says to: Eliminate backtracking time by: ...
8
votes
3answers
4k views

Minimum number of moves for a knight

The problem is to find the minimum number of moves that a knight will take to go from one square to another on a 'n' cross 'n' chessboard. The code below is based on backtracking. It works well until <...
6
votes
2answers
2k views

Sudoku solutions finder using brute force and backtracking

I'm calculating all possible solutions for a given Sudoku board with at least 17 values. My approach is a basic backtracking approach and it works. ...
5
votes
1answer
399 views

Sudoku-solving program

This is a Sudoku solver program which uses backtracking. It is a problem from Online Judge and I made it work after some struggle, but it needs to be faster as I'm getting a Time Limit Exceeded ...
2
votes
1answer
217 views

Sudoku verifier program

I implemented a Sudoku validation program. Can this be optimized even further in terms of performance? ...
6
votes
1answer
183 views

Solving a partially completed 10x10 tournament schedule

My buddy schedules a dart tournament, and got into trouble when there were some scheduling conflicts. He has the first 3 weeks in the books, and needs to finish out the rest of the schedule. Turns out ...
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. ...
3
votes
2answers
371 views

Backtracking all the words in the English alphabet that have 5 letters, where no 2 consecutive letters can be consonants or vowels

I have the following problem in my algorithms textbook: Write a computer program that generates and counts how many words of 5 letters of the English alphabet can be formed, with the condition that ...
3
votes
1answer
917 views

Haskell Sudoku solver using bactracking

This solves Sudoku by using backtracking. Accepts one grid where 0 represents a missing number. Here are some examples: http://norvig.com/easy50.txt The program is quite slow. Input is stdin. ...
2
votes
1answer
524 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
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 ...
7
votes
1answer
349 views

Depth First Backtracking Puzzle Solver

There is this type of puzzle that can easily be solved with a depth-first backtracking solver. I wrote one in python 3.4 and like to get some feedback. I'm especially interested in the following ...
4
votes
0answers
826 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? ...
2
votes
2answers
172 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 ...
6
votes
1answer
94 views

'Tis the season for gift-wrapping

When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer: ...
10
votes
3answers
954 views

How many semi magic squares are there?

I want to write a program to work out how many semi-magic squares there are. Here is the definition of semi-magic squares If we define \$H_n(t)\$ is the number of semi magic squares which satisfy:...
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 ...