实在闲着无聊，把平时在公司闲着无聊刷的有意思一点的算法题发一下把。虽然平时喜欢写C++，不过上班用的C#嘛，就随手C#写了。有更好想法，或者想一起交流学习的就留言咯~尤其是有游戏客户端开发的大佬能一起学习就更好了（本人服务器开发，哈哈）不多说，上代码吧。
public class SudokuArea { private class SudokuInputNode { public List
ValidList = new List
(); public int CurNum; public int Column; public int Row; public int Area; public int Next; } private class SudokuArea { public int Id; public List
SourceList = new List
(); public List
InputList = new List
(); } private class SudokuColumn { public int Id; public List
SourceList = new List
(); public List
InputList = new List
(); } private class SudokuRow { public int Id; public List
SourceList = new List
(); public List
InputList = new List
(); } // 测试用数据 private readonly int[] _numberArray = { 5, 3, 0, 0, 7, 0, 0, 0, 0, 6, 0, 0, 1, 9, 5, 0, 0, 0, 0, 9, 8, 0, 0, 0, 0, 6, 0, 8, 0, 0, 0, 6, 0, 0, 0, 3, 4, 0, 0, 8, 0, 3, 0, 0, 1, 7, 0, 0, 0, 2, 0, 0, 0, 6, 0, 6, 0, 0, 0, 0, 2, 8, 0, 0, 0, 0, 4, 1, 9, 0, 0, 5, 0, 0, 0, 0, 8, 0, 0, 7, 9, }; private readonly List
_sudokuInputList = new List
(); private readonly Dictionary
_sudokuAreas = new Dictionary
(); private readonly Dictionary
_sudokuColumns = new Dictionary
(); private readonly Dictionary
_sudokuRows = new Dictionary
(); private void Run() { var curIndex = 0; while (curIndex < _sudokuInputList.Count || curIndex < 0) { var curNode = _sudokuInputList[curIndex]; if (!TryNodeNextNum(curNode)) { RemoveInputNum(curNode.Row, curNode.Column, curNode.Area, curNode.CurNum); curIndex--; var lastNode = _sudokuInputList[curIndex]; RemoveInputNum(lastNode.Row, lastNode.Column, lastNode.Area, lastNode.CurNum); continue; } curIndex++; } foreach (var node in _sudokuInputList) { _numberArray[node.Row * 9 + node.Column] = node.CurNum; } } private void Init() { InitSudokuData(); InitSudokuNodeValidNum(); } private void AddInputNum(int rowId, int columnId, int areaId, int num) { _sudokuRows[rowId].InputList.Add(num); _sudokuColumns[columnId].InputList.Add(num); _sudokuAreas[areaId].InputList.Add(num); } private void RemoveInputNum(int rowId, int columnId, int areaId, int num) { _sudokuRows[rowId].InputList.Remove(num); _sudokuColumns[columnId].InputList.Remove(num); _sudokuAreas[areaId].InputList.Remove(num); } private bool TryNodeNextNum(SudokuInputNode node) { bool valid = false; var curNum = 0; while (node.Next < node.ValidList.Count) { curNum = node.ValidList[node.Next++]; if (CheckNumValid(node.Row, node.Column, node.Area, curNum)) { valid = true; break; } } if (!valid) { node.CurNum = 0; node.Next = 0; return false; } node.CurNum = curNum; AddInputNum(node.Row, node.Column, node.Area, node.CurNum); return true; } private bool CheckNumValid(int rowId, int columnId, int areaId, int num) { if (_sudokuAreas.TryGetValue(areaId, out var area)) { if (area.SourceList.Contains(num) || area.InputList.Contains(num)) { return false; } } if (_sudokuColumns.TryGetValue(columnId, out var column)) { if (column.SourceList.Contains(num) || column.InputList.Contains(num)) { return false; } } if (_sudokuRows.TryGetValue(rowId, out var row)) { if (row.SourceList.Contains(num) || row.InputList.Contains(num)) { return false; } } return true; } // 初始化所有节点可填数字 private void InitSudokuNodeValidNum() { foreach (var node in _sudokuInputList) { for (var i = 1; i <= 9; ++i) { if (_sudokuAreas.TryGetValue(node.Area, out var area)) { if (area.SourceList.Contains(i)) { continue; } } if (_sudokuColumns.TryGetValue(node.Column, out var column)) { if (column.SourceList.Contains(i)) { continue; } } if (_sudokuRows.TryGetValue(node.Row, out var row)) { if (row.SourceList.Contains(i)) { continue; } } node.ValidList.Add(i); } } } private void InitSudokuData() { for (var i = 0; i < _numberArray.Length; i++) { var column = i % 9; var row = i / 9; var num = _numberArray[i]; var area = GetSudokuAreaId(row, column); if (num == 0) { _sudokuInputList.Add(new SudokuInputNode { CurNum = 0, Column = column, Row = row, Area = area }); continue; } if (_sudokuColumns.TryGetValue(column, out var sudokuColumn)) { sudokuColumn.SourceList.Add(num); } else { _sudokuColumns.Add(column, new SudokuColumn{ Id = column, SourceList = {num} }); } if (_sudokuRows.TryGetValue(row, out var sudokuRow)) { sudokuRow.SourceList.Add(num); } else { _sudokuRows.Add(row, new SudokuRow { Id = row, SourceList = { num } }); } if (_sudokuAreas.TryGetValue(area, out var sudokuArea)) { sudokuArea.SourceList.Add(num); } else { _sudokuAreas.Add(area, new SudokuArea { Id = area, SourceList = { num } }); } } } private int GetSudokuAreaId(int row, int column) { return (row / 3) * 3 + (column / 3); } }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208086.html原文链接：https://javaforall.net
