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 static System.Console;
using System.Collections.Generic;
using System.Collections.Generic;
using System;


namespace Sudoku {
namespace Sudoku {
static class Program {
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 bool Solve(this int[][] grid, int r, int c) {
private static IEnumerable<int> Hints(this int[][] grid, int row, int col) =>
if (r == 9)
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(c == 8 ? r + 1 : r, ++c % 9);
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(r, c))
if (grid.Constraints(r, c) && grid.Solve(cells,++idx))
return true;
return true;
grid[r][c] = 0;
}
}
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) =>
⚫
string.Join('\n', grid.Select(row => string.Concat(row)));

public static int[][] Run(string input) {
var grid = Parse(input);
return grid.Solve(grid.SortedCells().ToList(), 0) ? grid : new int[][]{ Array.Empty<int>() };
}
}
⚫
}</lang>
Usage
<lang csharp>
⚫
using static System.Console;
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";
var grid = Parse(puzzle);
watch.Start();
WriteLine(Sudoku.Run(puzzle).AsString());
Write(grid.Solve(0, 0)
watch.Stop();
WriteLine($"Completed in {watch.ElapsedMilliseconds} ms");
⚫
? string.Join('\n', grid.Select(row=>string.Concat(row)))
: "No Solution");
Read();
Read();
}
}
}
}
}</lang>
}
⚫
</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===
Retrieved from "https://rosettacode.org/wiki/Sudoku"