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
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? ...
25
votes
5answers
11k 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. ...
17
votes
2answers
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:...
3
votes
1answer
634 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'...
14
votes
1answer
276 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 ...
10
votes
3answers
973 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 ...
1
vote
1answer
129 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 "...
6
votes
1answer
105 views

'Tis the season for gift-wrapping

When reviewing a Graham scan convex hull algorithm implementation, I wrote the following function in an answer: ...
4
votes
3answers
607 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
291 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. ...
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. ...