mshubham's blog

Programming Help
By mshubham, 13 years ago, In English

  1. Can anyone provide me the implementation and tutorial on Aho Corasick algorithms and some problems containing aho corasick algorithm.

  2. An algorithm to generate a random unsolved Sudoku whose only a unique solution exist.

  3. Find the dividend

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Aho Corasic Problem:

LightOJ 1427 — Substring Frequency (II)

CodeChef Music & Lyrics

Ahmed Aly's Site contains more problems.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Aho Corasick .This link is from wikipedia. The explanation is not absolutely clear but using my code you will understand it. I have named my variables according to the wikipedia post, so you can swap between webpage and source code.Here is the code. I hope that this would be helpful

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I don't think this could be so fast but it could make a random Sudoku in a few seconds. It's is very easy to solve a Sudoku by backtracing with little time. To generate a random unsolve Sudoku, firstly, create a finish state. Afterward, try to remove one cell in this state, then check the number of solotion (by backtracking). If this number = 0, you must undo your action, if this number >= 2, you could repeat this action.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Question 2

Your definition of "random" is underspecified. Uniformly random from all possible unique Sudoku puzzles? (This is insane and I doubt there is a better way than lookup of a gigantic table.) Simply generate a unique Sudoku puzzle that is sufficiently random? Just generate a valid Sudoku grid and remove a random square. Three squares, if you wish (this is the largest that can still ensure a unique solution).

Or you want to make a nice Sudoku puzzle that is human solvable? That is called intelligence and creativity. There's a reason why there are many popular pencil puzzle constructors (most notably Thomas Snyder for Sudoku perhaps?) whose puzzles are not boring/computer-generated.

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I have got the algorithm by ACRUSH to solve the problem, but i am unable to code it.

can anyone code it for mr ?

1) Implement one function SUDOKU(board) taking one board and output 0, 1, 2, for no solution, exact one solution, or two or more solutions, respectively.
2) Starting from an empty board. (say, board)
3) Random pick a empty cell (say, x, y), and random number (say v).
4) Set board[x][y] to v.
5) Call SUDOKU(board), suppose the return is c.
6) If (c = 1) we got it.
7) If (c = 0) clear board[x][y] and goto 3)
8) If (c = 2) goto 3)
→ Reply