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.
72
questions
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.
...
4
votes
3answers
3k 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 ...
5
votes
1answer
466 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 ...
8
votes
3answers
6k 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 <...
2
votes
1answer
269 views
Sudoku verifier program
I implemented a Sudoku validation program.
Can this be optimized even further in terms of performance?
...
6
votes
1answer
189 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 ...
3
votes
2answers
395 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 ...
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
1answer
1k 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
585 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
393 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
978 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
201 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
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:
...
10
votes
3answers
987 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 ...
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
984 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 ...
10
votes
2answers
855 views
Finding path in Maze
I recently gave an interview and was asked the following question. I posted this here
Finding path in Maze also, and someone suggested I should try Code Review. So here it goes.
A maze is a group of ...
1
vote
2answers
443 views
All permutations of the pairs that add to squares
Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number.
E.g: Given an input number of 16, one of the possible answers would be:
...
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?
...
