搜索

首页  >  问答  >  正文

Typescript数独问题显示部分填充的棋盘

我已经成功将一个js数独生成器转换成了一个ts生成器进行练习,唯一的问题是如何让它只输出完整的数独盘面。现在,它无论盘面是否完整都会输出,我必须刷新直到出现一个正确的盘面。

我不确定如何编写以下函数,以便它只输出完整的盘面:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

function fillBoard(puzzleArray: number[][]): number[][] {

    if (nextEmptyCell(puzzleArray).colIndex === -1) return puzzleArray;

 

    let emptyCell = nextEmptyCell(puzzleArray);

 

    for (var num in shuffle(numArray)) {

      if (safeToPlace(puzzleArray, emptyCell, numArray[num])) {

        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = numArray[num];

        fillBoard(puzzleArray);

      }

    }

 

    return puzzleArray;

  }

这是我的所有代码:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

import { Box } from "./Box";

 

export function Board() {

  let BLANK_BOARD = [

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

  ];

 

  let NEW_BOARD = [

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

    [0, 0, 0, 0, 0, 0, 0, 0, 0],

  ];

 

  let counter: number = 0;

  let check: number[];

  const numArray: number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9];

 

  function rowSafe(

    puzzleArray: number[][],

    emptyCell: { rowIndex: number; colIndex: number },

    num: number

  ): boolean {

    return puzzleArray[emptyCell.rowIndex].indexOf(num) == -1;

  }

 

  function colSafe(

    puzzleArray: number[][],

    emptyCell: { rowIndex: number; colIndex: number },

    num: number

  ): boolean {

    let test = puzzleArray.flat();

    for (let i = emptyCell.colIndex; i < test.length; i += 9) {

      if (test[i] === num) {

        return false;

      }

    }

    return true;

  }

 

  function regionSafe(

    puzzleArray: number[][],

    emptyCell: { rowIndex: number; colIndex: number },

    num: number

  ): boolean {

    const rowStart: number = emptyCell.rowIndex - (emptyCell.rowIndex % 3);

    const colStart: number = emptyCell.colIndex - (emptyCell.colIndex % 3);

 

    for (let i = 0; i < 3; i++) {

      for (let j = 0; j < 3; j++) {

        if (puzzleArray[rowStart + i][colStart + j] === num) {

          return false;

        }

      }

    }

    return true;

  }

 

  console.log(rowSafe(BLANK_BOARD, { rowIndex: 4, colIndex: 6 }, 5));

  console.log(colSafe(BLANK_BOARD, { rowIndex: 2, colIndex: 3 }, 4));

  console.log(regionSafe(BLANK_BOARD, { rowIndex: 5, colIndex: 6 }, 5));

 

  function safeToPlace(

    puzzleArray: number[][],

    emptyCell: { rowIndex: number; colIndex: number },

    num: number

  ): boolean {

    return (

      regionSafe(puzzleArray, emptyCell, num) &&

      rowSafe(puzzleArray, emptyCell, num) &&

      colSafe(puzzleArray, emptyCell, num)

    );

  }

 

  console.log(safeToPlace(BLANK_BOARD, { rowIndex: 5, colIndex: 6 }, 5));

 

  function nextEmptyCell(puzzleArray: number[][]): {

    colIndex: number;

    rowIndex: number;

  } {

    let emptyCell = { rowIndex: -1, colIndex: -1 };

    for (let i = 0; i < 9; i++) {

      for (let j = 0; j < 9; j++) {

        if (puzzleArray[i][j] === 0) {

          return { rowIndex: i, colIndex: j };

        }

      }

    }

    return emptyCell;

  }

 

  function shuffle(array: number[]): number[] {

    // using Array sort and Math.random

 

    let shuffledArr = array.sort(() => 0.5 - Math.random());

    return shuffledArr;

  }

 

  function fillBoard(puzzleArray: number[][]): number[][] {

    if (nextEmptyCell(puzzleArray).colIndex === -1) return puzzleArray;

 

    let emptyCell = nextEmptyCell(puzzleArray);

 

    for (var num in shuffle(numArray)) {

      if (safeToPlace(puzzleArray, emptyCell, numArray[num])) {

        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = numArray[num];

        fillBoard(puzzleArray);

      } else {

        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = 0;

      }

    }

 

    return puzzleArray;

  }

 

  console.log(nextEmptyCell(BLANK_BOARD));

 

  NEW_BOARD = fillBoard(BLANK_BOARD);

 

  function fullBoard(puzzleArray: number[][]): boolean {

    return puzzleArray.every((row) => row.every((col) => col !== 0));

  }

 

  return (

    <div

      style={{

        height: "450px",

        width: "450px",

        display: "inline-grid",

        gap: "10px",

        gridTemplateColumns: "repeat(9,50px)",

        gridTemplateRows: "repeat(9,50px)",

        position: "absolute",

        top: "30px",

        left: "0px",

        right: "0px",

        marginLeft: "auto",

        marginRight: "auto",

      }}

    >

      {NEW_BOARD.flat().map((item) => (

        <Box i={item} />

      ))}

    </div>

  );

}

P粉135799949P粉135799949566 天前600

全部回复(1)我来回复

  • P粉638343995

    P粉6383439952023-09-08 17:29:57

    当发现在一个空白单元格中无法添加有效数字时,该函数将返回一个不完整的数独板。

    为了解决这个问题,你的函数应该:

    • 实现正确的回溯,即撤销一个不成功的移动
    • 使函数返回一个布尔值(表示成功/失败)--不需要返回puzzleArray,因为该数组在原地进行了修改,所以调用者可以访问到这些变化。
      • 这也意味着NEW_BOARD = fillBoard(BLANK_BOARD);的副作用是NEW_BOARDBLANK_BOARD引用了同一个数独板,而且它不再是空白的(所以名称有误导性)。
    • 在成功时中断/返回循环。

    下面是修改后的实现:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    function fillBoard(puzzleArray: number[][]): boolean {

        if (nextEmptyCell(puzzleArray).colIndex === -1) return true; // 布尔值

     

        let emptyCell = nextEmptyCell(puzzleArray);

     

        for (var num in shuffle(numArray)) {

          if (safeToPlace(puzzleArray, emptyCell, numArray[num])) {

            puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = numArray[num];

            if fillBoard(puzzleArray) return true; // 成功时退出

          }

        }

        puzzleArray[emptyCell.rowIndex][emptyCell.colIndex] = 0; // 撤销

        return false; // 布尔值 - 没有成功

    }

    调用者应该检查返回值,但如果你从一个空白板开始,保证会得到true作为返回值。所以你可以这样做:

    1

    2

    3

    const puzzleArray = BLANK_BOARD.map(row => [...row]); // 深拷贝

    const success = fillBoard(puzzleArray); // 返回一个布尔值

    // ... 对puzzleArray做一些操作 ...

    回复
    0
  • 取消回复