Anonymous user
Sudoku: Difference between revisions
m
→Functional Recursive Backtrack Solution
Line 1,826:
}</lang>
===
<!-- By Martin Freedman, 20/11/2021 -->
Still needs profiling/hot path tuning:
<lang csharp>using System.Linq;
using static System.Linq.Enumerable;
using System.Collections.Generic;
using System;
using System.Runtime.CompilerServices;
namespace Sudoku {
internal static class Sudoku {
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static
private static IEnumerable<(int
private static IEnumerable<int> GetBox(int[][] grid, int row, int col) =>▼
from r in Range(RowCol(row), 3)
from c in Range(RowCol(col), 3)
select
private static
from col in Range(0,
.ToDictionary(kvp => kvp.Item1, kvp => kvp.Item2.ToList());
private static IEnumerable<int>
.Union(Range(0, 9).Select(r => grid[r][col]).Distinct())▼
private static readonly
.Where(c => c != 0);▼
private static bool Solve(this int[][] grid, List<(int, int)> cells, int idx) {▼
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;
var (r, c) = cells[idx];
▲ if (grid.Constraints(r, c) && grid.Solve(cells,idx+1))
}
grid[r][c] = 0;
return false;
}
private static readonly int[] Unmarked = new[] { 0 };
.Union(GetBox(grid, row, col))
▲ private static IEnumerable<(int, int)> SortedCells(this int[][] grid) =>
▲ let cell = (count: grid[row][col] > 0 ? 10 : Hints(grid, row, col).Count(), cell: (row, col))
▲ orderby cell.count descending
▲ select cell.cell;
private static int[][] Parse(string input) =>
input
.Select((c, i) => (index: i, val: int.Parse(c.ToString())))
.GroupBy(id => id.index / 9
.Select(grp => grp.Select(id => id.val).ToArray())
.ToArray();
Line 1,890 ⟶ 1,897:
public static int[][] Run(string input) {
var grid = Parse(input);
var sorted = grid.SortedCells().ToList();
return grid.Solve(sorted, hits) ? grid : new int[][] { Array.Empty<int>() };
}
}
Line 1,900 ⟶ 1,909:
static class Program {
static void Main(string[] args) {
//https://staffhome.ecm.uwa.edu.au/~00013890/sudoku17 format
var puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000";
WriteLine(Sudoku.Run(puzzle).AsString());
Line 1,906 ⟶ 1,916:
}
}</lang>
Output
<pre>
617328945
| |||