CombinatorialPuzzleSolver::Constraint

is an array

CombinatorialPuzzleSolver::Constraint#possible_values

should return a Hash

should contain each value, and the identifiers that can have them.

CombinatorialPuzzleSolver::Constraint#resolvable_identifiers

should return a Hash

should return the identifiers mapped to their resolved value

CombinatorialPuzzleSolver::Identifier#value

should have value nil by default

CombinatorialPuzzleSolver::Identifier#has_value?

should return true if it has a value, false otherwise

CombinatorialPuzzleSolver::Identifier#constraints

should return an Array of all dependent constraints

CombinatorialPuzzleSolver::Identifier#set!

should set the given value

CombinatorialPuzzleSolver::Identifier#dependent_identifiers

should give all other identifiers covered by its constraints

CombinatorialPuzzleSolver::Possibilities

is an array

CombinatorialPuzzleSolver::Possibilities#must_be!

should remove all values except the given value

should return the dependent identifiers that becomes resolved.

Given the solution space:

{[0]=>[1], [1]=>[2], [2]=>[3], [3]=>[4, 5], [4]=>[4, 5]}

It resolves the follwing if [3] must be 4:

{[4]=>5}

should raise Inconsistency if identifier already has different value

should raise Inconsistency if the given value is not part of the set

CombinatorialPuzzleSolver::Possibilities#cannot_be!

should remove the given value

should raise Inconsistency if it becomes empty

should raise Inconsistency if the identifier is set to the given value

should return a Hash

should return the same Hash object as the given one (if it is given)

should return the resolved identifier if it only has one remaining value

CombinatorialPuzzleSolver::Possibilities#dependent_identifiers_cannot_be!

should reduce possibilities of dependent identifiers

CombinatorialPuzzleSolver::Possibilities#resolved?

should return true if it only has one possible value, false otherwise

CombinatorialPuzzleSolver::Puzzle#initialize

should fail unless the block returns Constraint(s)

CombinatorialPuzzleSolver::Puzzle#identifiers

should return an array of all the identifiers

CombinatorialPuzzleSolver::Puzzle#constraints

should return an array of all the constraints

CombinatorialPuzzleSolver::Puzzle#symbols

should return an array of all the possible symbolsfor an identifier

CombinatorialPuzzleSolver::Puzzle#resolve!

should return true when puzzle is solvable

{  [ }  ]

should raise inconsistency when the puzzle is unsolvable

when :parsed_stream is given

should write the parsed input puzzle

when :steps_stream is given

should write each resolution step

when :puzzle_stream is given

should write the puzzle for each resolution step

when :result_stream is given

should write the resulting puzzle

CombinatorialPuzzleSolver::SolutionSpace#initialize

is a Hash mapping between identifiers and their possible values

creates a clone if another SolutionSpace is given as argument

CombinatorialPuzzleSolver::SolutionSpace#resolved_identifiers

should return a Hash

should return all identifiers that are resolved

should not include identifiers that have value

CombinatorialPuzzleSolver::SolutionSpace#unresolved_identifiers

should return a Hash

should return all unresolved identifiers and their possible values

CombinatorialPuzzleSolver::SolutionSpace#resolvable_from_constraints

should return a Hash

should return the identifiers that can be resolved by constraints

CombinatorialPuzzleSolver::SolutionSpace#resolve!

should return true if the solution space becomes resolved

should return false if the solution space is still not resolved

should raise Inconsistency if a solution is impossible

should yield solution space, identifier and value for every step

Given the 4x4 sudoku puzzle:

   |4  
1  |   
---+---
   |  3
  1|   

Yielded [2,4]=2.

   |4  
1  |  2
---+---
   |  3
  1|   

Yielded [4,3]=2.

   |4  
1  |  2
---+---
   |  3
  1|2  

Yielded [2,3]=3.

   |4  
1  |3 2
---+---
   |  3
  1|2  

Yielded [1,4]=1.

   |4 1
