29
votes
Algorithm to transform one word to another through valid words
There are four other answers here, and they all have very sensible advice. But none of them, as far as I can see, points out the terrible runtime complexity of the chosen algorithm, so I think an ...
26
votes
Accepted
Loading military units into ships optimally, using backtracking
The algorithm
This algorithm creates every combination of ships and tests them one by one, including combinations that could be seen to be useless by the first choice made. For example, if the first ...
16
votes
Accepted
Algorithm to transform one word to another through valid words
Always Return An Answer
Whenever you're writing an algorithm, it should return the answer. Not print and return, not just print. Just return. If you want to print, you can always write ...
15
votes
Accepted
Recover flights from found tickets
1. Review
The problem of putting the tickets in order is the same as that of constructing an Eulerian path on the directed graph whose edges correspond to the tickets. (An Eulerian path is a path in ...
14
votes
13
votes
Accepted
N Queen Problem C++
Welcome to Code Review. This post is a mixture between review, remarks, tutorial and general guidelines. Overall, your code has two complexity issues: space complexity due to types (see "Tip: Use ...
10
votes
Find biggest basin
I find this a nice piece of code.
Still I found 1 minor and 1 bigger issue.
Bigger issue :
You say in the javadoc that if more then 1 bassin is found the biggest must be returned.
You implement ...
9
votes
Loading military units into ships optimally, using backtracking
It appears that you've massively underestimated the complexity of the task. This is a classic Multiple Knapsack problem, and as is the case with all NP-hard problems, the time to solve it and/or the ...
7
votes
Coloring grid game
This is not C++. This is C. I suspect the only reason you label it as C++ code is because you needed to use a map.
Don't use C-style headers. <cstdio> ...
7
votes
Find biggest basin
private final
I think this is not the first time I'm telling you this. The ints in your enum really should be private final (At least final!)
...
7
votes
7
votes
Accepted
6
votes
Finding path in Maze
I'm sorry, but that code is really convoluted.
First off, does this actually work? The comparisons direction == "N"(etc.) should fail at compile time due to ...
6
votes
Accepted
Sudoku solutions finder using brute force and backtracking
Instead of using a fixed order of filling in cells you can first take the cells with the least amount of options left.
In other words if you know that cell 5,8 can only contain 5 and 6 then try each ...
6
votes
Accepted
Leetcode 17. Letter Combinations of a Phone Number
To use only static methods increases complexity of your code (because you need more parameters for function calls). In this review I won't change this to do not go to far away from your original code ...
6
votes
Accepted
A KenKen puzzle/solver in Python
I am unfamiliar with both the design pattern and the backtracking algorithm, so almost all of my comments will be nitpicks.
utils.py
...
5
votes
Accepted
Minimum number of moves for a knight
I will answer an isomorphous question of finding a minimal value in a binary tree. In your case, the tree is octal, but the same rules apply.
Consider that you have
...
5
votes
Accepted
Backtracking all the words in the English alphabet that have 5 letters, where no 2 consecutive letters can be consonants or vowels
In Python, strings support the sequence interface, so you can write the vowels and consonants as strings, which are easier to read than lists:
...
5
votes
Accepted
Haskell Sudoku solver using bactracking
Since you said you were looking for suggestions for coding style I will focus on that.
Comment your code! Preferably with Haddock style comments. Even if you aren't planning on sharing your code with ...
5
votes
5
votes
Accepted
UVA 750: 8 Queens Chess
Besides what Hosch250 said, with all of which I agree, here are a few more C++ style points:
#include <cmath>
You don't use anything from ...
5
votes
Sudoku solver iterating too much
You are not handling all the constraints, and that is the main problem leading to long runtime. So the only change needed is in the solve member function:
...
5
votes
Accepted
N Queens in Python
One option that might help speed things up would be to include a bit of redundant metadata with your board. Rather than just representing an array of 8*8 Booleans representing whether a Queen is in ...
5
votes
Accepted
Java Magic square program
Don't repeat yourself
You use x/size and x%size a lot. You can easily assign them to local variables, and your code becomes ...
5
votes
Accepted
Sudoku solver using backtracting and depth-first-search
Overall it looks fine for a beginner-level program, you keep the functions small and separate different parts of the logic between them, which is good.
...
4
votes
How many semi magic squares are there?
There could be smarter ways to write your code in such a way that it would scale better (for instance, if you were to consider squares of side 4 or 5, you'd have 16 or 25 nested loops and local ...
4
votes
Sudoku solutions finder using brute force and backtracking
creating a lot of objects
You are creating a new object every time you branch:
List<SudokuBoard> results = new SudokuBacktrackSolver().solve(newInput);
...
4
votes
Algorithm to transform one word to another through valid words
is_diff_one()
You have chosen to require both strings to be the same length. That's fine, but perhaps you would like to also consider adding or removing one ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
backtracking × 75algorithm × 27
java × 22
sudoku × 20
python × 16
recursion × 15
performance × 14
c++ × 13
programming-challenge × 8
n-queens × 8
beginner × 7
c × 7
time-limit-exceeded × 7
depth-first-search × 7
python-3.x × 6
chess × 5
haskell × 4
combinatorics × 4
c# × 3
matrix × 3
complexity × 3
game × 2
f# × 2
iteration × 2
prolog × 2