**Sudoku solver**
Sudoku solver can solve any sudoku.
**How to use:**
1. Downlod sources.
2. Compile and run:
$ gcc main.c -lcurses -lm -ggdb && ./a.out data.sudoku.4 map.sudoku.4
**Examples of input data**
data.sudoku.4:
0,0,0,4,
0,0,3,0,
0,2,0,0,
1,0,0,0
map.sudoku.4
0,0,1,1,
0,0,1,1,
2,2,3,3,
2,2,3,3
+-----------------------+
| -2 1- | 12 4 |
| 3- 3- | -- |
| | |
| -2 1- | 3 12 |
| -4 -4 | -- |
|-----+-----+-----+-----|
| -- 2 | 1- 1- |
| 34 | -4 3- |
| | |
| 1 -- | -2 -2 |
| 34 | -4 3- |
+-----------------------+
--
2 3 1 4
4 1 3 2
3 2 4 1
1 4 2 3
------------------------------------------------------------------------------
+--------------------------------------------------------------+
| -23 1-3 12- | 123 123 123 | 123 123 9 |
| 456 456 456 | -56 4-6 45- | 456 456 |
| 78- 78- 78- | 78- 78- 78- | --- --- |
| | | |
| -23 1-3 12- | 123 123 123 | 123 8 123 |
| 456 456 456 | -56 4-6 45- | 456 456 |
| 7-9 7-9 7-9 | 7-9 7-9 7-9 | --- --- |
| | | |
| -23 1-3 12- | 123 123 123 | 7 123 123 |
| 456 456 456 | -56 4-6 45- | 456 456 |
| -89 -89 -89 | -89 -89 -89 | --- --- |
|------+------+------+------+------+------+------+------+------|
| -23 1-3 12- | 123 123 6 | 123 123 123 |
| 45- 45- 45- | --- --- | 45- 45- 45- |
| 789 789 789 | 789 789 | -89 7-9 78- |
| | | |
| -23 1-3 12- | 123 5 123 | 123 123 123 |
| 4-6 4-6 4-6 | --- --- | 4-6 4-6 4-6 |
| 789 789 789 | 789 789 | -89 7-9 78- |
| | | |
| -23 1-3 12- | 4 123 123 | 123 123 123 |
| -56 -56 -56 | --- --- | -56 -56 -56 |
| 789 789 789 | 789 789 | -89 7-9 78- |
|------+------+------+------+------+------+------+------+------|
| --- --- 3 | 12- 12- 12- | 12- 12- 12- |
| 456 456 | -56 4-6 45- | 456 456 456 |
| 789 789 | 789 789 789 | -89 7-9 78- |
| | | |
| --- 2 --- | 1-3 1-3 1-3 | 1-3 1-3 1-3 |
| 456 456 | -56 4-6 45- | 456 456 456 |
| 789 789 | 789 789 789 | -89 7-9 78- |
| | | |
| 1 --- --- | -23 -23 -23 | -23 -23 -23 |
| 456 456 | -56 4-6 45- | 456 456 456 |
| 789 789 | 789 789 789 | -89 7-9 78- |
+--------------------------------------------------------------+
--
7 8 4 3 6 5 1 2 9
5 6 9 1 2 7 3 8 4
2 3 1 8 4 9 7 5 6
3 1 5 2 8 6 9 4 7
9 4 2 7 5 1 6 3 8
6 7 8 4 9 3 2 1 5
4 5 3 6 7 2 8 9 1
8 2 6 9 1 4 5 7 3
1 9 7 5 3 8 4 6 2
------------------------------------------------------------------------------
+----------------------------------+
| -23 12- | 12- 123 5 |
| 4- 4- | 4- -- |
| | |
| +------+ |
| -23 12- | 12- | 123 123 |
| 45 45 | -5 | -- 4- |
| | | |
| +------+ +------+------|
| -2- | 12- 3 4 | 12- |
| -5 | -5 | -- |
| | | |
|------+------+ +------+ |
| -2- 3 | 12- | 12- 12- |
| 45 | -5 | -5 4- |
| | | |
| +------+ |
| 1 -2- -2- | -23 -23 |
| 45 45 | -5 4- |
| | |
+----------------------------------+
--
3 1 4 2 5
5 4 2 1 3
2 5 3 4 1
4 3 1 5 2
1 2 5 3 4
------------------------------------------------------------------------------
Example of not solvable sudoku:
+---------------------------------------------------------------------------------------------------------------+
| ---- | ---- ---- ---- | ---- | ---- |
| 4 ---8 | 5 ---8 ---8 7 3 ---8 1 | ---8 6 2 | ---8 a |
| --bc | 9-bc --bc 9-b- | --bc | 9-b- |
| -- | d- d- d- | de | -e |
| +-------+-------+ +-------+ | |
| ---- ---- ---- | ---4 ---4 ---- | --3- 1-3- 1--- | |
| ---8 5 ---8 -6-8 | ---8 -6-8 ---8 e | ---- ---8 7 ---8 | c 2 |
| 9-b- 9ab- 9ab- | -ab- 9ab- 9ab- | 9ab- -ab- 9ab- | |
| d- d- d- | d- d- d- | d- d- -- | |
| | +-------+ +-------+ |
| ---- ---- ---- ---- | ---- ---- | ---- ---- ---- | ---- |
| ---8 -678 --78 -678 | ---8 -6-8 2 | 4 5--- 5--8 5--8 | 5-78 1 3 |
| 9-bc -abc 9abc 9abc | -abc 9abc | 9ab- -abc -ab- | 9-b- |
| d- -- d- d- | d- d- | de de de | -- |
| +-------+-------+-------+ +-------+ |
| ---- | ---- | ---- ---- | ---- ---- ---- | ---- ---- |
| ---8 1 2 3 | --78 | -6-8 5-78 | 5--8 5--- 5--8 | 5--8 d -6-8 4 |
| 9-bc | -abc | 9abc 9abc | 9ab- 9ab- -abc | --b- 9-b- |
| -- | -- | -e -e | -- -e -e | -e -e |
|-------+-------+-------+-------+ | +-------+-------+-------+-------+ |
| ---4 ---- ---4 | ---- --3- --34 | --34 | ---- ---- ---- |
| 2 -678 e -678 --78 | 1 5-78 56-8 567- | 567- c | 5-78 -6-8 567- |
| -ab- -ab- -ab- | 9ab- 9ab- 9ab- | -ab- | 9-b- 9-b- 9-b- |
| -- d- d- | d- d- d- | d- | -- -- -- |
| +-------+ +-------+ +-------+-------+-------|
| ---4 ---4 | ---4 ---4 ---- ---- | ---4 | ---- ---- |
| 3 -678 --78 e | --78 -6-8 5-78 56-8 | 1 9 5--- 2 | -6-8 567- |
| -abc -abc | -abc -abc -abc -ab- | -ab- | -ab- --b- |
| -- d- | d- d- d- d- | d- | d- d- |
| | | | |
| ---4 | --34 -234 ---- -23- | --34 --34 ---4 | -23- ---- |
| 5 9 --7- 1 | --7- -6-- --7- -6-- | 8 -67- ---- --7- | -6-- -67- |
| -abc | -abc -abc -abc -ab- | -ab- -ab- -ab- | -ab- --b- |
| d- | de de de d- | d- d- -- | de de |
|-------+-------+-------+-------+-------+-------+-------+-------+ | |
| ---- --34 -2-- --34 | -234 ---- | --34 --34 --34 | -23- ---- |
| ---8 ---8 1 ---8 ---8 | ---8 ---8 7 | 56-- 56-- 5--- e | -6-8 56-- |
| 9-bc -abc 9abc -abc | -ab- -ab- | -ab- -ab- -ab- | 9ab- 9-b- |
| -- -- -- -- | d- d- | d- d- d- | d- d- |
| +-------+ +-------+-------+-------+-------+ |
| ---- ---- -2-- | 1-3- -23- | -23- 123- | 123- 1--- 1--- |
| ---8 e ---8 ---8 | ---8 ---8 6 c | 5-7- 5-78 | 5--8 5-78 4 5-7- |
| 9-b- 9ab- 9ab- | -ab- -ab- | 9ab- -ab- | -ab- 9ab- 9-b- |
| -- -- -- | d- d- | d- d- | d- -- d- |
| +-------+ +-------+ | |
| --34 ---4 | -2-- 1-34 1--- | 123- -234 1234 | 123- -23- 1--- |
| 6 ---8 ---8 | ---8 ---8 5 ---8 | ---8 --7- --78 | ---8 c ---8 --7- |
| -ab- 9ab- | -ab- -ab- -ab- | 9ab- 9ab- -ab- | -ab- 9ab- 9-b- |
| -- -- | d- de de | d- d- d- | de de de |
| +-------+-------+ | +-------+-------+-------+-------|
| | ---- | -23- 1--- | 123- -23- 123- 123- 1--- | -2-- 1--- |
| 7 d | ---8 4 | 9 ---8 ---8 | 56-8 56-- 56-8 5--8 5--8 | ---- ---- |
| | --bc | -ab- -ab- | -ab- -ab- -abc -ab- -ab- | -ab- --b- |
| | -- | -e -e | -- -- -- -- -- | -e -e |
|-------+-------+ +-------+-------+-------+ +-------+ |
| ---- ---- | ---- 1--- | -2-4 12-4 12-4 | -2-- 1--- |
| a --78 3 --78 | 5 ---8 --78 | e --7- --78 ---8 | 6 ---- ---- |
| --bc 9-bc | 9-b- 9-b- | 9-b- --bc --b- | --b- --b- |
| -- -- | d- d- | d- d- d- | d- d- |
| | +-------+-------+-------+-------+ |
| ---- ---- | --3- 1--- 1-3- 1-3- | 1--4 1--4 |
| e 2 --7- --7- | 6 ---- --7- ---- c --7- | ---- ---- 5 8 |
| 9-b- 9-b- | 9ab- 9ab- 9ab- -ab- | -ab- -ab- |
| -- -- | d- d- d- d- | d- -- |
| | +-------+ |
| | ---- ---- ---- | ---- |
| 1 d 6 5 | 2 ---8 4 ---8 ---- | ---- 9 3 7 c |
| | -ab- -ab- -ab- | -ab- |
| | -e -- -e | -e |
+---------------------------------------------------------------------------------------------------------------+
+---------------------------------------------------------------------------------------------------------------+
| | | | |
| 4 c | 5 8 d 7 3 9 1 | e 6 2 | b a |
| | | | |
| | | | |
| +-------+-------+ +-------+ | |
| ---- | | | |
| 8 5 ---- a | 4 6 b e | 3 1 7 9 | c 2 |
| ---- | | | |
| -- | | | |
| | +-------+ +-------+ |
| | | ---- | |
| d 7 9 6 | a c 2 | 4 b 8 ---- | 5 1 3 |
| | | ---- | |
| | | -- | |
| +-------+-------+-------+ +-------+ |
| | | | ---- | |
| b 1 2 3 | c | 9 7 | 5 a ---- | e d 6 4 |
| | | | ---- | |
| | | | -- | |
|-------+-------+-------+-------+ | +-------+-------+-------+-------+ |
| | | | ---- |
| 2 6 e b 7 | 1 5 3 4 | a c | 8 ---- 9 |
| | | | ---- |
| | | | -- |
| +-------+ +-------+ +-------+-------+-------|
| | | | |
| 3 a 4 e | b d c 6 | 1 9 5 2 | 8 7 |
| | | | |
| | | | |
| | | | |
| | ---- | | |
| 5 9 d 1 | e a ---- 2 | 8 7 b 4 | 3 6 |
| | ---- | | |
| | -- | | |
|-------+-------+-------+-------+-------+-------+-------+-------+ | |
| ---- | | | |
| c 4 1 ---- 8 | 2 a 7 | 6 3 d e | 9 5 |
| ---- | | | |
| -- | | | |
| +-------+ +-------+-------+-------+-------+ |
| | ---- | | ---- |
| 9 e a 2 | 3 ---- 6 c | 7 5 | ---- 1 4 d |
| | ---- | | ---- |
| | -- | | -- |
| +-------+ +-------+ | |
| ---- | | | |
| 6 3 ---- | d 1 5 e | 8 9 4 | 2 c a b |
| ---- | | | |
| -- | | | |
| +-------+-------+ | +-------+-------+-------+-------|
| | | ---- | ---- ---- | |
| 7 d | c 4 | 9 ---- 8 | ---- ---- 2 3 b | e 1 |
| | | ---- | ---- ---- | |
| | | -- | -- -- | |
|-------+-------+ +-------+-------+-------+ +-------+ |
| | | | ---- |
| a 8 3 7 | 5 b 9 | e d c 1 | 6 2 ---- |
| | | | ---- |
| | | | -- |
| | +-------+-------+-------+-------+ |
| | ---- | |
| e 2 b 9 | 6 3 1 ---- c d | 4 a 5 8 |
| | ---- | |
| | -- | |
| | +-------+ |
| | | |
| 1 d 6 5 | 2 8 4 a e | b 9 3 7 c |
| | | |
| | | |
+---------------------------------------------------------------------------------------------------------------+