Sudoku: Difference between revisions
Content added Content deleted
m (→Functional Recursive Backtrack Solution: No need to state C# version) |
|||
Line 1,830: | Line 1,830: | ||
<lang csharp>using System.Linq; |
<lang csharp>using System.Linq; |
||
using static System.Linq.Enumerable; |
using static System.Linq.Enumerable; |
||
⚫ | |||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System; |
|||
namespace Sudoku { |
namespace Sudoku { |
||
static class |
internal static class Sudoku { |
||
private static bool Unique(this IEnumerable<int> values) => values.Distinct().Count() == values.Count(); |
private static bool Unique(this IEnumerable<int> values) => values.Distinct().Count() == values.Count(); |
||
private static bool IsUnequal(this IEnumerable<int> values) => values.Where(c => c != 0).Unique(); |
private static bool IsUnequal(this IEnumerable<int> values) => values.Where(c => c != 0).Unique(); |
||
Line 1,849: | Line 1,849: | ||
GetBox(grid, row, col).IsUnequal(); |
GetBox(grid, row, col).IsUnequal(); |
||
private static |
private static IEnumerable<int> Hints(this int[][] grid, int row, int col) => |
||
grid[row].Distinct() |
|||
.Union(Range(0, 9).Select(r => grid[r][col]).Distinct()) |
|||
.Union(GetBox(grid, row, col).Distinct()) |
|||
.Where(c => c != 0); |
|||
⚫ | |||
private static IEnumerable<(int, int)> SortedCells(this int[][] grid) => |
|||
from row in Range(0, 9) |
|||
from col in Range(0, 9) |
|||
let cell = (count: Hints(grid, row, col).Count(), cell: (row, col)) |
|||
orderby cell.count descending |
|||
select cell.cell; |
|||
private static bool Solve(this int[][] grid, List<(int,int)> cells, int idx) { |
|||
if (idx == 81) |
|||
return true; |
return true; |
||
var (r, c) = cells[idx]; |
|||
if (grid[r][c] != 0) |
if (grid[r][c] != 0) |
||
return grid.Solve( |
return grid.Solve(cells,++idx); |
||
⚫ | |||
foreach (var i in Range(1,9)) { |
foreach (var i in Range(1, 9)) { |
||
grid[r][c] = i; |
grid[r][c] = i; |
||
if (grid.Constraints(r, c) && grid.Solve( |
if (grid.Constraints(r, c) && grid.Solve(cells,++idx)) |
||
return true; |
return true; |
||
} |
|||
grid[r][c] = 0; |
|||
return false; |
return false; |
||
} |
} |
||
private static int[][] Parse(string input) => |
private static int[][] Parse(string input) => |
||
input |
input |
||
.Select((c, i) => (index: i, val: int.Parse(c.ToString()))) |
.Select((c, i) => (index: i, val: int.Parse(c.ToString()))) |
||
Line 1,871: | Line 1,885: | ||
.ToArray(); |
.ToArray(); |
||
public static string AsString(this int[][] grid) => |
|||
⚫ | |||
public static int[][] Run(string input) { |
|||
var grid = Parse(input); |
|||
return grid.Solve(grid.SortedCells().ToList(), 0) ? grid : new int[][]{ Array.Empty<int>() }; |
|||
} |
|||
} |
|||
⚫ | |||
Usage |
|||
<lang csharp> |
|||
⚫ | |||
namespace Sudoku { |
|||
static class Program { |
|||
static void Main(string[] args) { |
static void Main(string[] args) { |
||
var watch = new System.Diagnostics.Stopwatch(); |
|||
//https://staffhome.ecm.uwa.edu.au/~00013890/sudoku17 format |
|||
var puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000"; |
var puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000"; |
||
watch.Start(); |
|||
WriteLine(Sudoku.Run(puzzle).AsString()); |
|||
watch.Stop(); |
|||
WriteLine($"Completed in {watch.ElapsedMilliseconds} ms"); |
|||
⚫ | |||
: "No Solution"); |
|||
Read(); |
Read(); |
||
} |
|||
} |
|||
}</lang> |
|||
} |
|||
⚫ | |||
Output |
Output |
||
<pre> |
<pre> |
||
697328105 |
|||
617328945 |
|||
800517234 |
|||
894517236 |
|||
354906700 |
|||
325946781 |
|||
579682403 |
|||
978651423 |
|||
286134957 |
|||
256834179 |
|||
103759628 |
|||
143792658 |
|||
738460509 |
|||
731489562 |
|||
425093816 |
|||
489265317 |
|||
961875302 |
|||
562173894</pre> |
|||
Completed in 431 ms |
|||
</pre> |
|||
===“Automatic” Solution=== |
===“Automatic” Solution=== |