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: - `Cell` is used to model a (row, col, value) tuple - `Cage` (abstract) is used to model a grouping of `Cell` objects that must collectively satisfy a constraint. From this class, we have the following derived classes: - `AddCage` for cells involved in addition constraints - `MulCage` for cells involved in multiplication constraints - `SubCage` for cells involved in subtraction constraints - `DivCage` for cells involved in division constraints - `ConCage` for constant constraints - `RowCage` for unique row/column constraints - `Puzzle` combines cages, cells, and exposes methods for the unassigned cells, whether or not the puzzle is solved, etc. Now for the code: ``` from abc import ABC, abstractmethod from utils import kk_add, kk_mul, kk_sub, kk_div class Cell: def __init__(self, row, col, value=None): """ Models a cell in a kenken puzzle Args: row: row col: column value: cell value """ self.row = row self.col = col self.value = value def __str__(self): return ''.format(self.row, self.col, self.value) def __hash__(self): return hash((self.row, self.col)) def accept(self, visitor): """ Visitor implementation; accept a visitor object and call the object's visit method for this object Args: visitor: `CellVisitor` implementation Returns: None """ visitor.visit_cell(self) class Cage(ABC): def __init__(self, cells, func): """ Base class to model a cage in a kenken puzzle A cage is a grouping of cells with a constraint that the values of the cells must collectively satisfy Args: cells: the `Cell` objects i

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 unicorns. Each of your unicorns has either one or two of the following kinds of hairs in its mane: red hairs, yellow hairs, and blue hairs. The color of a mane depends on exactly which sorts of colored hairs it contains: ``` A mane with only one color of hair appears to be that color. For example, a mane with only blue hairs is blue. A mane with red and yellow hairs appears orange. A mane with yellow and blue hairs appears green. A mane with red and blue hairs appears violet. ``` You have R, O, Y, G, B, and V unicorns with red, orange, yellow, green, blue, and violet manes, respectively. You have just built a circular stable with N stalls, arranged in a ring such that each stall borders two other stalls. You would like to put exactly one of your unicorns in each of these stalls. However, unicorns need to feel rare and special, so no unicorn can be next to another unicorn that shares at least one of the hair colors in its mane. For example, a unicorn with an orange mane cannot be next to a unicorn with a violet mane, since both of those manes have red hairs. Similarly, a unicorn with a green mane cannot be next to a unicorn with a yellow mane, since both of those have yellow hairs. Is it possible to place all of your unicorns? If so, provide any one arrangement. Input The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with seven integers: N, R, O, Y, G, B, and V. Output For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if it is not possible to place all the unicorns, or a string of N characters representing the placements of unicorns in stalls, starting at a p

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 below. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. My explanation of algorithm I spent more than one hour to review my last practice, and like to ask code review for C# code. Highlights of change - Use meaningful variable names - the depth first search function has 5 arguments, I chose to order the arguments using 3 categories, input, DFS helper, output. - Use var explicit typing when possible. - Add two test cases. I am not sure if variable names can be named better, and 5 arguments in depth first search function `RunDepthFirstSearch` can be replaced by better implementation. ``` using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace _17LetterCombinationOfAPhoneNUmber_DFS { /* * Leetcode 17: * https://leetcode.com/problems/letter-combinations-of-a-phone-number/ * 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 below. * Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. * * Telephone dial pad: * 0 1 2 3 4 5 6 7 8 9 * String[] keyboard={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; */ class Solution { static void Main(string[] args) { RunTestcase(); } public static void RunTestcase() { // test result: "abc", "def", so 3x3 = 9 cases. IList letterCombinations = LetterCombination("23"); Debug.Assert(letterCombinatio

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, NOPNO is a valid output but NOPNPNO is not because it repeats here NOPNPNO. I tried to approach the problem using backtracking. My idea is to add a letter and check for repetitions until I get the right length that is required. You can check for more details of the problem here. This is the code that I came up: ``` #include #include using namespace std; bool found; /* This function check, for every time a letter is added, if the sequence * is going to repeat itself. For each pair of substrings with length i * they are compared to check if they are equal. * ex: * The sequence NONPNOPN will check if N = P, PN = NO, OPN = NPN, NOPN = NONP * * The function returns True if it should reject the sequence and False otherwise. */ bool reject(string str){ int i = 1, len = str.size(); while(i > n && n){ found = false; cin.ignore(); Thue(n,""); } return 0; } ``` It is working fine but my problem is, it's too slow. I think my problem is the function to check for repetitions but I don't know how I can make it faster. How can I speed this up?

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 the initial position of one of the queens. Input The first line of the input contains the number of datasets, and it's followed by a blank line. Each dataset contains a pair of positive integers separated by a single space that describes the initial position of one of the 8 queens Output Output for each dataset will consist of a one-line-per-solution representation. Each solution will be sequentially numbered 1...N. Each solution will consist of 8 numbers. Each of the 8 numbers will be the ROW coordinate for that solution. The column coordinate will be indicated by the order in which the 8 numbers are printed. That is, the rst number represents the ROW in which the queen is positioned in column 1; the second number represents the ROW in which the queen is positioned in column 2, and so on Sample Input ``` 1 1 1 ``` Sample Output ``` SOLN COLUMN # 1 2 3 4 5 6 7 8 1 1 5 8 6 3 7 2 4 2 1 6 8 3 7 4 2 5 3 1 7 4 6 8 2 5 3 4 1 7 5 8 2 4 6 3 ``` The full description of the problem can be found here. ``` #include #include #include #include class Chess { const int row_size, col_size; const int row_queen, col_queen; std::vector > sol; // queens_row_num[i] == on which row the queen is placed on col i int queens_row_num[8 + 1], idx_queens_row_num; bool queen_is_in_attack_pos(const int &row, const int &col) { for ( int j = 1; j v; for ( int j = 1; j > T; for ( int t = 1; t > r >> c; Chess chess = Chess(r, c); chess.find_solutions(); chess.print_solutions(); if ( t < T ) std::cout << std::endl; } return 0; } ``` What are the possible way to improve: - on quality-wise - t

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 in some suggestions/flaws in my code. Also, I had a really tough time getting this to work - I struggled mainly in trying to debug so many recursive calls and often got lost in analyzing which ones were waiting for "return value" from the other deeper function calls. — any help on how to get started/thinking about recursion while writing code would be very helpful. ``` package com.komal.backtracking; import java.util.concurrent.TimeUnit; public class Nqueens { static boolean[][] chessBoard; static int size; static int boundary; public void initChessBoard() { chessBoard = new boolean[size][size]; boundary = size - 1; } static int noOfBacktrackCalls; public static void main(String[] args) { size = 8; Nqueens nQueens = new Nqueens(); nQueens.initChessBoard(); long startTime = System.nanoTime(); if (!nQueens.backTrackRoutine(0, 0)) { System.out.println("Cannot be solved!!"); } for (boolean[] i : chessBoard) { System.out.print("\n{"); for (boolean i1 : i) { System.out.print(i1 + ","); } System.out.print("}"); } long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime); System.out.println("\nCompleted in :" + timeTaken + " milli sec"); System.out.println("\nTook " + noOfBacktrackCalls + " backtrack calls for completion!"); } public boolean backTrackRoutine(int row, int col) { noOfBacktrackCalls++; boolean flag = true; if (col == size || row == size) { return false; } if (canPlace(row, col)) { System.out.println("Placing queen at Row- " + row + " , col-" + col);

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 terminate but works for infinite domains: ``` brachylog_equals(Z,Z) :- brachylog_equals_('init',10,Z). brachylog_equals_(I,J,'integer':Z) :- fd_inf(Z,'inf'), fd_sup(Z,'sup') -> ( ( I = 'init' ; I \= 'init', abs(Z) #>= I ), abs(Z) # ( ( I = 'init' ; I \= 'init', Z #= -J, label([Z]) ; I2 is J, J2 is J*10, brachylog_equals_(I2,J2,'integer':Z) ) ; fd_sup(Z,'sup') -> ( ( I = 'init' ; I \= 'init', Z #>= I ), Z #< J, label([Z]) ; I2 is J, J2 is J*10, brachylog_equals_(I2,J2,'integer':Z) ) ; label([Z]). ``` A few notes about this code: - This predicate is supposed to be used in automatically generated Prolog code, therefore its name does not describe its function but rather follows a convention. - `'integer':Z` rather than simply `Z` is simply here to comply with the rest of the project (it is used to check easily the type of arguments in some other predicates) Here are my worries: - Is this the most idiomatic solution? (i.e. impose a finite bound on the variable where it has an infinite bound, and increase it recursively if backtracking occurs?) - Is this actually correct in all cases? (From what I tested it is, but I'm wondering if I missed some odd domains where it would break) - Is this computationally efficient? Of course comments on code style (which I know does not respect usual conventions) or code simplication are also welcome.

I have an assignment to write a knights tour backtracking program in Java where the professor says to: Eliminate backtracking time by: ``` Find the knights with the least possible moves Sort those moves from knight with least moves to greatest moves Backtrack if that path fails ``` I have done that with and attempted some other optimizations but my algorithm is still pretty slow for most squares. I went online and found my algorithm was pretty similar to others. I even took the algorithm from here and found it ran slow on the same spaces as mine (ahem pretty much never finishes) I was ready to call it until I took my processor's version from his website and it ran instantaneously on the squares every other version I had seen had run slowly on, he even showed me his code in his office last week and I recall it looking very similar. I have also seen questions on this site asking about their slow backtracking programs for knights tour. How is this possible!? Virtually every other source I have seen can confirm that this algorithm is slow except for my professor. My code: ``` /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// //Grid.java THIS IS WHERE THE MEAT AND POATATOS IS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!// //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/ public class Grid { //Constants to keep things consistant and avoid errors.// public final static char OBSTICLE_TILE_SYMBOLE = '0'; public final static char OPEN_TILE_SYMBOLE = '1'; private Tile[][] tileGrid; /************************************************* ** 'Makes for a nice api to do things this way, ** ** no construtor discourages the user from ******* ** makin

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. ``` # Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only # one letter at a time. The new word you get in each step must be in the # dictionary. # def transform(english_words, start, end): # transform(english_words, 'damp', 'like') # ['damp', 'lamp', 'limp', 'lime', 'like'] # ['damp', 'camp', 'came', 'lame', 'lime', 'like'] def is_diff_one(str1, str2): if len(str1) != len(str2): return False count = 0 for i in range(0, len(str1)): if str1[i] != str2[i]: count = count + 1 if count == 1: return True return False potential_ans = [] def transform(english_words, start, end, count): global potential_ans if count == 0: count = count + 1 potential_ans = [start] if start == end: print potential_ans return potential_ans for w in english_words: if is_diff_one(w, start) and w not in potential_ans: potential_ans.append(w) transform(english_words, w, end, count) potential_ans[:-1] return None english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like']) transform(english_words, 'damp', 'lame', 0) ```

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. ``` protected void calculateSolutions(final SudokuBoard input) { if (input.getFilledCells() == 81) { addSolution(input); return; } for (int grid = 0; grid results = new SudokuBacktrackSolver().solve(newInput); for (SudokuBoard result : results) { addSolution(result); } } } return; } } } } ``` The function `isPossibleAtPosition` checks whether the number exists in the cell, row or grid. If it is possible, I create a new `SudokuBoard`, which ends up in a tree structure, where each solution has a depth of 81. I also thought about creating a matrix containing all possibilities. This would improve the chance of finding a solution fastest but would produce a big overhead, and as I want to find all possible solutions, it would not be an improvement. Are there any delimitations to improve the algorithm?