1  |3 2
---+---
   |  3
  1|2  

Yielded [4,4]=4.

   |4 1
1  |3 2
---+---
   |  3
  1|2 4

Yielded [3,3]=1.

   |4 1
1  |3 2
---+---
   |1 3
  1|2 4

Yielded [2,2]=4.

   |4 1
1 4|3 2
---+---
   |1 3
  1|2 4

Yielded [4,1]=3.

   |4 1
1 4|3 2
---+---
   |1 3
3 1|2 4

Yielded [3,2]=2.

   |4 1
1 4|3 2
---+---
  2|1 3
3 1|2 4

Yielded [1,1]=2.

2  |4 1
1 4|3 2
---+---
  2|1 3
3 1|2 4

Yielded [3,1]=4.

2  |4 1
1 4|3 2
---+---
4 2|1 3
3 1|2 4

Yielded [1,2]=3.

2 3|4 1
1 4|3 2
---+---
4 2|1 3
3 1|2 4
CombinatorialPuzzleSolver::SolutionSpace#resolve_by_trial_and_error!

should return a completely resolved solution space if possible

should raise Inconsistency if no solution is possible

CombinatorialPuzzleSolver::SolutionSpace#try_resolve_with

should return SolutionSpace resolved with the the identifier and value

should return nil if the identifier and value makes it irresolvable.

CombinatorialPuzzleSolver::SolutionSpace#resolved?

should return true if the puzzle is completely resolved, false otherwise

CombinatorialPuzzleSolver::Sudoku

solves sudoku puzzles

Given the puzzle:

     |3   1|     
    9|     |     
  8  |     |  3  
-----+-----+-----
     |    4|9 8  
    7|1 2  |5    
2    |  9  |1 7  
-----+-----+-----
  5  |  1 2|     
  9  |    7|     
3    |4   5|    8

When resolved:

4 2 6|3 8 1|7 5 9
1 3 9|7 5 6|8 2 4
7 8 5|2 4 9|6 3 1
-----+-----+-----
5 1 3|6 7 4|9 8 2
9 6 7|1 2 8|5 4 3
2 4 8|5 9 3|1 7 6
-----+-----+-----
8 5 4|9 1 2|3 6 7
6 9 2|8 3 7|4 1 5
3 7 1|4 6 5|2 9 8
CombinatorialPuzzleSolver::Sudoku#initialize

should raise RuntimeError if digits contain wrong number of values

CombinatorialPuzzleSolver::Sudoku#rows

should return an array of all identifiers grouped in rows.

Rows

111111111
222222222
333333333
444444444
555555555
666666666
777777777
888888888
999999999
CombinatorialPuzzleSolver::Sudoku#columns

should return an array of all identifiers grouped in columns.

Columns

123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
CombinatorialPuzzleSolver::Sudoku#squares

should return an array of all identifiers grouped in squares

Squares

111222333
111222333
111222333
444555666
444555666
444555666
777888999
777888999
777888999
CombinatorialPuzzleSolver::Sudoku.scan

should create Sudoku puzzles and set the values

Given the input string:

000|301|000
009|000|000
080|000|030
---+---+---
000|004|980
007|120|500
200|090|170
---+---+---
050|012|000
090|007|000
300|405|008

It creates the puzzle:

     |3   1|     
    9|     |     
  8  |     |  3  
-----+-----+-----
     |    4|9 8  
    7|1 2  |5    
2    |  9  |1 7  
-----+-----+-----
  5  |  1 2|     
  9  |    7|     
3    |4   5|    8

should ignore every character except the digits

Given the input string:

000301000009000000080000030000004980007120500200090170050012000090007000300405008

It creates the puzzle:

     |3   1|     
    9|     |     
  8  |     |  3  
-----+-----+-----
     |    4|9 8  
    7|1 2  |5    
2    |  9  |1 7  
-----+-----+-----
  5  |  1 2|     
  9  |    7|     
3    |4   5|    8