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
5
votes
1answer
463 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
5k 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
247 views

Sudoku verifier program

I implemented a Sudoku validation program. Can this be optimized even further in terms of performance? ...
6
votes
1answer
188 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
382 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
559 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
392 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
940 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
185 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
975 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
971 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
849 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
440 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? ...

1
2