Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
45 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
150 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
149 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
433 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
771 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
58 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
400 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
305 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
944 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
262 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
55 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. ...
3
votes
0answers
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
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
276 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
77 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
239 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
358 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
368 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
167 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
615 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
165 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
620 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
596 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
552 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
127 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
96 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
387 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 ...
1
vote
1answer
212 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
366 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
915 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
523 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
338 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
818 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
166 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
946 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 ...
10
votes
1answer
18k views

Solving Sudoku using backtracking

This is a solver for Sudoku using backtracking. How can I make it more optimized and clean? ...
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 ...
10
votes
3answers
927 views

Find biggest basin

Problem Statement A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland. We’ll represent the land as a two-dimensional ...